Benutzer:Miracle173/Entwurf2

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Artikel sollte vollständig überarbeitet werden

[Bearbeiten | Quelltext bearbeiten]

zwei Referenzen

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

B* Algorithnus von Hans Berliner

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

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