Se le da, como una lista o vector o lo que sea, un grupo de 3 tuplas o lo que sea, donde las dos primeras cosas son cadenas y la tercera es un número. Las cadenas son ciudades, y el número es la distancia entre ellas. El orden de las ciudades en la tupla es arbitrario (es decir, no importa cuál viene primero y cuál viene segundo) ya que es la misma distancia en cada sentido. Además, hay exactamente una tupla por cada par de citas conectadas. No todas las ciudades pueden estar conectadas. Además, la distancia siempre es positiva (no0) No es necesario que verifique estas condiciones, puede suponer que la entrada estará bien formada. Su trabajo es devolver las ciudades en una secuencia cíclica, de modo que, si comienza en cualquier ciudad y recorre la secuencia de regreso a la misma ciudad, el total de las distancias entre las ciudades será mínimo (exactamente y en total casos.) Puede suponer que existe una solución. Por ejemplo, digamos que le dan

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

Puede generar cualquiera de los siguientes (pero solo necesita generar uno):

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

porque es el viaje más corto: 13,9

pero no

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

porque no es el más corto

Ver en.wikipedia.org/wiki/Travelling_salesman_problem

Puntuación

Aquí es donde se pone interesante. Usted toma la cantidad de caracteres que tiene y luego los conecta a la fórmula de notación O más desfavorable. Por ejemplo, supongamos que escribe un programa de fuerza bruta que tiene 42 caracteres. Como todos sabemos, el peor de los casos es n!dónde nestá el número de ciudades. 42! = 1405006117752879898543142606244511569936384000000000, así que ese es tu puntaje. El puntaje más bajo gana .

Nota: También alivié esto después, pero no estaba seguro de cómo resolverlo y esperaba que nadie lo notara. La gente lo hizo, así que iré con la sugerencia de issacg:

las únicas opciones son O (n!) y O (b ^ n n ^ a ln (n) ^ k), y todos los límites deben ser lo más ajustados posible dada esa notación

Haskell, 259

Pensé que podría acortarlo. Quizás lo haga.
esto tiene una complejidad temporal de O (n ^ 2 * 2 ^ n) *, por lo que la puntuación es de aproximadamente 6.2e82

_{* No estoy realmente seguro, pero si hay alguna "adición" a la complejidad, no es más que polinomio, por lo que esto no debería cambiar mucho la puntuación.}

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 caracteres

Dado que este es un algoritmo ingenuo, ¡su puntaje es probablemente de 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 caracteres

Probablemente va así n!n, entonces ~ 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)

Para facilitar la lectura y demostrar el uso, dejé algunas líneas nuevas y pestañas sin puntaje, así como entradas de ejemplo y una llamada a la función. También utilicé un algoritmo que requiere n!tiempo, pero no n!memoria, es un poco más factible de ejecutar.

Python 3-491

No conté la longitud de la variable gráfica de entrada g. Esta solución utiliza programación dinámica y tiene una complejidad de n ^ 2 * 2 ^ n, para un puntaje total de ~ 6.39e147. Todavía soy bastante nuevo en el golf, ¡así que por favor interviene si ves un gran desperdicio de código en alguna parte!

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/@#]&

No tengo idea de la complejidad, por lo que la puntuación está en algún lugar entre 10^23y 10^93.

Rubí, 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]

La primera línea que lee la entrada no tiene puntaje, ya que parece ser lo que todos los demás están haciendo. Además, no hay una nueva línea final necesaria para ruby.

Simplemente genera tontamente todas las permutaciones de las ciudades, así que desánime O(n!*n). En realidad, pensándolo bien, es más lento incluso que eso, porque clasifica todos los O(n!)caminos en lugar de hacer un seguimiento de los mejores hasta ahora.