Kürzester Weg

[spong3bob]

Hallo!
Ich habe von der schule aus eine aufgabe bekommen: wir sollen einen plan von der schule zeichnen, und dann den kürzesten weg von A nach B ausgeben

Jetzt mein Ansatz: ich speicher Punkte (x,y) als Objekt ab. in den punkten speicher ich auch immer die nebenliegenden punkte ab..
mein problem ist aber, wie ich jetzt den kürzesten weg berechne?

(vl. aus auch der ansatz mit den punkten nicht so gut.. wenn euch was besseres einfallt.. ich bin für (fast) alles offen )

noch ein kleines bild:

d.h. die punkte können auch im kreis gehen, und ich möchte natürlich endlosschleifen vermeiden :?

danke für alle konstruktiven antworten

 

[Wildcard]

http://de.wikipedia.org/wiki/Dijkstra-Algorithmus

 

[Der Müde Joe]

oder:
http://de.wikipedia.org/wiki/A*-Algorithmus

 

[Marco13]

Oder gleich
http://de.wikipedia.org/wiki/Kürzester_Pfad

 

[spong3bob]

was is das für programmier sprache??
verwirrt mich ein bisschen

werds morgen mal mit Djikstra probieren.. wird aber denk ich mal bald mein nächster post kommen ..

 

[Der Müde Joe]

was is das für programmier sprache??

nennt sich Pseudocode

Google hilft bei suche nach geeigneter Sprache (falls dus nicht selber machen willst)

 

[spong3bob]

ok.. ich hab jetzt mal die Punkt-klasse geschrieben...
diese enthält: x,y position und eine ArrayList mit allen möglichen nachbarn..
aber jetzt steh ich irgendwie auf der leitung..
mir fehlt irgendwie ein ansatz.. wie speichere ich alle möglichen wege?

 

[bygones]

ich habe vor ca 3 jahren http://www.jdsl.org/ benutzt um dies fuer http://www.ebi.ac.uk/intact/mine/ zu loesen - bei dem es ebenso um den kuerzesten weg ging (hier bzgl proteininteraktoren, aber egal).... keine ahnung obs mittlerweilen was besseres gibt.

Damals war die lib sehr gut....

 

[SlaterB]

gar nicht, wäre zu viel Speicher,
es reicht, wenn du nach und nach ein paar Knoten auswählst und maximal pro Knoten einen Weg speicherst,

dazu kannst du in der Knoten-Klasse den Weg speichern,
ArrayList anderer Knoten oder ähnlich simples,

 

[spong3bob]

wie soll das gehen,dass ich pro knoten einen weg speicher... das funktioniert doch dann nichtmehr bei "kreuzungen", wo dann 3 andere knoten an den anschließen z.B.???

 

[SlaterB]

wie gesagt, du sollst nicht ALLE Wege speichern sondern nur ein paar im Laufe der Suche

 

[spong3bob]

ich weiß ja nicht, was ich speichern muss, und was nicht, bis ich am ziel, bzw. an einer sackgasse angekommen bin?

 

[SlaterB]

tja, das ist aber kein Argument,
wenn du das Quadrat von 420 ausrechnest, dannn speicherst du doch auch nicht vorsorglich alle Zahlen von 0 bis 10 Mio oder?

um den kürzesten Weg herauszufinden musst du eines der genannten Verfahren verwenden,
dabei wirst du durchaus zum Problem des Speichers von Wegen kommen,
es ist also nicht verkehrt, darüber schonmal nachzudenken,
aber es werden nur einige wenige Wege sein

 

[spong3bob]

hmmm die wege muss ich speichern, weil die punkte nicht in irgendeiner symmetrie oder so liegen.. und man den start und zielpunkt ändern können muss, und wenn ich nicht speicher welcher punkt mit welchem verbunden ist weiß ich nachher nichtmehr, welche verbindungen möglich sind...

 

[SlaterB]

du möchtest also zu jedem Knoten seine 1-3 Nachbarknoten abspeichern,
das ist ja eine ganz andere Frage als 'wie speichere ich alle möglichen wege [von beliebigen Knoten zu beliebigen anderen]?'
da siehst du mal wie genau man in der Informatik sein muss

die Lösung ist nicht viel anders:
speichere zu jedem Knoten eine Liste benachbarter Knoten,
ArrayList z.B.

(lies 'Knoten' ruhig immer als 'Punkt' )

 

[jPat]

Du speicherst alle Knoten bis du bei einer Sackgasse angekommen bist, oder bis du an einem Knoten angekommen bist, den du schon gespeichert hast, oder bis zum Ziel. Falls einer dieser punkte erreicht ist (Am Ziel angekommen kannst du die Liste mal ausgeben) nimmst du immer den letzten knoten aus der Liste heraus, prüfst, ob es eine Abzweigung von diesem Knoten existiert, wenn ja, dann wieder rein damit. -> Neuer weg >- wenn nein, dann wieder den letzten raus, prüfen ... .
Dijkstra benutzt zum speicher des Weges eine Stack. pop(): raus aus der List, push(): rein in die Liste. zum Prüfen ob du ein Knoten schon in deiner Liste hast, mußt du nachschauen, ob dieser in der liste vorhanden ist.
Das Problem ist recursiv zu Implementieren.

 

[spong3bob]

genau das hab ich bis jetzt gemacht
(siehe erster post)
meine frage is jetzt weiter vorgeh, dass ich den weg finde

€. sry ned gsehn, dass schon 2. seite existiert...
werd mir das mal zu herzen nehmen

 

[SlaterB]

> meine frage is jetzt weiter vorgeh, dass ich den weg finde

siehe Antwort jPat, siehe Verfahren in der Literatur,
stelle konkrete Fragen

 

[jPat]

Class Knoten { // 
  ArrayList<Knoten> nachbarn = new ArrayList<Konten>();
  addNachbar(Knoten k){
      nachbarn.add(k);
  }
}

Class main{

ArrayList<Knoten> weg = new ArrayList<Knoten>();
public static void main(String args){
Knoten start = new Knoten();
Konten k1 = new Knoten();
Knoten k2 = new Knoten();
...
// du kannst bei deiner Zeichnung die Knoten als k1 ... kn durchnummerieren. nun die richtigen hinzufügen.

start.addNachbar(k1); // Rechter anfang
start.addNachbar(k2); // Linker Anfang
// ... usw

}


public void findeWeg(Knoten start,Knoten ziel){

}
}

so würde ich anfangen. Der start-Knoten enthällt den gesamten Graphen, k1,k2 sind dann abzweigungen. in die Abzweigungen kannst du dann weiteren nachbarn hineintun.

Evtl. hilft dir ja eine Adjazenzliste / Matrix ....

Ist ja nur mal ein denkansatz ..... :wink:

 

[spong3bob]

hmm so in etwa bin ich eh schon gewesen

Der start-Knoten enthällt den gesamten Graphen

was meinst du damit??
sollen in start alle knoten gespeichert werden???
ich hab in jedem knoten jeweils dessen nachbarn gespeichert...
mein problem war eher, was nachher in der findeWeg methode drin steht ^^

 

[Der Müde Joe]

mein problem war eher, was nachher in der findeWeg methode drin steht ^^

DSSP = Dijkstras Single Shortest Path.....naja der Dijkstra Algorithmus halt...oder einer der anderen

 

[jPat]

In start sind alle knoten drin, da man über die nachbarfelder durch den gesamten Graphen durchgehen kann.

Es ist deine "wurzel".

 

[spong3bob]

hmm versteh ich nicht ganz, wozu ich das brauch....

 

[jPat]

Ich glaub, wir reden an einander vorbei .... so wie du es machst, ist es schon richtig. Nicht alle Knoten sind im start-knoten enthalten. Aber, man kommt vom Startknoten aus über die benachbarten felder zu jedem anderen knoten hin. Das wollte ich damit sagen, das es der root knoten ist.

Hast du jetzt schon mal ein wenig code geschrieben? Dann zeig mal, was du schon hast ...