Je me demandais quelle était la différence entre recherche à coût uniforme y Algorithme de Dijkstra . Il semble qu'il s'agisse du même algorithme.
Réponses
Trop de publicités?
NotAUser
Points
1296
l'algorithme de Dijkstra, qui est peut-être plus connu, comme une variante de la recherche à coût uniforme, où il n'y a pas d'état but et où le le traitement se poursuit jusqu'à ce que tous les nœuds aient été retirés de la liste des priorités. prioritaires, c'est-à-dire jusqu'à ce que les chemins les plus courts vers tous les nœuds (et pas seulement vers un nœud but) aient été déterminés. nœud cible) aient été déterminés
http://en.wikipedia.org/wiki/Uniform-cost_search#Relationship_to_other_algorithms
RobertoR
Points
424
L'algorithme de Dijkstra recherche Chemins les plus courts entre la racine et tous les autres nœuds dans un graphe, alors que le coût uniforme recherche des les chemins les plus courts en termes de coût vers un nœud cible .
En outre, le coût uniforme nécessite moins d'espace, tandis que la file d'attente prioritaire est remplie "paresseusement", contrairement à la méthode de Dijkstra, qui ajoute tous les nœuds à la file d'attente dès le départ, ce qui entraîne un coût infini.
VineetNayak28
Points
337
Compilation d'autres réponses de NotAUser, dreaMone et Bruno Calza
L'algorithme de Dijkstra trouve le chemin le plus court entre le nœud racine et tous les autres nœuds. L'algorithme du coût uniforme recherche les chemins les plus courts en termes de coût entre le nœud racine et un nœud cible. La recherche de coût uniforme est l'algorithme de Dijkstra qui se concentre sur la recherche d'un seul chemin le plus court vers un seul point d'arrivée plutôt que le chemin le plus court vers chaque point.
Pour ce faire, la NGC s'arrête dès que le point d'arrivée est trouvé. Pour Dijkstra, il n'y a pas d'état d'arrivée et le traitement se poursuit jusqu'à ce que tous les nœuds aient été retirés de la file d'attente prioritaire, c'est-à-dire jusqu'à ce que les chemins les plus courts vers tous les nœuds (et pas seulement vers un nœud d'arrivée) aient été déterminés.
Les NGC nécessitent moins d'espace, car la file d'attente prioritaire est remplie progressivement, contrairement à la méthode de Dijkstra, qui ajoute tous les nœuds à la file d'attente dès le départ, ce qui entraîne un coût infini.
En conséquence, Dijkstra prend plus de temps que UCS.
Les NGC sont généralement formulés pour les arbres, tandis que Dijkstra est utilisé pour les graphes généraux.
Djikstra n'est applicable qu'aux graphes explicites où le graphe entier est donné en entrée. La NGC commence par le sommet source et parcourt progressivement les parties nécessaires du graphe. Elle s'applique donc à la fois aux graphes explicites et aux graphes implicites (où les états/nœuds sont générés).
Bruno Calza
Points
74
Il existe un document qui traite des similitudes et des différences entre les deux.
http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4017/4357
