Der Artikel sollte vollständig überarbeitet werden
Bearbeitenzwei Referenzen
BearbeitenIch habe 2 Dokumente gefunden, wo der Algoritmus beschrieben ist:
- Der A* Algorithmus wird in "S. Russel, P. Norvig (1995). Artificial Intelligence - A Modern Approach", Seite 96ff beschrieben.
- Für den Originalartikel von "Peter E. Hart, Nils J. Nilsson und Bertram Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths, Transactions of Systems Sciences and Cybernetics, July 1968" gibt es schon eine Link hier im Artikel
Referenzen aus Stewart, Norvig
Bearbeiten- Pohl I, Practical and theoretical considerations in heuristics search algorithms
- Mero, L., A heuristic seatch algorithm with modifiable estimate
- Pohl I., First results on the effect of error in heuristic search
- Judea Pearl: Heuristics: Intelligent Search Strategies for Computer Problem Solving 1984, Addison-Wesley, S.82f
- Nilsson, N., Problem-Solving Methods in Artificial Intelligence, New York: McGraw-Hill, 1971.
- Nilsson, N., Principles of Artificial Intelligence, San Francisco: Morgan Kaufmann, 1980.
- Peter E. Hart, Nils J. Nilsson, Bertram Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths: IEEE Transactions on Systems Science and Cybernetics, Volume 4, Issue 2, July 1968, S.100–107
- Peter E. Hart, Nils J. Nilsson, Bertram Raphael: Correction to „A Formal Basis for the Heuristic Determination of Minimum Cost Paths“ ACM SIGART Bulletin: Issue 37, December 1972, S.28–29
https://www.python-forum.de/viewtopic.php?f=1&t=43367
Generalized Best First Search Strategies and the Optimality of A*; Rina Dechter, Judea Pearl
http://ai.stanford.edu/~nilsson/publications.html
http://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/astar.pdf
Python
Bearbeitenhttps://docs.python.org/3.5/reference/datamodel.html#customization
https://docs.python.org/3.5/library/stdtypes.html#sequence-types-list-tuple-range
Ähnlicher Algorithmus
BearbeitenB* Algorithnus von Hans Berliner
Anwendungen
Bearbeitenhttps://de.wikipedia.org/wiki/15-Puzzle
Links
Bearbeitenmonoton = consistent p 102 lesen
https://www.amazon.com/Principles-Artificial-Intelligence-Nils-Nilsson-ebook/dp/B01E548U26
Ein Graph
BearbeitenHier müssen geschlossene Knoen wider geöffnet werden, sonst funktioniert das nicht.
Knoten: S A B C E Kanten: SA SB AC BC CE S: start E: end
x h(x) ------- S 0 A 4 B 0 C 0 E 0
x c(x) ------- SA 1 SB 2 AC 1 BC 1 CE 3
Greedy Algorithm - Literaturhinweise
BearbeitenAlgorithmen und Datenstrukturen: Die Grundwerkzeuge
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
Heidelberg, 2014
p 307
"Die Bezeichnung Greedy-Algorithmus (...) wird für eine algorithmische Strategie benutzt, bei der die betrachteten Objekte in einer gewissen (meist sorgfältig gewählten) Reihenfolge nacheinander betrachtet werden, und eine Entscheidung über ein Objekt (z- B. ob es in die Lösung aufgenommen wird oder nicht) in dem Moment getroffen wird, in dem dieses Objekt betrachtet. Einmal getroffene Entscheidungen werden nachher nie mehr geändert."
E. Horowitz, S. Sahni, S. Rajasekaran
Computer Algorithms
New York, 1998
Chapter 4, The Greedy Method
4.8 Single-Source Shortest Paths
p.244
"This Algorithm (known as Dijkstra's Algorithm) (...)"
A. Aho, J. E. Hopcroft, J. D. Ullman
Data Structures and Algorithms
CHAPTER 6: Directed Graphs
6.3 The Single Source Shortest Paths
"To solve this problem we shall use a "greedy" technique, often known as Dijkstra's algorithm."
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein
Introduction to Algorithms
Third Edition
Cambridge, Massachusetts London, England, 2009
VI Graph Algorithms
24 Single-Source Shortest Paths
24.3 Dijkstra’s algorithm
p 659
"Because Dijkstra’s algorithm always chooses the “lightest” or “closest” vertex in to add to set , we say that it uses a greedy strategy. (...) Greedy strategies do not always yield optimal results in general, but as the following theorem and its corollary show, Dijkstra’s algorithm does indeed compute shortest paths. (...)"
