[Circular Salesman Problem (Wikipedia)](https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3%83 % AB% E3% 82% B9% E3% 83% 9E% E3% 83% B3% E5% 95% 8F% E9% A1% 8C) [Branch Limitation Method (Wikipedia)](https: // ja. wikipedia.org/wiki/%E5%88%86%E6%9E%9D%E9%99%90%E5%AE%9A%E6%B3%95). Neulich [Rucksackproblem (Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83 % 83% E3% 82% AF% E5% 95% 8F% E9% A1% 8C) wurde durch das Verzweigungsbegrenzungsverfahren gelöst. Lösen des Python-Rucksackproblems mit der Verzweigungs- und gebundenen Methode
Wenn die Entfernung (Kosten) von der gegebenen Stadt i zur Stadt j angegeben ist, werden alle Städte einmal umrundet und die Route gefunden, die die Kosten minimiert.
Wir würden uns freuen, wenn Sie uns mitteilen könnten, ob es Mängel oder Verbesserungsvorschläge bezüglich des Codes gibt.
Hier wird die Entfernung (Kosten) von Stadt i zu Stadt j als Beispiel für das folgende Problem genommen. Die Anzahl der Städte (Knoten) beträgt 10. Die Entfernung (Kosten) von Stadt i zu Stadt i ist unendlich. Erstellen Sie ein Programm, das das Problem des Handlungsreisenden löst, das auf diese Weise durch die Filialbegrenzungsmethode ausgedrückt wird.
[
[ math.inf, 22, 16, 21, 19, 24, 17, 21, 30, 29],
[ 16, math.inf, 16, 29, 16, 20, 20, 24, 26, 19],
[ 19, 27, math.inf, 22, 18, 20, 30, 26, 21, 27],
[ 28, 29, 24, math.inf, 28, 26, 18, 17, 16, 21],
[ 18, 26, 24, 21, math.inf, 26, 20, 19, 24, 20],
[ 16, 22, 26, 25, 26, math.inf, 26, 30, 28, 27],
[ 17, 20, 18, 20, 30, 28, math.inf, 30, 29, 16],
[ 24, 19, 16, 20, 19, 30, 23, math.inf, 22, 22],
[ 26, 29, 18, 22, 21, 20, 30, 22, math.inf, 17],
[ 19, 28, 29, 18, 23, 23, 30, 28, 21, math.inf]
]
import numpy as np
from pandas import DataFrame
import math
import copy
class Salesman():
def __init__(self, route_list):
self.route_df = DataFrame(route_list)
self.stack_search_nodes = [] #Eine Gruppe von Knoten, die mit Lösungen für Schadensbegrenzungsprobleme gestapelt sind
self.present_nodes = [] #Der Knoten, nach dem Sie suchen(1 oder 2)
self.suitable_val = math.inf #Vorläufiger Wert
self.suitable_ans = [] #Vorläufige Lösung
self.node_num = self.route_df.shape[0] #Anzahl der Knoten
#Der Mindestwert des angegebenen DataFrame[index, column]Gib ein Paar zurück
def __minimumRoute(self, target_route_df):
min_index = target_route_df.idxmin(axis=1) #Minimale Spalte für jede Zeile
minimum = math.inf #Anfangswert des Mindestwertes
loc = [-1, -1] #Anfangswert der Position
for index, column in zip(min_index.index, min_index.values):
if math.isnan(column): #NaN wenn alle Zeilen inf sind,Dies ist nicht das Minimum
continue
if minimum > target_route_df[column][index]:
minimum = target_route_df[column][index] #Aktualisierung des Mindestwerts
loc = [index, column] # index,Spaltenposition aktualisieren
return loc
#Gibt den optimalen Wert für den Standard-DataFrame und das Routenauswahlarray zurück
def __calcSuitableSum(self, route_list):
route_df_tmp = copy.deepcopy(self.route_df)
route_length = 0
for route in route_list:
if route[2] == 0: #Bei der Auswahl dieser Route
route_length += route_df_tmp[route[1]][route[0]] #Zur Routenlänge hinzugefügt
if (route[1] in route_df_tmp.index and route[0] in route_df_tmp.columns): #Wenn das entsprechende Element noch im DataFrame des reduzierten Pfads vorhanden ist
route_df_tmp[route[0]][route[1]] = math.inf # DataFrame[column][index],Umgekehrte Route der entsprechenden Straße(1->Wenn 2 2->1)Wird nicht adoptiert, also inf
route_df_tmp = route_df_tmp.drop(route[0], axis=0) #Zeile der entsprechenden Route löschen
route_df_tmp = route_df_tmp.drop(route[1], axis=1) #Spalte der entsprechenden Route löschen
else: #Wenn Sie diese Route nicht auswählen
if (route[0] in route_df_tmp.index and route[1] in route_df_tmp.columns): #Wenn das entsprechende Element noch im DataFrame des reduzierten Pfads vorhanden ist
route_df_tmp[route[1]][route[0]] = math.inf #Da es nicht übernommen wird, sei die entsprechende Route inf
min_sum = 0 #Fügen Sie die Pfadlängen von Schadensbegrenzungsproblemen hinzu
next_route = copy.deepcopy(route_df_tmp) #DataFrame an dieser Stelle ist der nächste_Auf dem Weg bleiben
for index in route_df_tmp.index: #In jeder Zeile ausführen
min_tmp = route_df_tmp.ix[index, :].min() #Ermitteln Sie den Mindestwert einer Zeile
min_sum += min_tmp #Fügen Sie den Mindestwert hinzu
route_df_tmp.ix[index, :] = route_df_tmp.ix[index, :] - min_tmp #Subtrahieren Sie den Mindestwert von jedem Element in der Zeile
for column in route_df_tmp.columns: #Führen Sie jede Spalte aus
min_tmp = route_df_tmp.ix[:, column].min() #Spaltenminimum abrufen
min_sum += min_tmp #Fügen Sie den Mindestwert hinzu
route_df_tmp.ix[:, column] = route_df_tmp.ix[:, column] - min_tmp #Subtrahieren Sie den Mindestwert von jedem Element in dieser Spalte
route_length += min_sum #Zur Routenlänge hinzugefügt
return route_length, next_route #DataFrame der Routenlänge und der Route zum Zeitpunkt des Knotens
#Überprüfen Sie, ob die Straße gesperrt ist
def __checkClosedCircle(self, route_list, route_df_tmp):
# route_df_Angenommen, tmp ist 2x2
mini_route = self.__minimumRoute(route_df_tmp) # route_df_Vom kleinsten Element von tmp[index, coumn]
if mini_route == [-1, -1]: #route_df_Wenn alle tmp inf sind
return False
mini_route.append(0) #Fügen Sie 0 hinzu, da dies die zu übernehmende Route ist
route_list.append(mini_route) #Zur Routenliste hinzufügen
route_df_tmp = route_df_tmp.drop(mini_route[0], axis=0) #Zeile löschen
route_df_tmp = route_df_tmp.drop(mini_route[1], axis=1) #Spalte löschen
last_route = [route_df_tmp.index[0], route_df_tmp.columns[0]] #Holen Sie sich den Rest der Elemente
last_route.append(0) #Fügen Sie 0 hinzu, da dies die zu übernehmende Route ist
route_list.append(last_route) #Zur Routenliste hinzufügen
label, counter = 0, 0 #label ist die aktuelle Position,Zähler ist die Anzahl der Züge
for i in range(self.node_num): #Maximale Anzahl von Iterationen
for route in route_list:
if route[0] == label and route[2] == 0: #Wenn der Startpunkt die Beschriftung und die angenommene Route ist
new_label = route[1] #Etikett aktualisieren
counter += 1 #Zählerinkrement
label = new_label
if label == 0: #Wenn label 0 ist, ist die Runde beendet
break
if counter == self.node_num: #Wenn die Anzahl der Bewegungen mit der Anzahl der Knoten übereinstimmt, wird eine Runde geschlossen
return True
else:
return False
#Fügen Sie der Route zu einem bestimmten Knoten eine neue Route hinzu und präsentieren Sie diese_Zu Knoten hinzufügen
def __setPresentNodes(self, target_route, target_branch):
for status in range(2):
target_route_tmp = copy.deepcopy(target_route) # target_Kopieren Sie ele
target_route_tmp.append(status) # status(Genehmigung) hinzugefügt
target_branch_tmp = copy.deepcopy(target_branch) # target_Zweig kopieren
target_branch_tmp.append(target_route_tmp) #Route hinzufügen
self.present_nodes.append(target_branch_tmp) # present_Zu Knoten hinzugefügt
#Bewerten Sie den entsprechenden Knoten,Bewerten Sie den Knoten, wenn eine Verzweigung möglich ist,Wenn die Verzweigung endet, vergleichen Sie sie mit dem vorläufigen Wert
def __evaluateNode(self, target_node):
if (False if target_node[1].shape == (2, 2) else True): #Wenn Sie noch verzweigen können,Das Urteil ist das Ziel_Der Datenrahmen des Knotens hat 2x2 nicht erreicht
next_route = self.__minimumRoute(target_node[1]) #Holen Sie sich das kleinste Element[index, column]
if next_route != [-1, -1]: # [-1, -1]Im Fall von wird der Abstand inf, so dass er nicht geeignet ist, present_Fügen Sie den Knoten nichts hinzu
self.__setPresentNodes(next_route, target_node[0])
else: #Am Ende der Niederlassung
if self.__checkClosedCircle(target_node[0], target_node[1]): #Ist es eine gesperrte Straße?
if self.suitable_val > target_node[2]: #Ist es kleiner als der vorläufige Wert?
self.suitable_val = target_node[2] #Aktualisierung des vorläufigen Wertes
self.suitable_ans = target_node[0] #Aktualisierung der vorläufigen Lösung
#Konvertieren Sie eine Liste von Routen in einen Pfad
def __displayRoutePath(self, route_list):
label, counter, route_path = 0, 0, "0" #label ist die aktuelle Position,Zähler ist die Anzahl der Züge, route_Pfad ist die Route
for i in range(self.node_num): #Maximale Anzahl von Iterationen
for route in route_list:
if route[0] == label and route[2] == 0: #Wenn der Startpunkt die Beschriftung und die angenommene Route ist
new_label = route[1] #Etikett aktualisieren
route_path += " -> " + str(new_label)
counter += 1 #Zählerinkrement
label = new_label
if label == 0: #Wenn label 0 ist, ist die Runde beendet
break
return route_path
#Berechnen Sie den optimalen Wert und die optimale Lösung(Hauptmethode)
def getSuitableAns(self):
target_route = self.__minimumRoute(self.route_df) #Holen Sie sich das minimale Element der Route DataFrame
self.__setPresentNodes(target_route, []) # present_Auf Knoten setzen
while True:
if self.suitable_val != math.inf: #Wenn der vorläufige Wert der optimalen Lösung festgelegt ist
self.stack_search_nodes = list(filter(lambda node: node[2] < self.suitable_val, self.stack_search_nodes)) #Ausschließen, wenn die Lösung des Relaxationsproblems der gestapelten Knoten den vorläufigen Wert überschreitet
while len(self.present_nodes) != 0: #Wenn eine Liste mit Suchvorgängen vorhanden ist, fragen Sie nach der Lösung des Schadensbegrenzungsproblems und stapeln Sie sie
first_list = self.present_nodes[0] # present_Holen Sie sich Knoten zu bewerten
self.present_nodes.pop(0) #Ich werde es so präsent bewerten_Von Knoten ausschließen
route_length, next_route = self.__calcSuitableSum(first_list) #Holen Sie sich die Lösung für das Schadensbegrenzungsproblem
self.stack_search_nodes.insert(0, [first_list, next_route, route_length]) #Stapel
if len(self.stack_search_nodes) == 0: #Beenden Sie das Programm, wenn keine Stapel mehr vorhanden sind
break;
#Wenn die Anzahl der gestapelten Knoten 1 ist oder wenn die Lösung des ersten Minderungsproblems der gestapelten Knoten kleiner ist als die Lösung des zweiten Minderungsproblems(Aus der Lösung zu bestätigen, die gut zu sein scheint)
if len(self.stack_search_nodes) == 1 or self.stack_search_nodes[0][2] <= self.stack_search_nodes[1][2]:
self.__evaluateNode(self.stack_search_nodes[0]) #Bewerten Sie den ersten Knoten
self.stack_search_nodes.pop(0) #Löschen Sie den ersten Knoten
else:
self.__evaluateNode(self.stack_search_nodes[1]) #Bewerten Sie den zweiten Knoten
self.stack_search_nodes.pop(1) #Löschen Sie den zweiten Knoten
return self.suitable_val, self.__displayRoutePath(self.suitable_ans) #Gibt den optimalen Wert und die optimale Route zurück
#Liste der Problemrouten
route_list = [
[ math.inf, 22, 16, 21, 19, 24, 17, 21, 30, 29],
[ 16, math.inf, 16, 29, 16, 20, 20, 24, 26, 19],
[ 19, 27, math.inf, 22, 18, 20, 30, 26, 21, 27],
[ 28, 29, 24, math.inf, 28, 26, 18, 17, 16, 21],
[ 18, 26, 24, 21, math.inf, 26, 20, 19, 24, 20],
[ 16, 22, 26, 25, 26, math.inf, 26, 30, 28, 27],
[ 17, 20, 18, 20, 30, 28, math.inf, 30, 29, 16],
[ 24, 19, 16, 20, 19, 30, 23, math.inf, 22, 22],
[ 26, 29, 18, 22, 21, 20, 30, 22, math.inf, 17],
[ 19, 28, 29, 18, 23, 23, 30, 28, 21, math.inf]
]
#Methode instanziieren und anwenden
salesman = Salesman(route_list)
suitable_val, suitable_route = salesman.getSuitableAns()
print(suitable_val)
print(suitable_route)
177.0
0 -> 6 -> 9 -> 3 -> 8 -> 2 -> 4 -> 7 -> 1 -> 5 -> 0
Recommended Posts