[PYTHON] Algorithme Dikstra pour les débutants
N'y a-t-il pas un algorithme Dyxtra? Il est difficile de se souvenir du nom, et il est peu probable que vous l'implémentiez dans la pratique, comme le problème d'itinéraire le plus court pour les graphiques pondérés, donc vous l'oublierez tout de suite. .. ..
Qu'est-ce que l'algorithme Dyxtra?
L'algorithme Dyxtra est un algorithme qui trouve le chemin le plus court d'un graphe. Je pense que beaucoup de gens n'ont entendu que le nom. C'est facile et simple à faire, mais c'est un peu difficile à atteindre, mais c'est un algorithme relativement facile à comprendre si vous comprenez chacun d'eux. Les recherches non pondérées, les labyrinthes, etc. peuvent être résolues par la recherche de priorité de largeur, mais si chaque côté est pondéré, vous devrez calculer toutes les rues après tout. En supposant que tous les sommets ne sont passés qu'une seule fois, s'il y a des côtés E, ce sera O (E!) Et la quantité de calcul explosera. C'est un peu difficile de calculer cela.
L'algorithme Dyxtra est un algorithme qui résout efficacement ces problèmes.
À propos, le coût de chaque côté doit être une valeur non négative (0 ou plus). Si un nombre négatif est inclus, la méthode Bellman-Ford etc. sera utilisée.
procédure
La procédure de la méthode Dyxtra est assez simple.
- Définissez la distance la plus courte 0 comme point de départ
- Déplacez-vous à la distance la plus courte connue des points que vous n'avez pas encore tracés
- Définissez la distance la plus courte entre les sommets connectés à ce sommet. À ce stade, si la distance la plus courte du sommet peut être mise à jour, mettez-la à jour.
- Faites ceci jusqu'à ce que vous connaissiez la distance la plus courte de tous les sommets
Eh bien, je pense que c'est un peu difficile à dire, alors voyons un exemple.
Exemple
C'est une méthode analogique, mais j'ai pu l'exprimer le plus. .. ..
Considérez l'itinéraire le plus court dans la figure ci-dessous.
Le vert est l'itinéraire le plus court et sera le sommet du mouvement. Le rouge est le point de départ. Le nombre à chaque sommet est le chemin le plus court à ce moment
Comme vous pouvez le voir, vous pouvez voir qu'il se déplace du point de départ à l'apex le plus court à ce point dans l'ordre, puis calcule le chemin le plus court de l'apex adjacent.
la mise en oeuvre
Passons maintenant à l'implémentation. Implémentons la procédure ci-dessus de manière simple.
function main(nodes) {
const start = nodes[0]
//Enregistrer les pics visités
const visited = new Set()
const routesFromStart = new Map()
//Enregistrez la distance depuis le point de départ
routesFromStart.set(start, {distance: 0})
for(const n of nodes) {
if(n != start) {
//Remplacez tous les sommets par l'infini sauf le début
routesFromStart.set(n, {distance: Number.MAX_VALUE})
}
}
let current = start
let routes = new Map()
while(current != null) {
visited.add(current)
for(const edge of current.edges) {
//Calculez la distance la plus courte entre les sommets adjacents de ce sommet et mettez à jour si elle est inférieure à la valeur calculée
if(edge.cost + routesFromStart.get(current).distance < routesFromStart.get(edge.to).distance) {
routesFromStart.set(edge.to, {distance: edge.cost + routesFromStart.get(current).distance})
routes.set(current, edge.to)
}
}
let cheapestNodeDistance = Number.MAX_VALUE
current = null
//Sélectionnez le plus petit sommet parmi les sommets calculés pour la distance non visitée la plus courte
for(const city of routesFromStart.keys()) {
if(!visited.has(city) && cheapestNodeDistance > routesFromStart.get(city).distance){
cheapestNodeDistance = routesFromStart.get(city).distance
current = city
}
}
}
return routesFromStart.get(nodes[nodes.length - 1]).distance
}
En supposant que chaque sommet est V, ce code fait tourner une boucle pour sélectionner le plus petit sommet parmi les boucles qui tournent le nombre maximum de chaque côté, de sorte que la quantité de calcul est O (V ^ 2 + E) pour chaque mémoire. C'est O (V) car il faut enregistrer les pics.
À propos de la mise en œuvre à l'aide de la file d'attente prioritaire
Eh bien, comme vous l'avez peut-être remarqué, ce code vous permet en fait d'optimiser la logique qui détermine les plus petits sommets. C'est la file d'attente prioritaire. Les files d'attente prioritaires nécessitent un calcul O (logN) pour l'insertion et la récupération, mais le calcul pour déterminer les plus petits sommets est plus rapide qu'une recherche linéaire.
La file d'attente prioritaire n'est pas implémentée en standard en JavaScript, elle est donc implémentée en Python.
def dijkstra(nodes):
start_node = nodes[0]
routes_from_start = {n: math.inf for n in nodes}
#Mettre zéro au premier sommet
routes_from_start[start_node] = 0
minHeap = []
#Ajouter le premier sommet
heappush(minHeap, (0, start_node))
#Rechercher jusqu'à ce que le tas soit épuisé
while minHeap:
(cost, current_node) = heappop(minHeap)
#La clé de priorité étant dupliquée, cochez ici
if cost > routes_from_start[current_node]:
continue
for node in current_node.routes:
price_info = current_node.routes[node]
if routes_from_start[node] > price_info + routes_from_start[current_node]:
routes_from_start[node] = price_info + routes_from_start[current_node]
#Ajouter de la valeur à la priorité lors de la mise à jour
heappush(minHeap, (price_info + routes_from_start[current_node], node))
return routes_from_start[nodes[-1]]
Profitons d'une autre occasion pour expliquer la file d'attente prioritaire. Si l'efficacité du calcul est meilleure et que chaque sommet est V et chaque côté est V, O (V) qui définit V à mapper et le tas sont exploités pour le nombre de fois de E, donc O (ElogE). Vous pouvez voir qu'il peut être calculé par le total O (V + ElogE) de. C'est plus efficace que le premier algorithme.
Souvenez-vous de l'itinéraire
Maintenant, je connais le coût le plus court. Mais ce problème est le problème du "chemin le plus court". Lorsque vous trouvez le coût le plus court, vous voulez généralement connaître l'itinéraire. Améliorons le code ci-dessus.
def dijkstra(nodes):
start_node = nodes[0]
routes_from_start = {n: math.inf for n in nodes}
#Mettre zéro au premier sommet
routes_from_start[start_node] = 0
minHeap = []
#Ajouter le premier sommet
heappush(minHeap, (0, start_node))
path = collections.defaultdict(Node)
#Rechercher jusqu'à ce que le tas soit épuisé
while minHeap:
(cost, current_node) = heappop(minHeap)
#La clé de priorité étant dupliquée, cochez ici
if cost > routes_from_start[current_node]:
continue
for node in current_node.routes:
price_info = current_node.routes[node]
if routes_from_start[node] > price_info + routes_from_start[current_node]:
routes_from_start[node] = price_info + routes_from_start[current_node]
#Enregistrez le nœud qui met à jour la distance la plus courte
path[node.id] = current_node.id
#Ajouter de la valeur à la priorité lors de la mise à jour
heappush(minHeap, (price_info + routes_from_start[current_node], node))
current_node = nodes[-1].id
path_array = []
#Suivez le nœud qui a enregistré la distance la plus courte de l'objectif
while current_node:
path_array.append(current_node)
if current_node not in path:
break
current_node = path[current_node]
return routes_from_start[nodes[-1]], path_array[::-1]
L'algorithme Dyxtra sait quel nœud met à jour la distance la plus courte, vous pouvez donc l'enregistrer et le suivre en dernier. La quantité de calcul augmentera du nombre de nœuds avec la distance la plus courte.
Au fait, pourquoi est-ce le chemin le plus court?
En passant, je pense que beaucoup de gens ont pensé de cette façon après l'avoir examiné jusqu'à présent. Bien sûr, l'algorithme est simple et il n'est pas trop difficile à mettre en œuvre. Mais pourquoi pouvez-vous trouver la distance la plus courte? Vérifions-le légèrement
En supposant que les sommets de L sont la distance la plus courte du début S, il serait bon de dire que les sommets les plus courts connectés à partir de là sont aussi la distance la plus courte de S.
Maintenant, puisqu'il se déplace vers le sommet le plus court inclus dans T, si le plus petit point est i, alors d [i] = min (T), n'est-ce pas? Maintenant, en supposant que chaque sommet est k, il est certain que la distance la plus courte d [k] est d [k]> = d [i]. Parce que d [i] est le plus petit point et que chaque sommet est non négatif. Vous pouvez le prouver de manière récursive en le faisant l'un après l'autre.
Eh bien, si vous y réfléchissez, c'est une formule progressive.
La distance la plus courte entre les sommets de L adjacents à d [i] = min (k ⊂ T) + i
Lorsqu'il s'agit d'une formule graduelle, la méthode de planification dynamique
La formule progressive est DP, n'est-ce pas? Cet article est très utile pour DP (https://qiita.com/drken/items/a5e6fe22863b7992efdb)
Alors, comment la valeur est-elle mise à jour avec DP?
La valeur sera mise à jour comme ceci. L'axe vertical représente le nombre d'essais. L'axe horizontal est le sommet.
Qu'est-ce que l'algorithme Dyxtra était une sorte de DP.
Résumé
L'algorithme Dyxtra que j'ai essayé, mais une fois que vous l'avez compris, il est assez facile à comprendre. Après cela, lorsque j'ai essayé de l'implémenter et que j'ai rencontré un problème similaire en raison d'un problème d'algorithme, c'était à ce moment-là! !! Je veux le résoudre comme ça.
- En passant, je veux aussi écrire un article DP
Cliquez ici pour la chaîne youtube expliquée https://youtu.be/jz8b0q5R1Ss
référence
http://www.lab2.kuis.kyoto-u.ac.jp/~shuichi/algintro/alg-6s.pdf https://www.youtube.com/watch?v=X1AsMlJdiok
Recommended Posts