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