Wegsuche - Facharbeit



  • Hi,

    Ich muss in Mathe in den nächsten Monaten eine Facharbeit schreiben mit dem Thema Wegsuche bzw. der kürzeste Weg in bewerteten Graphen.

    Kennt ihr da gute Bücher, sowohl zum Einstieg als auch weiterführend, die mir da helfen könnten?

    Gruß



  • Jedes Grundlagenbuch über Graphenalgorithmen enthält vermutlich Tiefen- und Breitensuche, sowie den Dijkstra-Algorithmus -- Cormen et al. "Introduction to Algorithms" zum Beispiel. Zu A* dürfte sich auch so einiges finden lassen und viel tiefer kannst Du im Rahmen einer Facharbeit vermutlich eh nicht einsteigen. Die moderneren Verfahren stehen eher nicht in Büchern, sondern in den entsprechenden Veröffentlichungen.



  • Mit "Introduction to Algorithms" sollte ich also einigermaßen durchkommen?

    Ich meine, im Internet findest man ja auch einiges, aber ich arbeite lieber mit Büchern.



  • Ich denke schon. Es ist sowohl single-source shortest paths drin, als auch die dafür nötigen Datenstrukturen (nämlich Heaps). Bellman-Ford ist auch beschrieben, damit ist von Theorie-Seite eigentlich alles abgedeckt.

    Ich finde, der Cormen ist recht gut lesbar, aber ich bin auch viel in dem Bereich tätig und kann das daher vermutlich nicht ganz objektiv einschätzen.
    Vielleicht hast Du die Möglichkeit Dir das Buch mal irgendwo auszuleihen? Es gibt auch eine deutsche Übersetzung, falls Du lieber deutsche Literatur verwenden möchtest.



  • Jester schrieb:

    Vielleicht hast Du die Möglichkeit Dir das Buch mal irgendwo auszuleihen? Es gibt auch eine deutsche Übersetzung, falls Du lieber deutsche Literatur verwenden möchtest.

    Mal schauen, ob die bayr. Staatsbibliothek das hat, dann könnte ich da mal reinsehen.

    Eine deutsche Übersetzung wäre natürlich am besten; mein Englisch ist zwar recht gut, aber wenn es schon eine Übersetzung gibt, brauche ich es ja nicht umständlich machen. 😉



  • Das müsste sie ja sein, oder?
    Algorithmen - Eine Einführung



  • godfather schrieb:

    Das müsste sie ja sein, oder?
    Algorithmen - Eine Einführung

    Ja, das ist das Buch.



  • Hatte TGGC nicht darueber irgendwas im Studium geschrieben und hier verlinkt?

    Ivo



  • Meine Diplomarbeit zu dem Thema findet sich auf meiner HP. Meine andere Artikel dazu sind weniger interessant. f'`8k

    Autocogito

    Gruß, TGGC (Das kommt gut)



  • Das ist gut, je mehr Quellen desto besser. 🙂

    Mal was anderes: es besteht die Möglichkeit, dass ich dazu ein Programm schreibe, das eben die Wegsuche simuliert; das wird mir dann vom Umfang der eigentlichen Facharbeit abgezogen, lohnt sich also durchaus.
    Sollte ich da eher zu leistungsstärkeren Sprachen, wie C, C++, etc. greifen, oder reichen Skriptsprachen, wie bsplw. Python/Ruby aus? Damit meine ich primär den Simulationsteil, wobei ich natürlich auch eine GUI schreiben müsste.

    Gruß



  • Ich denke, Du solltest die Sprache wählen, mit der es Dir am leichtesten fällt. Die Algorithmen sind recht schnell, so dass es vermutlich kein Problem ist, wenn die ein bißchen langsamer laufen. Das sind ja nur konstante Faktoren. 😉



  • Jester schrieb:

    Ich denke, Du solltest die Sprache wählen, mit der es Dir am leichtesten fällt.

    Das wäre dann Python. 🤡



  • Dieser nette Mensch hat schon ein paar Sachen in Python implementiert: http://www.ics.uci.edu/~eppstein/

    Siehe: http://www.ics.uci.edu/~eppstein/PADS/
    Dijkstra ist allerdings noch nicht dabei. 🙂
    Vielleicht hilft's bei irgendwas?



  • Jester schrieb:

    Siehe: http://www.ics.uci.edu/~eppstein/PADS/
    Dijkstra ist allerdings noch nicht dabei. 🙂
    Vielleicht hilft's bei irgendwas?

    "Gebookmarked". 😉



  • Hmm, das wird noch etwas dauern bis ich an das buch rankomme - ist gerade ausgeliehen.
    Hat jemand vielleicht gute (legale ;)) ebooks zu dem Thema oder grob in die Richtung?



  • "Introduction to Algorithms" hätte mich in der Oberstufe ehrlich gesagt überfordert.

    Ich denke, einfache, anschauliche und evtl. sogar graphisch verdeutlichte Webseiten sollten genügen.



  • tawa schrieb:

    Ich denke, einfache, anschauliche und evtl. sogar graphisch verdeutlichte Webseiten sollten genügen.

    Das Problem ist, dass viele Sachen im Web in Bereich ungenau bis schlicht falsch rangieren.

    Taschenbuch der Algorithmen | ISBN: 9783540763932

    Das ist ein echt schönes Buch, einerseits so geschrieben, dass man es ohne große Vorkenntnisse gut lesen kann, andererseits von Leuten, die wirklich in den Bereichen arbeiten. Kürzeste Wege ist auch drin. Und noch viel mehr.

    Das Buch ist aus dem "Algorithmus der Woche" aus dem Informatik-Jahr 2006 hervorgegangen. Die Webseite zu den kürzesten Wegen ist hier: http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo7.php


Log in to reply