Python: j'ai essayé le problème du voyageur de commerce

Quel genre de problème était le [problème du vendeur circulaire](https://ja.wikipedia.org/wiki/Circuit Problème du vendeur)? Je l'ai essayé. seulement.

Résolution du problème du voyageur de commerce avec diverses solutions approximatives (1)

from itertools import permutations as IT_perm

total_cost = lambda costs : lambda seq : sum(
    costs[ seq[i - 1] ][ e ]
    for i, e in enumerate( seq )
)

head_fixed_permutations = lambda nodes : (
    nodes[ 0:1 ] + list( tail ) 
    for tail in IT_perm( nodes[ 1: ] )
)


costs = [
      [0, 6, 5, 5]
    , [6, 0, 7, 4]
    , [5, 7, 0, 3]
    , [5, 4, 3, 0]
    ]

nodes = [0, 1, 2, 3]

print(
    min(
        head_fixed_permutations( nodes )
        , key = total_cost( costs )
    )
)

#résultat:[0, 1, 3, 2]

Dans la liste des coûts, on suppose que le coût du déplacement du nœud a au nœud b est donné par le coût [a] [b]. nœuds est une liste des nœuds, le point de départ est fixé aux nœuds [0]: (la valeur est 0).

La façon dont j'y ai pensé était Dans l'ordre des nœuds à têtes fixes, Valeur à laquelle la fonction de calcul du coût total est appliquée. Le plus petit Production à propos de ça.

Je vois, c'est ce que c'est. C'était étonnamment simple.

Recommended Posts

Python: j'ai essayé le problème du voyageur de commerce
J'ai essayé de mettre en œuvre le problème du voyageur de commerce
J'ai essayé de résoudre le problème avec Python Vol.1
À propos du problème du vendeur de patrouille commandé
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 le problème du voyageur de commerce avec OR-Tools
J'ai essayé le framework de test Python Tornado
J'ai essayé Python> autopep8
J'ai essayé Python> décorateur
J'ai essayé de "lisser" l'image avec Python + OpenCV
[Python] J'ai essayé de remplacer le nom de la fonction par le nom de la fonction
vprof - J'ai essayé d'utiliser le profileur pour Python
J'ai essayé de "différencier" l'image avec Python + OpenCV
J'ai essayé de simuler "Birthday Paradox" avec Python
J'ai essayé la méthode des moindres carrés en Python
J'ai essayé la programmation python pour la première fois.
J'ai essayé d'utiliser le module Datetime de Python
J'ai essayé fp-growth avec python
J'ai essayé de gratter avec Python
J'ai essayé de représenter graphiquement les packages installés en Python
J'ai essayé Python sur Mac pour la première fois.
J'ai essayé de toucher un fichier CSV avec Python
J'ai essayé de résoudre Soma Cube avec python
J'ai essayé python pour la première fois avec heroku
J'ai essayé la bibliothèque changefinder!
J'ai essayé l'extension C de Python
J'ai essayé gRPC avec Python
J'ai essayé de gratter avec du python
J'ai téléchargé la source python
J'ai essayé de frapper l'API avec le client python d'echonest
J'ai essayé de résumer les opérations de chaîne de Python
Le 15e temps réel hors ligne, j'ai essayé de résoudre le problème de l'écriture avec python
J'ai essayé la "correction gamma" de l'image avec Python + OpenCV
J'ai essayé d'utiliser la bibliothèque Python de Ruby avec PyCall
J'ai essayé la reconnaissance faciale du problème du rire en utilisant Keras.
J'ai essayé de reconnaître le visage de la vidéo (OpenCV: version python)
J'ai essayé de programmer le test du chi carré en Python et Java.
[Python] J'ai essayé de visualiser la relation de suivi de Twitter
J'ai essayé d'implémenter la fonction d'envoi de courrier en Python
Notes diverses sur l'utilisation de python pour les projets
[Python] J'ai essayé de collecter des données en utilisant l'API de wikipedia
J'ai essayé d'énumérer les différences entre java et python
J'ai essayé de changer le script python de 2.7.11 à 3.6.0 sur Windows10
J'ai essayé le tutoriel TensorFlow 1er
J'ai essayé de toucher Python (installation)
Problème de méthode de gravure et de voyageur de commerce
J'ai essayé d'utiliser Thonny (Python / IDE)
J'ai essayé Grumpy (allez exécuter Python).
J'ai aimé le tweet avec python. ..
J'ai écrit la file d'attente en Python
J'ai essayé l'API du roman Naruro
J'ai essayé d'exécuter prolog avec python 3.8.2.
J'ai essayé la notification de ligne en Python
J'ai essayé la communication SMTP avec Python
J'ai essayé de déplacer le ballon
J'ai essayé d'utiliser l'API checkio
J'ai écrit la pile en Python
J'ai essayé d'estimer la section.