Sie erhalten eine Liste, einen Vektor oder was auch immer, ein Bündel von 3-Tupeln oder was auch immer, wobei die ersten beiden Dinge Zeichenfolgen sind und das dritte eine Zahl. Die Zeichenfolgen sind Städte, und die Zahl gibt die Entfernung zwischen ihnen an. Die Reihenfolge der Städte im Tupel ist willkürlich (dh es spielt keine Rolle, welche zuerst und welche dann an zweiter Stelle kommt), da die Entfernung in jeder Richtung gleich ist. Außerdem gibt es genau ein Tupel für jedes Paar verbundener Städte. Möglicherweise sind nicht alle Städte verbunden. Auch der Abstand ist immer positiv (nicht0). Sie brauchen diese Bedingungen nicht zu überprüfen, Sie können davon ausgehen, dass die Eingabe korrekt ist. Ihre Aufgabe ist es, die Städte in einer zyklischen Reihenfolge zurückzugeben, sodass, wenn Sie an einer beliebigen Stadt beginnen und die Reihenfolge bis zu derselben Stadt wiederholen, die Gesamtentfernung zwischen den Städten minimal ist (genau und insgesamt) Fälle.) Sie können davon ausgehen, dass eine Lösung existiert. Nehmen wir zum Beispiel an, Sie sind gegeben

[("New York", "Detroit", 2.2), ("New York", "Dillsburg", 3.7), ("Hong Kong", "Dillsburg", 4), ("Hong Kong", "Detroit", 4), ("Dillsburg", "Detroit", 9000.1), ("New York", "Hong Kong", 9000.01)]

Sie können Folgendes ausgeben (aber Sie müssen nur eines ausgeben):

["Detroit","Hong Kong","Dillsburg","New York"]
["Hong Kong","Dillsburg","New York","Detroit"]
["Dillsburg","New York","Detroit","Hong Kong"]
["New York","Detroit","Hong Kong","Dillsburg"]
["Dillsburg","Hong Kong","Detroit","New York"]
["New York","Dillsburg","Hong Kong","Detroit"]
["Detroit","New York","Dillsburg","Hong Kong"]
["Hong Kong","Detroit","New York","Dillsburg"]

weil es die kürzeste fahrt ist: 13.9

aber nicht

["Dillburg","Detroit","New York","Hong Kong"]

weil es nicht das kürzeste ist.

Siehe en.wikipedia.org/wiki/Travelling_salesman_problem

Wertung

Hier wird es interessant. Sie nehmen die Anzahl der Zeichen, die Sie haben, und stecken sie dann in die O-Notationsformel für den schlimmsten Fall. Angenommen, Sie schreiben ein Brute-Force-Programm mit 42 Zeichen. Wie wir alle wissen, ist der schlimmste Fall , n!wo ndie Zahl der Städte ist. 42! = 1405006117752879898543142606244511569936384000000000, das ist also Ihre Punktzahl. Die niedrigste Punktzahl gewinnt .

Hinweis: Ich habe das später auch gelindert, war mir aber nicht sicher, wie ich es lösen sollte, und hoffte, dass es niemand bemerken würde. Die Leute taten es, also werde ich mit issacgs Vorschlag weitermachen:

Die einzigen Optionen sind O (n!) und O (b ^ n ^ a (n) ^ k), und alle Grenzen müssen unter Berücksichtigung dieser Notation so eng wie möglich sein

Haskell, 259

Ich dachte, ich könnte es kürzer machen. Vielleicht werde ich.
Dies hat eine zeitliche Komplexität von O (n ^ 2 * 2 ^ n) *, so dass die Punktzahl etwa 6,2e82 beträgt

_{* Ich bin mir nicht sicher, aber wenn es irgendeinen "Zusatz" zur Komplexität gibt, ist es nicht mehr als ein Polynom, daher sollte dies die Punktzahl nicht wesentlich verändern.}

import Data.List
g e=tail$snd$minimum[r|r@(_,b)<-iterate(\l->nubBy((.f).(==).f)$sort[(b+d,c:a)|(b,a)<-l,c<-h\\init a,d<-a!!0%c])[(0,[h!!0])]!!length h,b!!0==h!!0]where h=sort$nub$e>>= \(a,b,_)->[a,b];a%b=[z|(x,y,z)<-e,x==a&&y==b||x==b&&y==a]
f(_,x:b)=x:sort b

Python 2, 237 231 228 225 Zeichen

Da dies ein naiver Algorithmus ist, liegt seine Punktzahl wahrscheinlich bei 225! ≈ 1,26e433.

from itertools import*
a=input()
n=lambda*a:tuple(sorted(a))
d=dict((n(*x[:2]),x[2])for x in a)
print min(permutations(set(chain(*[x[:2]for x in a]))),key=lambda x:sum(d.get(n(x[i],x[i+1]),1e400)for i in range(-1,len(x)-1)))

Julia, 213 Zeichen

n!nGeht wohl so , also ~ 2e407.

a=[("New York", "Detroit", 2.2), ("New York", "Dillsburg", 3.7), ("Hong Kong", "Dillsburg", 4), ("Hong Kong", "Detroit", 4), ("Dillsburg", "Detroit", 9000.1), ("New York", "Hong Kong", 9000.01)]
f(a)=(
d(x,y)=(r=filter(z->x in z&&y in z,a);r==[]?Inf:r[1][3]);
m=Inf;
q=0;
c=unique([[z[1] for z=a],[z[2] for z=a]]);
n=length(c);
for p=permutations(c);
    x=sum([d(p[i],p[mod1(i+1,n)]) for i=1:n]);
    x<m&&(m=x;q=p);
end;
q)
f(a)

Zur besseren Lesbarkeit und zur Veranschaulichung der Verwendung habe ich in einigen Zeilenumbrüchen und Tabulatoren sowie bei der Beispieleingabe einen Aufruf der Funktion hinterlassen. Außerdem habe ich einen Algorithmus verwendet, der n!Zeit benötigt , aber keinen n!Speicher. Der Algorithmus ist etwas praktikabler.

Python 3 - 491

Ich habe die Länge der Eingabegraphvariablen nicht gezählt g. Diese Lösung verwendet dynamische Programmierung und hat eine Komplexität von n ^ 2 * 2 ^ n für eine Gesamtpunktzahl von ~ 6,39e147. Ich bin noch ziemlich neu im Golfen, also bitte melden Sie sich, wenn Sie irgendwo eine große Verschwendung von Code sehen!

g=[("New York", "Detroit", 2.2), ("New York", "Dillsburg", 3.7), ("Hong Kong", "Dillsburg", 4), ("Hong Kong", "Detroit", 4), ("Dillsburg", "Detroit", 9000.1), ("New York", "Hong Kong", 9000.01)]
s=''
c={s:1}
D={}
for t in g:c[t[0]]=1;c[t[1]]=1;D[(t[0],t[1])]=t[2];D[(t[1],t[0])]=t[2];D[('',t[0])]=0;D['',t[1]]=0
V={}
y=[x for x in c.keys() if x!='']
f=''
def n(z,p):
 if(len(p)==len(y)-1):
  global f;f=z
 if(0==len(p)):
  return (D[(z,f)] if (z,f) in D else float('inf'))
 Y=[(float('inf'),'')]
 for P in p:
  if((z,P) in D):
   Y.append((D[(z,P)] + n(P,[m for m in p if m!=P]), P))
 V[(z,tuple(p))]=min(Y)
 return min(Y)[0]
n('',y)
for i in range(len(c)-1):
 N=V[(s,tuple(y))][1]
 print(N)
 s=N
 y.remove(N)

Mathematica, 66 Bytes

Most@Last@FindShortestTour@Graph[#<->#2&@@@#,EdgeWeight->Last/@#]&

Keine Ahnung von der Komplexität, daher liegt die Punktzahl irgendwo zwischen 10^23und 10^93.

Rubin, 198 180 Bytes

G=eval(gets.tr("()","[]"))
C=G.map{|t|[t[0],t[1]]}.flatten.uniq
D=Hash.new(+1.0/0)
G.map{|p|D[[p[0],p[1]]]=D[[p[1],p[0]]]=p[2]}
p C.permutation.map{|l|d=0;p=l[-1];l.map{|c|d+=D[[p,c]];p=c};[d,l]}.sort[0][1]

Die erste Zeile, in der die Eingabe gelesen wird, ist nicht markiert, da dies anscheinend alle anderen Benutzer tun. Außerdem wird für Ruby kein abschließender Zeilenumbruch benötigt.

Es erzeugt nur dumm alle Permutationen von Städten, also mach mich fertig O(n!*n). Eigentlich ist es, wenn man es sich überlegt, sogar langsamer, weil es alle O(n!)Pfade sortiert, anstatt die bisher besten zu verfolgen.