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.
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
Dans l'exemple d'image ci-dessus
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
- Trouvez l'heure du point de connexion le plus ancien (ci-après EL)
- Trouvez la dernière heure du point de connexion (TL)
- 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