[Problème de vendeur circulaire (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) [Méthode de limitation de branche (Wikipedia)](https: // ja. wikipedia.org/wiki/%E5%88%86%E6%9E%9D%E9%99%90%E5%AE%9A%E6%B3%95). L'autre jour [Problème de sac à dos (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) a été résolu par la méthode de limitation de branche. Résolution du problème du sac à dos Python avec la méthode de branchement et de liaison
Lorsque la distance (coût) de la ville donnée i à la ville j est donnée, il fait le tour de toutes les villes une fois et trouve l'itinéraire qui minimise le coût.
Nous vous serions reconnaissants si vous pouviez nous faire savoir s'il y a des lacunes ou des suggestions d'amélioration concernant le code.
Ici, la distance (coût) de la ville i à la ville j est prise comme exemple du problème suivant. Le nombre de villes (nœuds) est de 10. La distance (coût) de la ville i à la ville i est infinie. Créez un programme qui résout le problème du voyageur de commerce exprimé de cette manière par la méthode de limitation de branche.
[
[ 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 = [] #Un groupe de nœuds empilés avec des solutions aux problèmes d'atténuation
self.present_nodes = [] #Le nœud que vous recherchez(1 ou 2)
self.suitable_val = math.inf #Valeur provisoire
self.suitable_ans = [] #Solution provisoire
self.node_num = self.route_df.shape[0] #Nombre de nœuds
#La valeur minimale du DataFrame donné[index, column]Renvoyer une paire
def __minimumRoute(self, target_route_df):
min_index = target_route_df.idxmin(axis=1) #Colonne minimum pour chaque ligne
minimum = math.inf #Valeur initiale de la valeur minimale
loc = [-1, -1] #Valeur initiale de la position
for index, column in zip(min_index.index, min_index.values):
if math.isnan(column): #NaN lorsque toutes les lignes sont inf,Ce n'est pas le minimum
continue
if minimum > target_route_df[column][index]:
minimum = target_route_df[column][index] #Mise à jour de la valeur minimale
loc = [index, column] # index,Mettre à jour la position de la colonne
return loc
#Renvoie la valeur optimale en fonction du DataFrame par défaut et d'un tableau de sélections d'itinéraire
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: #Lors de la sélection de cet itinéraire
route_length += route_df_tmp[route[1]][route[0]] #Ajouté à la longueur de l'itinéraire
if (route[1] in route_df_tmp.index and route[0] in route_df_tmp.columns): #Lorsque l'élément correspondant existe toujours dans le DataFrame du chemin réduit
route_df_tmp[route[0]][route[1]] = math.inf # DataFrame[column][index],Itinéraire inverse de la route correspondante(1->Quand 2->1)Ne sera pas adopté, donc inf
route_df_tmp = route_df_tmp.drop(route[0], axis=0) #Supprimer la ligne de l'itinéraire correspondant
route_df_tmp = route_df_tmp.drop(route[1], axis=1) #Supprimer la colonne de l'itinéraire correspondant
else: #Lorsque vous ne sélectionnez pas cet itinéraire
if (route[0] in route_df_tmp.index and route[1] in route_df_tmp.columns): #Lorsque l'élément correspondant existe toujours dans le DataFrame du chemin réduit
route_df_tmp[route[1]][route[0]] = math.inf #Puisqu'il n'est pas adopté, laissez la route correspondante être inf
min_sum = 0 #Ajouter les longueurs de chemin des problèmes d'atténuation
next_route = copy.deepcopy(route_df_tmp) #DataFrame à ce stade est le suivant_Rester en route
for index in route_df_tmp.index: #Courir sur chaque ligne
min_tmp = route_df_tmp.ix[index, :].min() #Obtenez la valeur minimale d'une ligne
min_sum += min_tmp #Ajouter la valeur minimale
route_df_tmp.ix[index, :] = route_df_tmp.ix[index, :] - min_tmp #Soustrayez la valeur minimale de chaque élément de la ligne
for column in route_df_tmp.columns: #Exécuter sur chaque colonne
min_tmp = route_df_tmp.ix[:, column].min() #Obtenir le minimum de colonne
min_sum += min_tmp #Ajouter la valeur minimale
route_df_tmp.ix[:, column] = route_df_tmp.ix[:, column] - min_tmp #Soustrayez la valeur minimale de chaque élément de cette colonne
route_length += min_sum #Ajouté à la longueur de l'itinéraire
return route_length, next_route #DataFrame de la longueur de la route et de la route au moment du nœud
#Vérifiez si la route est fermée
def __checkClosedCircle(self, route_list, route_df_tmp):
# route_df_En supposant que tmp est 2x2
mini_route = self.__minimumRoute(route_df_tmp) # route_df_Du plus petit élément de tmp[index, coumn]
if mini_route == [-1, -1]: #route_df_Quand tous les tmp sont inf
return False
mini_route.append(0) #Ajouter 0 car c'est la route à adopter
route_list.append(mini_route) #Ajouter à la liste des itinéraires
route_df_tmp = route_df_tmp.drop(mini_route[0], axis=0) #Supprimer la ligne
route_df_tmp = route_df_tmp.drop(mini_route[1], axis=1) #Supprimer la colonne
last_route = [route_df_tmp.index[0], route_df_tmp.columns[0]] #Obtenez le reste des éléments
last_route.append(0) #Ajouter 0 car c'est la route à adopter
route_list.append(last_route) #Ajouter à la liste des itinéraires
label, counter = 0, 0 #label est la position actuelle,compteur est le nombre de coups
for i in range(self.node_num): #Nombre maximum d'itérations
for route in route_list:
if route[0] == label and route[2] == 0: #Si le point de départ est l'étiquette et l'itinéraire adopté
new_label = route[1] #Mettre à jour l'étiquette
counter += 1 #incrément du compteur
label = new_label
if label == 0: #Si l'étiquette est 0, le tour est terminé
break
if counter == self.node_num: #Si le nombre de mouvements correspond au nombre de nœuds, un tour fermé
return True
else:
return False
#Ajouter une nouvelle route à la route vers un certain nœud et présenter_Ajouter aux nœuds
def __setPresentNodes(self, target_route, target_branch):
for status in range(2):
target_route_tmp = copy.deepcopy(target_route) # target_Copier ele
target_route_tmp.append(status) # status(Approbation) ajouté
target_branch_tmp = copy.deepcopy(target_branch) # target_Copier la branche
target_branch_tmp.append(target_route_tmp) #Ajouter un itinéraire
self.present_nodes.append(target_branch_tmp) # present_Ajouté aux nœuds
#Évaluer le nœud correspondant,Évaluer le nœud si le branchement est possible,Si la branche se termine, comparez avec la valeur provisoire
def __evaluateNode(self, target_node):
if (False if target_node[1].shape == (2, 2) else True): #Quand tu peux encore créer une branche,Le jugement est la cible_DataFrame du nœud n'a pas atteint 2x2
next_route = self.__minimumRoute(target_node[1]) #Obtenez le plus petit élément[index, column]
if next_route != [-1, -1]: # [-1, -1]Dans le cas de, la distance devient inf, donc elle ne convient pas, present_N'ajoutez rien aux nœuds
self.__setPresentNodes(next_route, target_node[0])
else: #Au bout de la branche
if self.__checkClosedCircle(target_node[0], target_node[1]): #Est-ce une route fermée?
if self.suitable_val > target_node[2]: #Est-elle inférieure à la valeur provisoire?
self.suitable_val = target_node[2] #Mise à jour de la valeur provisoire
self.suitable_ans = target_node[0] #Mise à jour de la solution provisoire
#Convertir une liste d'itinéraires en chemin
def __displayRoutePath(self, route_list):
label, counter, route_path = 0, 0, "0" #label est la position actuelle,compteur est le nombre de coups, route_le chemin est la route
for i in range(self.node_num): #Nombre maximum d'itérations
for route in route_list:
if route[0] == label and route[2] == 0: #Si le point de départ est l'étiquette et l'itinéraire adopté
new_label = route[1] #Mettre à jour l'étiquette
route_path += " -> " + str(new_label)
counter += 1 #incrément du compteur
label = new_label
if label == 0: #Si l'étiquette est 0, le tour est terminé
break
return route_path
#Calculez la valeur optimale et la solution optimale(Méthode principale)
def getSuitableAns(self):
target_route = self.__minimumRoute(self.route_df) #Obtenez le plus petit élément de l'itinéraire DataFrame
self.__setPresentNodes(target_route, []) # present_Définir sur les nœuds
while True:
if self.suitable_val != math.inf: #Lorsque la valeur provisoire de la solution optimale est fixée
self.stack_search_nodes = list(filter(lambda node: node[2] < self.suitable_val, self.stack_search_nodes)) #Exclure si la solution du problème d'atténuation des nœuds empilés dépasse la valeur provisoire
while len(self.present_nodes) != 0: #S'il existe une liste de recherches, demandez la solution du problème d'atténuation et empilez
first_list = self.present_nodes[0] # present_Évaluer les nœuds
self.present_nodes.pop(0) #Je vais l'évaluer si présent_Exclure des nœuds
route_length, next_route = self.__calcSuitableSum(first_list) #Obtenez la solution au problème d'atténuation
self.stack_search_nodes.insert(0, [first_list, next_route, route_length]) #empiler
if len(self.stack_search_nodes) == 0: #Quitter quand il n'y a plus de piles
break;
#Lorsque le nombre de nœuds empilés est de 1, ou lorsque la solution du premier problème d'atténuation des nœuds empilés est inférieure à la solution du deuxième problème d'atténuation(Pour confirmer de la solution qui semble être bonne)
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]) #Évaluer le premier nœud
self.stack_search_nodes.pop(0) #Supprimer le premier nœud
else:
self.__evaluateNode(self.stack_search_nodes[1]) #Évaluer le deuxième nœud
self.stack_search_nodes.pop(1) #Supprimer le deuxième nœud
return self.suitable_val, self.__displayRoutePath(self.suitable_ans) #Renvoie la valeur optimale et l'itinéraire optimal
#Liste des routes problématiques
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]
]
#Instancier et utiliser la méthode
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