Dostajesz, jako listę, wektor lub cokolwiek, wiązkę 3-krotek lub cokolwiek, gdzie pierwsze dwie rzeczy są łańcuchami, a trzecia to liczba. Ciągi to miasta, a liczba to odległość między nimi. Kolejność miast w krotce jest dowolna (tzn. Nie ma znaczenia, który z nich będzie pierwszy, a który drugi), ponieważ w każdym kierunku jest taka sama odległość. Ponadto dla każdej pary połączonych cytatów jest dokładnie jedna krotka. Nie wszystkie miasta mogą być połączone. Ponadto odległość jest zawsze dodatnia (nie0). Nie musisz sprawdzać tych warunków, możesz założyć, że dane wejściowe będą dobrze sformułowane. Twoim zadaniem jest zwracanie miast w cyklicznej sekwencji, tak że jeśli zaczniesz od jednego miasta i przejdziesz sekwencję z powrotem do tego samego miasta, całkowita odległość między miastami będzie minimalna (dokładnie i we wszystkich przypadki). Możesz założyć, że istnieje rozwiązanie. Powiedzmy na przykład, że otrzymałeś

[("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)]

Możesz wypisać dowolne z poniższych (ale musisz tylko wypisać jedno):

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

ponieważ jest to najkrótsza podróż: 13,9

ale nie

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

ponieważ nie jest najkrótszy.

Zobacz en.wikipedia.org/wiki/Travelling_salesman_problem

Punktacja

Tutaj zaczyna się robić ciekawie. Bierzesz liczbę posiadanych znaków, a następnie podłączasz je do najgorszego wzoru O-notacji. Powiedzmy na przykład, że piszesz program brutalnej siły, który ma 42 znaki. Jak wszyscy wiemy, najgorszy przypadek n!, gdzie njest liczbą miast. 42! = 1405006117752879898543142606244511569936384000000000, więc taki jest twój wynik. Te najniższe wynikiem wygrywa .

Uwaga: później też mi to ulżyło, ale nie byłem pewien, jak to rozwiązać i miałem nadzieję, że nikt tego nie zauważy. Ludzie to zrobili, więc przejdę do sugestii Issacga:

jedynymi opcjami są O (n!) i O (b ^ n n ^ a ln (n) ^ k), a wszystkie granice muszą być jak najściślejsze, biorąc pod uwagę ten zapis

Haskell, 259

Myślałem, że uda mi się to skrócić. Może, bedę.
ma to złożoność czasową O (n ^ 2 * 2 ^ n) *, więc wynik wynosi około 6,2e82

_{* Nie jestem do końca pewien, ale jeśli jest coś „dodającego” do złożoności, to nie jest to więcej niż wielomian, więc nie powinno to zbytnio zmieniać wyniku.}

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 znaków

Ponieważ jest to naiwny algorytm, jego wynik to prawdopodobnie około 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 znaków

Prawdopodobnie idzie tak n!n, więc ~ 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)

Dla czytelności i zademonstrowania użycia pozostawiłem w nieskalowanych znakach nowej linii i kartach, a także przykładowe dane wejściowe i wywołanie funkcji. Użyłem również algorytmu, który wymaga n!czasu, ale nie n!pamięci, jego nieco bardziej wykonalne działanie.

Python 3 - 491

Nie policzyłem długości zmiennej wykresu wejściowego g. To rozwiązanie wykorzystuje programowanie dynamiczne i ma złożoność n ^ 2 * 2 ^ n, co daje łączny wynik ~ 6,39 e147. Nadal jestem całkiem nowy w golfie, więc włącz się, jeśli zobaczysz gdzieś duże marnotrawstwo kodu!

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 bajtów

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

Nie ma pojęcia o złożoności, więc wynik jest gdzieś pomiędzy 10^23a 10^93.

Rubin, 198 180 bajtów

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]

Pierwszy wiersz, w którym czytane są dane wejściowe, nie jest oceniany, ponieważ wydaje się, że robią to wszyscy inni. Poza tym ruby ​​nie wymaga ostatecznej nowej linii.

Po prostu głupio generuje wszystkie permutacje miast, więc mnie odłóż O(n!*n). Właściwie, po zastanowieniu, jest nawet wolniejszy, ponieważ sortuje wszystkie O(n!)ścieżki, a nie śledzi najlepszych do tej pory.