Вам дают в виде списка или вектора, или чего-то еще, набор из 3-х кортежей или чего-то еще, где первые две вещи - это строки, а третья - это число. Строки - это города, а число - это расстояние между ними. Порядок городов в кортеже произвольный (т. Е. Не имеет значения, что идет первым, а что вторым), так как это одинаковое расстояние в каждом направлении. Кроме того, существует ровно один кортеж для каждой пары связанных сайтов. Не все города могут быть связаны. Кроме того, расстояние всегда положительно (не0). Вам не нужно проверять эти условия, вы можете предположить, что входные данные будут правильно сформированы. Ваша задача состоит в том, чтобы возвращать города в циклической последовательности, так что, если вы начнете с какого-либо одного города и обойдете последовательность обратно в один и тот же город, общее расстояние между городами будет минимальным (точно и во всех случаи.) Вы можете предположить, что решение существует. Например, скажем, вам дали

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

Вы можете вывести любое из следующего (но вам нужно вывести только одно):

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

потому что это самая короткая поездка: 13,9

но нет

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

потому что это не самый короткий.

См. En.wikipedia.org/wiki/Travelling_salesman_problem

счет

Вот где это становится интересным. Вы берете количество символов, которое у вас есть, а затем вставляете их в формулу O-обозначения в наихудшем случае. Например, допустим, вы пишете программу грубой силы длиной 42 символа. Как мы все знаем, худший случай , n!когда nэто число городов. 42! = 1405006117752879898543142606244511569936384000000000, так что это ваш счет. Самый низкий балл побеждает .

Примечание: потом я тоже это облегчил, но не знал, как ее решить, и надеялся, что никто не заметит. Люди сделали, так что я пойду с предложением issacg:

единственными вариантами являются O (n!) и O (b ^ n n ^ a ln (n) ^ k), и все границы должны быть как можно более точными, учитывая эту запись

Хаскелл, 259

Я думал, что смогу сделать это короче. Может быть, я буду.
это имеет временную сложность O (n ^ 2 * 2 ^ n) *, поэтому оценка составляет около 6.2e82

_{* На самом деле я не уверен, но если есть какое-то «дополнение» к сложности, оно не более чем полиномиальное, так что это не должно сильно изменить счет.}

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 символов

Поскольку это наивный алгоритм, его оценка, вероятно, около 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)))

Юлия, 213 символов

Вероятно, идет как n!n, так что ~ 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)

Для удобства чтения и демонстрации использования я оставил некоторые неотмеченные символы новой строки и вкладки, а также пример ввода и вызова функции. Также я использовал алгоритм, который требует n!времени, но не n!памяти, его чуть более выполнимо для запуска.

Питон 3 - 491

Я не посчитал длину входной переменной графика g. Это решение использует динамическое программирование и имеет сложность n ^ 2 * 2 ^ n для общего балла ~ 6,39e147. Я все еще довольно новичок в гольфе, поэтому, пожалуйста, присоединяйтесь, если вы видите где-то большую трату кода!

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 байт

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

Понятия не имею по сложности, поэтому оценка где-то между 10^23и 10^93.

Рубин, 198 180 байт

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]

Первая строка, которая читает входные данные, не оценивается, так как кажется, что это делают все остальные. Кроме того, нет окончательного перевода строки, необходимого для ruby.

Он просто тупо порождает все перестановки городов, так что опусти меня O(n!*n). На самом деле, если подумать, это даже медленнее, потому что он сортирует все O(n!)пути, а не отслеживает лучшие.