A* Algorithmus

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Vykyfikation
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 9. Mai 2017 12:44

A* Algorithmus

Beitrag von Vykyfikation » 12. Jun 2017 16:16

Hallo,
Ich brauche mal wieder eure Hilfe.
ich komme einfach mit diesen riesen Allgorithmen nicht klar. Grade versuche ich mich an A Stern und scheitere schon am Preprocessing. Irgendwie wird mir nich so ganz klar, wie ich denn ohne Konstruktoren eine neue Priority Queue erstellen soll, oder eine neue ArrayList. Dann wird mir nicht klar, wie ich denn die predecessorsMap mit den gegebenen Methoden instanzieren soll. Ebenso bei der SourceDistanceMap.
Hier mal mein Witz von Code:

Code: Alles auswählen

{
    if(getGraph() == null || getGraph().getNodeList().size() == 0) throw new InvalidInputException("Graph incorrect");
    if(getSourceNode() == null || !getGraph().getNodeList().contains(getSourceNode())) throw new InvalidInputException("SourceNode incorrect");
    if(getTargetNode() == null || !getGraph().getNodeList().contains(getTargetNode())) throw new InvalidInputException("TargetNode incorrect");
    setPathFound(false);
    PriorityQueue pri = new ProrityQueue(AbstractGraph.getComperator());
    pri.offer(getSourceNode());
    setOpenList(pri);
    setClosedList(new ArrayList());
    
}
Irgendwie komme ich einfach nicht mit diesen riesen Methoden klar. Wie soll man das denn alles in einer Stunde schaffen? Irgendwie hat man doch echt die Arschkarte gezogen, wenn man als Aufgabenstellung so eine 50 Punkte Aufgabe bekommt. Denn wenn man nicht alle Methoden implementiert hat schlägt jeder Test fehl. Oder werden im Testat dann nur einzelne Methoden abgefragt?

tna_wirth
Neuling
Neuling
Beiträge: 9
Registriert: 20. Okt 2013 23:51

Re: A* Algorithmus

Beitrag von tna_wirth » 19. Jun 2017 13:17

Du hast doch bereits bei der PriorityQueue und der ArrayList die instanziierung mit Konstruktor korrekt durchgefuehrt. Bei den beiden HashMaps erfolgt die Erzeugung mittels Konstruktor analog.

AStern bekommt ab heute auch eine neue TestSuite, bei der die Fehlermeldungen klarer formuliert und das erreichen von Teilpunkten einfacher sein sollte.
AuD - Codemonkey - Graphen u. Baeume - Development

Kabooom
Erstie
Erstie
Beiträge: 19
Registriert: 17. Jun 2017 15:04

Re: A* Algorithmus

Beitrag von Kabooom » 20. Jun 2017 18:51

Hallo Vykyfikation,

ich habe ein paar Anmerkungen zu deinem Code, die dir vielleicht helfen könnten:
  • Denk dran, alle generischen Datenstrukturen wie die PriorityQueue und die ArrayList mit den korrekten generischen Typen zu erstellen, also z.B. PriorityQueue<Node<N,E>> und ArrayList<Node<N,E>>
  • Ich finde es auch nicht gut, dass in den Aufgabenstellungen keine Konstruktoren angegeben werden. Bei der PriorityQueue wird allerdings in der Aufgabenstellung erwähnt, dass diese im Konstruktor einen Comparator über die Methode getQueueComparator erhalten soll
  • Die Methode offer von PriorityQueue gibt das erste Element der Queue zurück und entfernt es aus der Queue. Wenn du den Startknoten in die PriorityQueue einfügen willst, musst du stattdessen eigentlich die Methode add verwenden. Diese ist aber aus irgendeinem Grund in der Aufgabenstellung nicht gelistet und wird von Codemonkeys auch noch blockiert, obwohl genau diese Methode in allen anderen Aufgabenstellungen mit PriorityQueues verwendet wurde...
  • Um die beiden HashMaps zu erstellen kannst du einfach einen leeren Konstruktor verwenden (z.B. HashMap<Node<N,E>, Node<N,E>> predecessors = new HashMap<Node<N,E>, Node<N,E>>();). Danach kann ein Key-Value-Paar mit der Methode put eingefügt werden. Da die Setter-Methoden für diese beiden HashMaps leider wie so vieles nicht aufgelistet sind, konnte ich sie auch nur durch Ausprobieren herausfinden: setPredecessorMap und setSourceDistanceMap

Kabooom
Erstie
Erstie
Beiträge: 19
Registriert: 17. Jun 2017 15:04

Re: A* Algorithmus

Beitrag von Kabooom » 21. Jun 2017 14:26

Entschuldigung, ich habe bei der PriorityQueue etwas vertauscht, offer wird doch verwendet um ein Element einzufügen, nicht um eines zu entfernen

Antworten

Zurück zu „AuD: Programmieraufgaben“