- Tytuł:
- Dijkstras algorithm revisited: the dynamic programming connexion
- Autorzy:
- Sniedovich, M.
- Powiązania:
- https://bibliotekanauki.pl/articles/970872.pdf
- Data publikacji:
- 2006
- Wydawca:
- Polska Akademia Nauk. Instytut Badań Systemowych PAN
- Tematy:
-
programowanie dynamiczne
badania operacyjne
Dijkstra's algorithm
dynamic programming
greedy algorithm
principle of optimality
successive approximation
operations research
computer science - Opis:
- Dijkstra's Algorithm is one of the most popular algorithms in computer science. It is also popular in operations research. It is generally viewed and presented as a greedy algorithm. In this paper we attempt to change this perception by providing a dynamic programming perspective on the algorithm. In particular, we are reminded that this famous algorithm is strongly inspired by Bellman's Principle of Optimality and that both conceptually and technically it constitutes a dynamic programming successive approximation procedure par excellence. One of the immediate implications of this perspective is that this popular algorithm can be incorporated in the dynamic programming syllabus and in turn dynamic programming should be (at least) alluded to in a proper exposition/teaching of the algorithm.
- Źródło:
-
Control and Cybernetics; 2006, 35, 3; 599-620
0324-8569 - Pojawia się w:
- Control and Cybernetics
- Dostawca treści:
- Biblioteka Nauki
Artykuł