Was für ein Problem war das [Circular Salesman Problem](https://ja.wikipedia.org/wiki/Circuit Salesman Problem)? Ich versuchte es. nur.
Lösung des Problems des Handlungsreisenden mit verschiedenen Näherungslösungen (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 )
)
)
#Ergebnis:[0, 1, 3, 2]
In den Listenkosten wird angenommen, dass die Kosten für den Wechsel von Knoten a zu Knoten b durch die Kosten [a] [b] gegeben sind. Knoten ist eine Liste der Knoten, der Startpunkt ist auf Knoten [0] festgelegt: (Wert ist 0).
So wie ich darüber dachte In der Reihenfolge der Knoten mit festen Köpfen, Der Wert, auf den die Funktion zur Berechnung der Gesamtkosten angewendet wird. Der kleinste Ausgabe darüber.
Ich verstehe, das ist es. Es war überraschend einfach.
Recommended Posts