Résolvez le problème du voyageur de commerce asymétrique Python avec la méthode de branche et de liaison

[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.

problème

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]
    ]

répondre

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)

résultat

177.0
0 -> 6 -> 9 -> 3 -> 8 -> 2 -> 4 -> 7 -> 1 -> 5 -> 0

Recommended Posts

Résolvez le problème du voyageur de commerce asymétrique Python avec la méthode de branche et de liaison
Résolvez le problème du sac à dos Python avec la méthode de branche et liée
Résolvez le problème du voyageur de commerce avec OR-Tools
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (théorie)
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (résultat de l'exécution)
[AtCoder] Résoudre ABC1 ~ 100 Un problème avec Python
Je voulais résoudre le problème ABC164 A ~ D avec Python
Python: j'ai essayé le problème du voyageur de commerce
Résolvez les problèmes de somme partielle avec une recherche complète en Python
J'ai essayé "Implémentation d'un algorithme génétique (GA) en python pour résoudre le problème du voyageur de commerce (TSP)"
Résolvez un simple problème de voyageur de commerce à l'aide d'une machine Boltzmann avec recuit simulé
[AtCoder] Résoudre un problème de ABC101 ~ 169 avec Python
Résolution du problème du voyageur de commerce avec l'algorithme génétique (GA) et sa bibliothèque (vcopt)
Essayez de résoudre le problème d'affectation du médecin de formation avec Python
J'ai essayé de résoudre le problème avec Python Vol.1
Résolvez le livre en spirale (algorithme et structure de données) avec python!
Résoudre ABC163 A ~ C avec Python
Problème de méthode de gravure et de voyageur de commerce
Résoudre ABC166 A ~ D avec Python
À propos du problème du vendeur de patrouille commandé
Résoudre ABC168 A ~ C avec Python
Résoudre ABC162 A ~ C avec Python
Résoudre ABC167 A ~ C avec Python
Résoudre ABC158 A ~ C avec Python
Une histoire dans laquelle l'algorithme est arrivé à une conclusion ridicule en essayant de résoudre correctement le problème du voyageur de commerce
Calculer l'itinéraire le plus court d'un graphe avec la méthode Dyxtra et Python
Le 16ème comment écrire un problème de référence en temps réel hors ligne à résoudre avec Python
Un mémo contenant Python2.7 et Python3 dans CentOS
Rechercher le labyrinthe avec l'algorithme python A *
Hit une méthode d'une instance de classe avec l'API Web Python Bottle
Résoudre AtCoder ABC168 avec python (A ~ D)
Résolvez le problème maximum de sous-tableau en Python
Le 19ème comment écrire un problème de référence en temps réel hors ligne à résoudre avec Python
Essayez de résoudre un problème défini de mathématiques au lycée avec Python
Créons un système de réception simple avec le framework sans serveur Python Chalice et Twilio
Formulez un puzzle en forme de lien numérique comme problème de satisfaction de contraintes et résolvez-le avec un solveur de contraintes
Visualisez les données d'itinéraires ferroviaires et résolvez les problèmes d'itinéraires les plus courts (Python + Pandas + NetworkX)
Obtenez le cours de l'action d'une entreprise japonaise avec Python et faites un graphique
[Python] Récupérez les fichiers dans le dossier avec Python
Essayez de résoudre le problème de l'héritage de classe Python
Résoudre les problèmes de sac à dos à l'aide de pyomo et glpk
Essayez de résoudre le diagramme homme-machine avec Python
ffmpeg-Construisez un environnement python et divisez la vidéo
Résolvez A ~ D du codeur yuki 247 avec python
Lancer un serveur Web avec Python et Flask
Résolution du modèle Lorenz 96 avec Julia et Python
Archivez et compressez tout le répertoire avec python
Défiez AtCoder (ABC) 164 avec Python! Un problème ~ C
Prise en compte des forces et faiblesses de Python
J'ai essayé de mettre en œuvre le problème du voyageur de commerce
Résolvez le problème du sac à dos Python avec l'algorithme glouton
Automatisez la suppression de l'arrière-plan pour les derniers portraits dans un répertoire avec Python et API
Le 15e temps réel hors ligne, j'ai essayé de résoudre le problème de l'écriture avec python
Essayez de résoudre le livre des défis de programmation avec python3
Détruire l'expression intermédiaire de la méthode sweep avec Python
J'ai essayé de résoudre Soma Cube avec python
Essayez de créer un jeu simple avec Python 3 et iPhone
Visualisez la gamme d'insertions internes et externes avec python
Résolvez des équations différentielles normales simultanées avec Python et SymPy.
Faire un point d'arrêt sur la couche c avec python