Anda diberikan, sebagai daftar atau vektor atau apa pun, sekelompok 3-tupel atau apa pun, di mana dua hal pertama adalah string, dan hal ketiga adalah angka. String adalah kota, dan jumlahnya adalah jarak di antara mereka. Urutan kota-kota dalam tupel adalah arbitrer (yaitu tidak masalah mana yang lebih dulu dan yang datang kedua) karena jaraknya sama untuk setiap jalan. Juga, ada tepat satu tuple untuk setiap pasangan kutipan yang terhubung. Tidak semua kota dapat terhubung. Juga, jaraknya selalu positif (tidak0). Anda tidak perlu memeriksa kondisi ini, Anda mungkin menganggap input akan terbentuk dengan baik. Tugas Anda adalah mengembalikan kota-kota dalam urutan siklik, sehingga, jika Anda memulai di satu kota, dan berkeliling urutan kembali ke kota yang sama, total jarak antara kota-kota akan minimum (persis dan dalam semua kasing.) Anda mungkin menganggap ada solusi. Sebagai contoh, katakanlah Anda diberi

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

Anda dapat menampilkan salah satu dari yang berikut ini (tetapi Anda hanya perlu menampilkan satu):

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

karena ini adalah perjalanan tersingkat: 13.9

tapi tidak

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

karena itu bukan yang terpendek.

Lihat en.wikipedia.org/wiki/Travelling_salesman_problem

Mencetak gol

Di sinilah mulai menarik. Anda mengambil jumlah karakter yang Anda miliki, dan kemudian tancapkan ke rumus O-notasi terburuk. Sebagai contoh, katakanlah Anda menulis program brute force yang terdiri dari 42 karakter. Seperti kita ketahui, kasus terburuk adalah di n!mana njumlah kota. 42! = 1405006117752879898543142606244511569936384000000000, jadi itu adalah skor Anda. The menang skor terendah .

Catatan: Saya juga lega setelah ini, tetapi tidak yakin bagaimana menyelesaikannya dan berharap tidak ada yang memperhatikan. Orang-orang melakukannya, jadi saya akan pergi dengan saran issacg:

satu-satunya pilihan adalah O (n!) dan O (b ^ n n ^ a ln (n) ^ k), dan semua batasan harus sekencang mungkin mengingat notasi tersebut

Haskell, 259

Saya pikir saya akan bisa membuatnya lebih pendek. mungkin aku akan.
ini memiliki kompleksitas waktu O (n ^ 2 * 2 ^ n) * sehingga nilainya sekitar 6.2e82

_{* Saya tidak benar-benar yakin, tetapi jika ada "penambahan" pada kompleksitas, itu tidak lebih dari polinomial, jadi ini seharusnya tidak mengubah banyak skor.}

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 karakter

Karena ini adalah algoritma yang naif, nilainya mungkin sekitar 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 karakter

Mungkin seperti n!n, jadi ~ 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)

Agar mudah dibaca dan untuk didemonstrasikan, saya meninggalkan beberapa baris dan tab baru yang tidak diawetkan, serta input contoh dan panggilan ke fungsi. Saya juga menggunakan algoritma yang membutuhkan n!waktu, tetapi bukan n!memori, ini sedikit lebih layak untuk dijalankan.

Python 3 - 491

Saya tidak menghitung panjang variabel grafik input g. Solusi ini menggunakan pemrograman dinamis, dan memiliki kompleksitas n ^ 2 * 2 ^ n, dengan skor total ~ 6.39e147. Saya masih cukup baru dalam bermain golf, jadi silakan berbaur jika Anda melihat pemborosan kode di suatu tempat!

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 byte

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

Tidak tahu kompleksitasnya, jadi nilainya ada di antara 10^23dan 10^93.

Rubi, 198 180 byte

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]

Baris pertama yang membaca input tidak diberi nilai, karena sepertinya itulah yang dilakukan orang lain. Juga, tidak ada baris baru final yang diperlukan untuk ruby.

Itu dengan bodohnya menghasilkan semua permutasi kota, jadi turunkan aku O(n!*n). Sebenarnya, setelah dipikir-pikir, ini lebih lambat dari itu, karena ini memilah semua O(n!)jalur daripada melacak yang terbaik sejauh ini.