Trouvez le chemin critique de PERT en utilisant la recherche de priorité de largeur et la recherche de priorité de profondeur

Contexte

Atcoder a cessé de passer du marron J'ai commencé à étudier sérieusement les algorithmes. Maintenant que j'ai un peu de compréhension de la recherche de priorité de largeur (BFS) et de la recherche de priorité de profondeur (DFS) En guise de révision, des questions sont également données dans les questions d'examen de base des ingénieurs en information. L'heure du point de connexion le plus ancien, l'heure du dernier point de connexion et le chemin critique dans PERT J'ai décidé de demander.

Objectif

En saisissant les informations du graphe, en PERT ・ La première heure du point de connexion ・ L'heure du dernier point de connexion ·Chemin critique Mettez en œuvre un programme qui calcule.

À propos de la recherche de priorité de largeur (BFS) et de la recherche de priorité de profondeur (DFS)

L'article de @ drken était très facile à comprendre.

DFS (Recherche prioritaire en profondeur) Super Introduction! ~ Entrée dans le monde des algorithmes graphiques ~ [Partie 1]DFS (Recherche prioritaire en profondeur) Super Introduction! ~ Entrée dans le monde des algorithmes graphiques ~ [Partie 2]BFS (recherche de priorité à la largeur) Super Introduction! ~ Utilisez la file d'attente de façon vivante ~

À propos de PERT

En montrant l'ordre de travail et les dépendances sur le diagramme fléché, C'est une méthode pour clarifier le temps le plus court requis pour terminer le projet et les travaux de gestion les plus importants. Veuillez consulter l'article de @sakamoto_t. ・ Qu'est-ce que WBS?

Exemple

Le diagramme fléché suivant est utilisé comme exemple. PERT_図解.png

Code d'implémentation

main.py


from collections import deque
import numpy as np
import sys

def main():
    node_num, path_num, start, goal, path = input_data()
    Graph, Graph_critical, Graph_reverse, need_day = made_graph(node_num, path_num, path)
    earliest_node_time = bfs_normal(node_num, start, Graph, need_day)
    latest_node_time = bfs_reverse(node_num, goal, earliest_node_time, Graph_reverse, need_day)
    candidate = check_critical_candidate(node_num, latest_node_time, earliest_node_time)
    temp = list(check_critical_path(start, goal, candidate, Graph_critical))
    critical_path = [str(path) for path in temp]
            
    #-------------Partie de sortie-----------------
    print('------------------')
    print('Earliest_node_time')
    print(earliest_node_time)
    print('------------------')
    print('Latest_node_time')
    print(latest_node_time)
    print('------------------')
    print('Critical path')
    print(' -> '.join(critical_path))

    return 0
    
#---------------Partie d'entrée--------------------    
def input_data():
    node_num, path_num = map(int, input().split())
    start, goal = 1, node_num
    path = [input().split() for i in range(path_num)]
    return node_num, path_num, start, goal, path


#---------------Création de graphes-------------------
def made_graph(node_num, path_num, path):
    Graph = [deque([]) for i in range(node_num+1)] 
    Graph_critical = [deque([]) for i in range(node_num+1)]
    Graph_reverse = [deque([]) for i in range(node_num+1)]
    
    #Graph[0], Graph_reverse[0]Jette((Parce que le numéro de sommet est pris de 1 lors de la création de la structure graphique)

    need_day = np.zeros((node_num, node_num))

    for i in range(path_num):
        Graph[int(path[i][0])].append(int(path[i][1]))
        Graph_critical[int(path[i][0])].append(int(path[i][1]))
        Graph_reverse[int(path[i][1])].append(int(path[i][0]))     #Création d'un graphique inversé
        need_day[int(path[i][0]) - 1][int(path[i][1]) - 1] = int(path[i][2])
        need_day[int(path[i][1]) - 1][int(path[i][0]) - 1] = int(path[i][2])

    return Graph, Graph_critical, Graph_reverse, need_day
    

#------------Partie de travail BFS(Trouvez plus l'heure du point de connexion)------------------
def bfs_normal(node_num, start, Graph, need_day):
    stack = deque([start])
    earliest_node_time = [0 for i in range(node_num)]
    
    while stack:    #Continuez jusqu'à ce que la pile soit vide
        tmp = stack[0]
        if Graph[tmp]:
            w = Graph[tmp].popleft() 
            if earliest_node_time[w-1] < earliest_node_time[tmp-1] + need_day[tmp-1][w-1]:
                earliest_node_time[w-1] = int(earliest_node_time[tmp-1] + need_day[tmp-1][w-1])
                stack.append(w)
        else:
            stack.popleft()
    return earliest_node_time


#------------Partie de travail BFS(Trouvez l'heure du dernier point de connexion)------------------
def bfs_reverse(node_num, goal, earliest_node_time, Graph_reverse, need_day):
    stack = deque([goal])
    latest_node_time = [float('inf') for i in range(node_num)]
    latest_node_time[goal-1] = earliest_node_time[goal-1]
    while stack:    #Continuez jusqu'à ce que la pile soit vide
        tmp = stack[0]
        if Graph_reverse[tmp]:
            w = Graph_reverse[tmp].popleft() 
            if latest_node_time[w-1] > latest_node_time[tmp-1] - need_day[tmp-1][w-1]:
                latest_node_time[w-1] = int(latest_node_time[tmp-1] - need_day[tmp-1][w-1])
                stack.append(w)
        else:
            stack.popleft()
    return latest_node_time


#--------------EL =Extraire les points qui deviennent TL-------------------
def check_critical_candidate(node_num, latest_node_time, earliest_node_time):
    critical_candidate = [False for i in range(node_num)]
    for i in range(node_num):
        if latest_node_time[i] == earliest_node_time[i]:
            critical_candidate[i] = True
    return critical_candidate


#--------------Partie de travail DFS (suivi des points candidats du chemin critique et recherche de l'objectif)-----------
def check_critical_path(start, goal, candidate, Graph_critical):
    stack = [start]
    seen = deque([start])
    
    while stack:    #Continuez jusqu'à ce que la pile soit vide
        tmp = stack[-1]
        if Graph_critical[tmp]:
            w = Graph_critical[tmp].popleft() 
            if w == goal:
                seen.append(w)
                return seen
            elif candidate[w - 1]:
                seen.append(w)
                stack.append(w)
            else:
                continue
        else:
            stack.pop()
            seen.pop()
    return seen


if __name__ == '__main__':
    sys.exit(main())

        

contribution

Le nœud au début du travail est 1, et le nœud à la fin du travail est la valeur maximale du nœud (= node_num). $ N $: Nombre d'états (node_num) $ P $: Nombre d'œuvres (path_num) $ {s_i, g_i, K_i} $: état pré-travail, état post-travail, jours requis Comme

N\ P s_0\ g_0\ K_0 s_1\ g_1\ K_1 s_2\ g_2\ K_2 ・ ・ ・ s_{M-1}\ g_{M-1}\ K_{M-1}

Dans l'exemple d'image ci-dessus

7\ 8 1\ 2\ 17 2\ 4\ 7 4\ 6\ 5 6\ 7\ 11 1\ 3\ 11 3\ 4\ 5 3\ 5\ 10 5\ 6\ 9

Sera.

production

------------------
Earliest_node_time
[0, 17, 11, 24, 21, 30, 41]
------------------
Latest_node_time
[0, 18, 11, 25, 21, 30, 41]
------------------
Critical path
1 -> 3 -> 5 -> 6 -> 7

Ceci est expliqué ci-dessous.

Décomposition des problèmes

Pour trouver le chemin critique

  1. Trouvez l'heure du point de connexion le plus ancien (ci-après EL)
  2. Trouvez la dernière heure du point de connexion (TL)
  3. Extraire les candidats qui peuvent être des nœuds de chemin critique avec EL = TL Obtenir un exemple de chemin critique en effectuant une recherche de priorité de profondeur sous la condition de passer par le nœud candidat de 4,3

J'ai pensé à la mise en œuvre en 4 étapes. Je vais expliquer chacun d'eux.

Créer un graphique

Lors de la recherche de l'heure du dernier point de connexion, le nombre de jours requis pour chaque travail est calculé à partir des informations de l'heure du point de connexion le plus ancien de chaque nœud. Il était nécessaire de déplacer les flèches dans le graphique dans la direction opposée, car nous serions en train de tirer et de comparer. Par conséquent, lors de la création du graphique, créez un graphique avec le sens de déplacement opposé en même temps. J'ai décidé de mettre le nombre de jours ouvrables sous forme de matrice et de stocker les informations opposées en même temps.

   #---------------Création de graphes-------------------
def made_graph(node_num, path_num, path):
    Graph = [deque([]) for i in range(node_num+1)] 
    Graph_critical = [deque([]) for i in range(node_num+1)]
    Graph_reverse = [deque([]) for i in range(node_num+1)]
    
    #Graph[0], Graph_reverse[0]Jette((Parce que le numéro de sommet est pris de 1 lors de la création de la structure graphique)

    need_day = np.zeros((node_num, node_num))

    for i in range(path_num):
        Graph[int(path[i][0])].append(int(path[i][1]))
        Graph_critical[int(path[i][0])].append(int(path[i][1]))
        Graph_reverse[int(path[i][1])].append(int(path[i][0]))     #Création d'un graphique inversé
        need_day[int(path[i][0]) - 1][int(path[i][1]) - 1] = int(path[i][2])
        need_day[int(path[i][1]) - 1][int(path[i][0]) - 1] = int(path[i][2])

    return Graph, Graph_critical, Graph_reverse, need_day

"""
------------------
Path
[deque([2, 3]), deque([4]), deque([4, 5]), deque([6]), deque([6]), deque([7]), deque([])]
------------------
Reverse_Path
[deque([]), deque([1]), deque([1]), deque([2, 3]), deque([3]), deque([4, 5]), deque([6])]
------------------
Need_time
[[ 0. 17. 11.  0.  0.  0.  0.]
 [17.  0.  0.  7.  0.  0.  0.]
 [11.  0.  0.  5. 10.  0.  0.]
 [ 0.  7.  5.  0.  0.  5.  0.]
 [ 0.  0. 10.  0.  0.  9.  0.]
 [ 0.  0.  0.  5.  9.  0. 11.]
 [ 0.  0.  0.  0.  0. 11.  0.]]

"""

Trouvez l'heure de point de connexion la plus ancienne (ci-après, ET)

Ce problème est remplacé par le ** problème du choix du chemin qui maximise la somme des ** poids latéraux sur chaque nœud. Au contraire, la ** méthode Dyxtra ** est réputée comme un problème de chemin qui minimise le poids. Cette fois, je l'ai implémenté en utilisant cette idée.

   #------------Partie de travail BFS(Trouvez plus l'heure du point de connexion)------------------
def bfs_normal(start):
    stack = deque([start])
    
    while stack:    #Continuez jusqu'à ce que la pile soit vide
        tmp = stack[0]
        if Graph[tmp]:
            w = Graph[tmp].popleft() 
            if earliest_node_time[w-1] < earliest_node_time[tmp-1] + need_day[tmp-1][w-1]:
                earliest_node_time[w-1] = int(earliest_node_time[tmp-1] + need_day[tmp-1][w-1])
                stack.append(w)
        else:
            stack.popleft()
    return earliest_node_time

La recherche de priorité de largeur est effectuée et Earliest_node_time est mis à jour en ajoutant le nombre de jours ouvrables. S'il existe plusieurs itinéraires, mettez à jour s'il est supérieur à la valeur existante.

Trouver la dernière heure du point de connexion (LT)

Ensuite, trouvez le LT. À ce stade, la valeur initiale est infinie en tant que Latest_node_time. Préparez une baie et mettez-la à jour avec la plus petite.

 #------------Partie de travail BFS(Trouvez l'heure du dernier point de connexion)------------------
def bfs_reverse(goal):
    stack = deque([goal])
    latest_node_time[goal-1] = earliest_node_time[goal-1]
    while stack:    #Continuez jusqu'à ce que la pile soit vide
        tmp = stack[0]
        if Graph_reverse[tmp]:
            w = Graph_reverse[tmp].popleft() 
            if latest_node_time[w-1] > latest_node_time[tmp-1] - need_day[tmp-1][w-1]:
                latest_node_time[w-1] = int(latest_node_time[tmp-1] - need_day[tmp-1][w-1])
                stack.append(w)
        else:
            stack.popleft()
    return latest_node_time

Trouvez le chemin critique

Le chemin critique est fait en connectant les nœuds avec EL = TL. A l'inverse, il faut suivre les nœuds qui satisfont EL = TL pour atteindre l'objectif, donc ** Sous réserve de passer par des nœuds candidats avec EL = TL J'ai fait une recherche de priorité en profondeur et j'ai trouvé un problème d'arrivée d'objectif depuis le début. ** **

Extraire les nœuds candidats avec EL = TL en comparant chaque élément.


#--------------EL =Extraire les points qui deviennent TL-------------------
def check_critical_candidate(node_num, latest_node_time, earliest_node_time):
    critical_candidate = [False for i in range(node_num)]
    for i in range(node_num):
        if latest_node_time[i] == earliest_node_time[i]:
            critical_candidate[i] = True
    return critical_candidate

Enfin, DFS détermine si vous pouvez atteindre l'objectif. Déterminez si vous faites partie des candidats lorsque vous atteignez chaque nœud. Il se termine lorsque vous atteignez l'objectif, donc si vous avez plusieurs passes critiques Montrez-en un.


 #--------------Partie de travail DFS (suivi des points candidats du chemin critique et recherche de l'objectif)-----------
def check_critical_path(start, goal, candidate, Graph_critical):
    stack = [start]
    seen = deque([start])
    
    while stack:    #Continuez jusqu'à ce que la pile soit vide
        tmp = stack[-1]
        if Graph_critical[tmp]:
            w = Graph_critical[tmp].popleft() 
            if w == goal:
                seen.append(w)
                return seen
            elif candidate[w - 1]:
                seen.append(w)
                stack.append(w)
            else:
                continue
        else:
            stack.pop()
            seen.pop()
    return seen

Partie fonction principale

def main():
    node_num, path_num, start, goal, path = input_data()
    Graph, Graph_critical, Graph_reverse, need_day = made_graph(node_num, path_num, path)
    earliest_node_time = bfs_normal(node_num, start, Graph, need_day)
    latest_node_time = bfs_reverse(node_num, goal, earliest_node_time, Graph_reverse, need_day)
    candidate = check_critical_candidate(node_num, latest_node_time, earliest_node_time)
    temp = list(check_critical_path(start, goal, candidate, Graph_critical))
    critical_path = [str(path) for path in temp]
            
    #-------------Partie de sortie-----------------
    print('------------------')
    print('Earliest_node_time')
    print(earliest_node_time)
    print('------------------')
    print('Latest_node_time')
    print(latest_node_time)
    print('------------------')
    print('Critical path')
    print(' -> '.join(critical_path))

    return 0

Je veux l'écrire un peu plus joliment Je n'avais pas assez de connaissances. Je l'améliorerai un jour.

Résumé

・ Afin d'obtenir le temps du point de connexion, le graphe orienté pondéré Il peut être résolu comme un problème qui maximise la valeur de poids total **. (Reportez-vous à l'idée de la méthode Dyxtra) ・ Il est nécessaire de combiner DFS et BFS pour déterminer le chemin critique (?) → Je voudrais savoir s'il existe une meilleure solution.

Impressions

J'ai écrit un article sur Qiita pour la première fois, donc je suis heureux d'avoir pu m'entraîner à écrire des articles. J'aimerais écrire positivement et organiser mes pensées.

Autres références

Pour l'implémentation de BFS en utilisant Python, je me suis référé à l'article suivant de @ takayg1. ・ Algorithme en Python (recherche de priorité en profondeur, dfs)

Recommended Posts

Trouvez le chemin critique de PERT en utilisant la recherche de priorité de largeur et la recherche de priorité de profondeur
[Python] Recherche de priorité de profondeur et recherche de priorité de largeur
Trouver le diamètre du graphique par recherche de priorité de largeur (mémoire Python)
Calcul de l'itinéraire le plus court selon la méthode de Monte Carlo
Implémenter la recherche de priorité en profondeur (DFS) et la recherche de priorité de largeur (BFS) en python
Accrocher à la première importation du module et imprimer le chemin du module
Recherche de chemin dans le graphique à l'aide de Networkx
Découvrez l'âge et le nombre de gains des gouverneurs de préfecture dans tout le pays
Flux d'obtention du résultat du traitement asynchrone à l'aide de Django et Celery
[Python] Notification LINE des dernières informations à l'aide de la recherche automatique Twitter
[ffmpeg] Si vous ffmpeg en utilisant le sous-processus Python, le système ne peut pas trouver le chemin spécifié.
Obtenez et définissez la valeur du menu déroulant en utilisant Python et Selenium
Utilisez le SDK Qore pour prédire les augmentations et les baisses de prix BTC
Trouvez la distance (en tenant compte de la rondeur de la terre) de la latitude et de la longitude.
Trouvez le waypoint à partir de la latitude et de la longitude (en tenant compte de la rondeur de la terre).
Trouver l'intersection d'un cercle et d'une droite (matrice sympy)
Trouvez la définition de la valeur de errno
L'histoire de Python et l'histoire de NaN
Avantages et exemples d'utilisation de Rabbit Mq
Recherche de priorité de profondeur à l'aide de la pile en Python
Obtenez le chemin du fichier à l'aide de Pathlib
Trouvez la broche inertielle et le moment d'inertie principal à partir du tenseur inertiel avec NumPy
Comment connaître le nombre de processeurs sans utiliser la commande sar
Python> sys.path> Liste de chaînes indiquant le chemin pour rechercher des modules
J'ai essayé de trouver l'itinéraire optimal du pays des rêves par recuit (quantique)
Retrouvez les termes généraux de la séquence de Tribonacci en algèbre linéaire et Python
J'ai essayé d'extraire et d'illustrer l'étape de l'histoire à l'aide de COTOHA
Obtenez et estimez la forme de la tête en utilisant Dlib et OpenCV avec python
Trouvez le terme général de la séquence de Fibonacci étendue (séquence k-Bonatch: somme des k termes immédiatement précédents) en utilisant l'algèbre linéaire et Python