[PYTHON] Finden Sie den kritischen Pfad von PERT mithilfe der Breitenprioritätssuche und der Tiefenprioritätssuche
Hintergrund
Atcoder hat aufgehört, sich von Braun zu bewegen Ich begann ernsthaft Algorithmen zu studieren. Jetzt, da ich ein wenig Verständnis für die Breitenprioritätssuche (BFS) und die Tiefenprioritätssuche (DFS) habe Zur Überprüfung werden Fragen auch in den Prüfungsfragen des Basic Information Engineer gestellt. Die früheste Verbindungspunktzeit, die späteste Verbindungspunktzeit und der kritische Pfad in PERT Ich beschloss zu fragen.
Zweck
Durch Eingabe der Informationen des Diagramms in PERT ・ Der früheste Verbindungszeitpunkt ・ Die späteste Verbindungszeit · Kritischer Pfad Implementieren Sie ein Programm, das berechnet.
Informationen zur Breitenprioritätssuche (BFS) und Tiefenprioritätssuche (DFS)
@ drkens Artikel war sehr leicht zu verstehen.
・ DFS (Depth Priority Search) Super Einführung! ~ Einstieg in die Welt der Graph-Algorithmen ~ [Teil 1] ・ DFS (Depth Priority Search) Super Einführung! ~ Einstieg in die Welt der Graph-Algorithmen ~ [Teil 2] ・ BFS (Width Priority Search) Super Einführung! ~ Verwenden Sie die Warteschlange lebhaft ~
Über PERT
Durch Anzeigen der Arbeitsreihenfolge und der Abhängigkeiten im Pfeildiagramm Es ist eine Methode, um die kürzeste Zeit, die für die Fertigstellung des Projekts erforderlich ist, und die wichtigsten Managementarbeiten zu klären. Bitte lesen Sie den Artikel von @sakamoto_t. ・ Was ist PSP?
Beispiel
Das folgende Pfeildiagramm dient als Beispiel.
Implementierungscode
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]
#-------------Ausgabeteil-----------------
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
#---------------Eingabeteil--------------------
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
#---------------Diagrammerstellung-------------------
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]Wirft weg((Da die Scheitelpunktnummer beim Erstellen der Diagrammstruktur von 1 übernommen wird)
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])) #Erstellen eines umgekehrten Diagramms
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
#------------BFS-Arbeitsteil(Finde die Verbindungszeit nicht mehr)------------------
def bfs_normal(node_num, start, Graph, need_day):
stack = deque([start])
earliest_node_time = [0 for i in range(node_num)]
while stack: #Fahren Sie fort, bis der Stapel leer ist
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
#------------BFS-Arbeitsteil(Finde den letzten Verbindungszeitpunkt)------------------
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: #Fahren Sie fort, bis der Stapel leer ist
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 =Extrahieren Sie die Punkte, die zu TL werden-------------------
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
#--------------DFS-Arbeitsteil (Verfolgung der Kandidatenpunkte des kritischen Pfades und Suche zum Ziel)-----------
def check_critical_path(start, goal, candidate, Graph_critical):
stack = [start]
seen = deque([start])
while stack: #Fahren Sie fort, bis der Stapel leer ist
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())
Eingang
Der Knoten am Anfang der Arbeit ist 1, und der Knoten am Ende der Arbeit ist der Maximalwert des Knotens (= node_num). $ N $: Anzahl der Zustände (node_num) $ P $: Anzahl der Arbeiten (path_num) $ {s_i, g_i, K_i} $: Status vor der Arbeit, Status nach der Arbeit, erforderliche Tage Wie
Im obigen Beispielbild
Wird sein.
Ausgabe
------------------
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
Dies wird unten erklärt.
Zerlegung von Themen
Den kritischen Pfad finden
- Finden Sie den frühesten Verbindungszeitpunkt (im Folgenden EL)
- Ermitteln Sie die letzte Verbindungszeit (TL).
- Extrahieren Sie Kandidaten, die kritische Pfadknoten sein können, mit EL = TL Erhalten Sie ein Beispiel für einen kritischen Pfad, indem Sie eine Tiefenprioritätssuche unter der Bedingung durchführen, dass der Kandidatenknoten von 4.3 durchlaufen wird
Ich habe über die Implementierung in 4 Schritten nachgedacht. Ich werde jeden von ihnen erklären.
Erstellen Sie ein Diagramm
Beim Ermitteln der letzten Verbindungspunktzeit wird die Anzahl der für jede Arbeit erforderlichen Tage aus den Informationen der frühesten Verbindungspunktzeit jedes Knotens berechnet. Es war notwendig, die Pfeile in der Grafik in die entgegengesetzte Richtung zu bewegen, da wir ziehen und vergleichen würden. Erstellen Sie daher beim Erstellen des Diagramms gleichzeitig ein Diagramm mit der entgegengesetzten Fahrtrichtung. Ich beschloss, die Anzahl der Arbeitstage in Form einer Matrix zu formulieren und die Informationen gleichzeitig in die entgegengesetzte Richtung zu speichern.
#---------------Diagrammerstellung-------------------
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]Wirft weg((Da die Scheitelpunktnummer beim Erstellen der Diagrammstruktur von 1 übernommen wird)
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])) #Erstellen eines umgekehrten Diagramms
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.]]
"""
Finden Sie den frühesten Verbindungszeitpunkt (im Folgenden ET)
Dieses Problem wird durch das ** Problem der Auswahl des Pfades ersetzt, der die Summe der ** Seitengewichte auf jedem Knoten maximiert. Im Gegenteil, die ** Dyxtra-Methode ** ist als Pfadproblem bekannt, das das Gewicht minimiert. Dieses Mal habe ich es mit dieser Idee umgesetzt.
#------------BFS-Arbeitsteil(Finde die Verbindungszeit nicht mehr)------------------
def bfs_normal(start):
stack = deque([start])
while stack: #Fahren Sie fort, bis der Stapel leer ist
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
Die Suche nach Breitenprioritäten wird durchgeführt, und Earliest_node_time wird durch Hinzufügen der Anzahl der Arbeitstage aktualisiert. Wenn mehrere Routen vorhanden sind, aktualisieren Sie diese, wenn sie größer als der vorhandene Wert sind.
Finden Sie die letzte Verbindungszeit (LT)
Als nächstes finden Sie den LT. Zu diesem Zeitpunkt ist der Anfangswert als Latest_node_time unendlich. Bereiten Sie ein Array vor und aktualisieren Sie es auf das kleinere.
#------------BFS-Arbeitsteil(Finde den letzten Verbindungszeitpunkt)------------------
def bfs_reverse(goal):
stack = deque([goal])
latest_node_time[goal-1] = earliest_node_time[goal-1]
while stack: #Fahren Sie fort, bis der Stapel leer ist
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
Finden Sie den kritischen Pfad
Der kritische Pfad wird durch Verbinden von Knoten mit EL = TL hergestellt. Umgekehrt müssen Sie den Knoten folgen, die EL = TL erfüllen, um das Ziel zu erreichen ** Vorbehaltlich des Durchlaufens von Kandidatenknoten mit EL = TL Ich habe eine Tiefenprioritätssuche durchgeführt und von Anfang an ein Problem mit der Zielankunft gefunden. ** ** **
Extrahieren Sie Kandidatenknoten mit EL = TL, indem Sie jedes Element vergleichen.
#--------------EL =Extrahieren Sie die Punkte, die zu TL werden-------------------
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
Schließlich bestimmt die DFS, ob Sie das Ziel erreichen können. Bestimmen Sie, ob Sie zu den Kandidaten gehören, wenn Sie jeden Knoten erreichen. Es endet, wenn Sie das Ziel erreichen. Wenn Sie also mehrere kritische Durchgänge haben Zeigen Sie eine davon an.
#--------------DFS-Arbeitsteil (Verfolgung von Kandidatenpunkten auf dem kritischen Pfad und Suche zum Ziel)-----------
def check_critical_path(start, goal, candidate, Graph_critical):
stack = [start]
seen = deque([start])
while stack: #Fahren Sie fort, bis der Stapel leer ist
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
Hauptfunktionsteil
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]
#-------------Ausgabeteil-----------------
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
Ich möchte es etwas schöner schreiben Ich hatte nicht genug Wissen. Ich werde es eines Tages verbessern.
Zusammenfassung
・ Um die Verbindungspunktzeit nicht mehr zu erhalten, das gewichtete gerichtete Diagramm Es kann als ein Problem gelöst werden, das den Gesamtgewichtswert ** maximiert. (Siehe Idee der Dyxtra-Methode) ・ Es ist notwendig, DFS und BFS zu kombinieren, um den kritischen Pfad zu bestimmen (?) → Ich würde gerne wissen, ob es einen besseren Weg gibt.
Impressionen
Ich habe zum ersten Mal einen Artikel über Qiita geschrieben, daher bin ich froh, dass ich das Schreiben von Artikeln üben konnte. Ich möchte positiv schreiben und meine Gedanken organisieren.
andere Referenzen
Für die Implementierung von BFS mit Python habe ich auf den folgenden Artikel von @ takayg1 verwiesen. ・ Algorithmus in Python (Suche nach Tiefenpriorität, dfs)
Recommended Posts