Benutzer:Miracle173/Entwurf2

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Miracle173 auf.

Der Artikel sollte vollständig überarbeitet werden

zwei Referenzen

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

• 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

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

Python

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

B* Algorithnus von Hans Berliner

Anwendungen

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

Links

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

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

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 $V-S$ to add to set $S$, 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. (...)"