Der Artikel sollte vollständig überarbeitet werden

Bearbeiten

zwei Referenzen

Bearbeiten

Ich 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

https://www.python-forum.de/viewtopic.php?f=1&t=43367

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, The MIT Press; Auflage: 3 (31. Juli 2009), S.162ff


Generalized Best First Search Strategies and the Optimality of A*; Rina Dechter, Judea Pearl

https://www.researchgate.net/publication/238799612_A_Formal_Basis_for_the_Heuristic_Determination_of_Minimum_Cost_Paths

http://ai.stanford.edu/~nilsson/publications.html


http://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/astar.pdf

https://docs.python.org/3.5/reference/datamodel.html#customization

https://docs.python.org/3.5/library/stdtypes.html#sequence-types-list-tuple-range

https://docs.python.org/3.5/library/heapq.html

https://github.com/python/cpython/blob/3.5/Lib/heapq.py

Ähnlicher Algorithmus

Bearbeiten

B* Algorithnus von Hans Berliner

Anwendungen

Bearbeiten

https://de.wikipedia.org/wiki/15-Puzzle

https://de.scribd.com/document/371597469/Judea-Pearl-Heuristics-Intelligent-Search-Strategies-for-Computer-Problem-Solving

monoton = consistent
p 102 lesen

https://books.google.at/books/about/Principles_of_Artificial_Intelligence.html?id=4JwN5DTpcqkC&redir_esc=y

https://www.amazon.com/Principles-Artificial-Intelligence-Nils-Nilsson-ebook/dp/B01E548U26

Ein Graph

Bearbeiten

Hier 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

Bearbeiten

Algorithmen 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. (...)"