[JAVA] 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.

  1. Définissez la distance la plus courte 0 comme point de départ
  2. Déplacez-vous à la distance la plus courte connue des points que vous n'avez pas encore tracés
  3. 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.
  4. 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. image.png

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 dijkstra algo.gif

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

image.png

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.

image.png

image.png

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? image.png

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.

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

Algorithme Dikstra pour les débutants
Paramètres Spacemacs (pour les débutants)
Manuel python pour les débutants
OpenCV pour les débutants en Python
[Pour les débutants] kaggle exercice (merucari)
Distribution Linux recommandée pour les débutants
CNN (1) pour la classification des images (pour les débutants)
Construction de l'environnement Python3 (pour les débutants)
Vue d'ensemble de Docker (pour les débutants)
Les bases de Seaborn pour les débutants ④ Pairplot
Grammaire de base Python pour les débutants
Pandas 100 coups pour les débutants en Python
Python #function 1 pour les super débutants
#List Python pour les super débutants
~ Conseils pour les débutants de Python présentés avec amour par Pythonista ③ ~
[Pour les débutants de Kaggle] Titanic (LightGBM)
Mémorandum de commande Linux [pour les débutants]
Raccourci Linux pratique (pour les débutants)
[Pour les débutants] Re: Algorithme génétique partant de zéro [Intelligence artificielle]
[Explication pour les débutants] Tutoriel TensorFlow MNIST (pour les débutants)
Traduction TensorFlow MNIST pour les débutants en ML
Arbre de décision (pour les débutants) -Édition de code-
Principes de base de Pandas pour les débutants ⑧ Traitement des chiffres
Exercices Python pour les débutants # 2 [pour instruction / instruction while]
Bases de Seaborn pour les débutants ② histogramme (distplot)
[Pour les débutants] Django -Construction d'environnement de développement-
[Pour les débutants] Script en 10 lignes (1.folium)
Python #index pour les super débutants, tranches
<Pour les débutants> bibliothèque python <Pour l'apprentissage automatique>
Tutoriel TensorFlow MNIST pour les débutants en ML
Commandes Linux fréquemment utilisées (pour les débutants)
[À voir pour les débutants] Bases de Linux
Fonction Python #len pour les super débutants
Web scraping pour les débutants en Python (1)
Exécutez unittest en Python (pour les débutants)
Qu'est-ce que xg boost (1) (pour les débutants)
Algorithme pour trouver des critiques de spam complices
Web scraping pour les débutants en Python (4) -1
Python #Hello World pour les super débutants
Régression linéaire (pour les débutants) -Édition de code-
Python pour les super débutants Super débutants Python # dictionnaire type 2
Lien récapitulatif des bases de Pandas pour les débutants
[Pour les débutants] Surveillance des processus à l'aide de cron
LSTM (1) pour la prédiction de séries chronologiques (pour les débutants)
[Déprécié] Tutoriel pour débutant Chainer v1.24.0
Tutoriel TensorFlow -MNIST pour les débutants en ML
Ridge Return (pour les débutants) -Code Edition-
[Explication pour les débutants] Tutoriel TensorFlow Deep MNIST
INSÉRER dans MySQL avec Python [Pour les débutants]
[Kaggle pour les super débutants] Titanic (retour logistique)
[Python] Compte-rendu de la réunion d'étude pour les débutants (7/15)
Premiers pas pour les débutants en apprentissage automatique (IA)
[Résumé des commandes Linux] Liste des commandes [À voir absolument pour les débutants]
Mettons ensemble Python pour les super débutants
Résumé du tutoriel Django pour les débutants par les débutants ③ (Afficher)
Implémentation et description à l'aide de XGBoost pour les débutants
Fonctionnement Linux pour les débutants Résumé des commandes de base
Détection d'anomalies de données chronologiques pour les débutants
Notes supplémentaires pour TensorFlow MNIST pour les débutants en ML