Vendeur ambulant

17

On vous donne, sous forme de liste ou de vecteur ou autre, un tas de 3-tuples ou autre, où les deux premières choses sont des chaînes, et la troisième chose est un nombre. Les chaînes sont des villes et le nombre est la distance entre elles. L'ordre des villes dans le tuple est arbitraire (c'est-à-dire que peu importe ce qui vient en premier et ce qui vient en second) car c'est la même distance dans chaque sens. En outre, il existe exactement un tuple pour chaque paire de citations connectées. Toutes les villes ne sont pas connectées. De plus, la distance est toujours positive (pas0). Vous n'avez pas besoin de vérifier ces conditions, vous pouvez supposer que l'entrée sera bien formée. Votre travail consiste à renvoyer les villes dans une séquence cyclique, de sorte que, si vous commencez dans une ville et que vous revenez dans la même ville, le total des distances entre les villes sera minimum (exactement et en tout .) Vous pouvez supposer qu'une solution existe. Par exemple, disons qu'on vous donne

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

Vous pouvez générer l'un des éléments suivants (mais vous n'en avez besoin que d'un):

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

car c'est le trajet le plus court: 13,9

mais non

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

car ce n'est pas le plus court.

Voir en.wikipedia.org/wiki/Travelling_salesman_problem

Notation

C'est là que ça devient intéressant. Vous prenez le nombre de caractères que vous avez, puis vous les branchez dans la pire formule de notation O du pire cas. Par exemple, disons que vous écrivez un programme de force brute de 42 caractères. Comme nous le savons tous, le pire des cas est n!nest le nombre de villes. 42! = 1405006117752879898543142606244511569936384000000000, c'est donc votre score. Le score le plus bas l'emporte .

Remarque: J'ai également soulagé cela par la suite, mais je ne savais pas comment le résoudre et j'espérais que personne ne le remarquerait. Les gens l'ont fait, je vais donc suivre la suggestion d'Issacg:

les seules options sont O (n!) et O (b ^ n n ^ a ln (n) ^ k), et toutes les limites doivent être aussi serrées que possible étant donné que la notation

PyRulez
la source
4
Mais comment dites-vous que le code de quelqu'un est O(n!)mais pas O(sqrt(n)*n^n/e^n)ni O(n!/100000000000000000000)?
jimmy23013
1
@ user23013 Une solution consiste à dire que les seules options sont O(n!)et O(b^n*n^a*ln(n)^k), et toutes les limites doivent être aussi serrées que possible compte tenu de cette notation. OP devrait clarifier, cependant.
isaacg
2
@Geobits Comme le montre la bande dessinée, la solution de programmation dynamique est O(n^2*2^n), ce qui est beaucoup moins que O(n!)pour les grands n.
isaacg
@proud haskeller ok (il est en fait sorti depuis un moment et je voulais juste l'accepter parce que c'était le meilleur malgré le fait qu'il n'y avait presque pas de votes, mais si vous obtenez quelque chose de mieux, allez-y.)
PyRulez
@PyRulez bien quoi que j'essaye, je me convainc que la complexité d'O (n!)
Est

Réponses:

5

Haskell, 259

J'ai pensé que je pourrais le raccourcir. peut être que je le ferais.
cela a une complexité temporelle de O (n ^ 2 * 2 ^ n) * donc le score est d'environ 6,2e82

* Je ne suis pas vraiment sûr, mais s'il y a un "ajout" à la complexité, ce n'est pas plus que polynomial, donc cela ne devrait pas beaucoup changer le score.

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
fier haskeller
la source
cela fait un moment, mais existe-t-il une version «non minifiée» (peut-être annotée) disponible? Je suis curieux de savoir comment vous avez résolu ce problème avec Haskell.
Henk Mollema
5

Python 2, 237 231 228 225 caractères

Puisqu'il s'agit d'un algorithme naïf, son score est probablement d'environ 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)))
Greg Hewgill
la source
from itertools import*serait plus court.
seequ
Oh, bonne idée ..!
Greg Hewgill
Je ne peux pas tester maintenant, donc je lance juste des idées. L'ensemble est-il nécessaire?
seequ
L'ensemble est utilisé pour éliminer les doublons dans la liste des villes. Puisque l'entrée ne contient pas d'entrées comme ("a", "a", 0), il faudrait une logique supplémentaire quelque part pour ignorer les bords de longueur nulle. (Et si vous êtes sur le Web, vous pouvez toujours tester avec quelque chose comme codepad.org. )
Greg Hewgill
Je ne connais pas grand chose à Python, mais apparemment vous avez fait appel sumà chaque élément d'une permutation. N'est-ce pas O(n!*n)?
jimmy23013
4

Julia, 213 caractères

n!nVa probablement comme , donc ~ 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)

Pour plus de lisibilité et pour démontrer l'utilisation, j'ai laissé dans certains sauts de ligne et onglets non marqués ainsi que des exemples d'entrée et un appel à la fonction. J'ai également utilisé un algorithme qui nécessite du n!temps, mais pas de n!mémoire, son légèrement plus réalisable à exécuter.

gggg
la source
Appelé sumsur chaque élément d'une permutation. Ne serait-ce pas O (n! * N)?
jimmy23013
Ouais je pense que tu as raison.
gggg
2

Python 3-491

Je n'ai pas compté la longueur de la variable graphique d'entrée g. Cette solution utilise une programmation dynamique et a une complexité de n ^ 2 * 2 ^ n, pour un score total de ~ 6,39e147. Je suis encore assez novice dans le golf, alors n'hésitez pas à jouer si vous voyez un gros gaspillage de code quelque part!

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)
RT
la source
1

Mathematica, 66 octets

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

Aucune idée de la complexité, donc le score se situe entre 10^23et 10^93.

ngenisis
la source
0

Rubis, 198 180 octets

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 première ligne qui lit l'entrée n'est pas notée, car cela semble être ce que tout le monde fait. De plus, aucune nouvelle ligne finale n'est nécessaire pour le rubis.

Il génère simplement toutes les permutations des villes, alors mettez-moi de côté O(n!*n). En fait, à y réfléchir, c'est plus lent encore que cela, car il trie tous les O(n!)chemins plutôt que de garder la trace des meilleurs jusqu'à présent.

DépriméDaniel
la source