/* Programmation dynamique du ploblème du voyageur de commerce.
Pour n villes, la taille mémoire est O(n 2^n) et le temps de calcul O(n² 2^n).
Ce programme met moins d'une seconde pour 25 villes.
f[(1<<2)+(1<<3)+(1<<5)][4]=min(d[n-1][2]+d[2][3]+d[3][5]+d[5][4],
                               d[n-1][2]+d[2][5]+d[5][3]+d[3][4],
                               d[n-1][3]+d[3][2]+d[2][5]+d[5][4],
                               d[n-1][3]+d[3][5]+d[5][2]+d[2][4],
                               d[n-1][5]+d[5][2]+d[2][3]+d[3][4],
                               d[n-1][5]+d[5][3]+d[3][2]+d[2][4])
est la longueur du plus court chemin de la ville n-1 à la ville 4
en passant intermédiairement par les villes 2, 3 et 5.
if((1<<j)&J) veut dire "si la ville j est dans l'ensemble J". 
if((1<<j)&~J) veut dire "si la ville j n'est pas dans l'ensemble J". 
J-=1<<j veut dire "on enlève la ville j de l'ensemble J".
x est la longueur du plus court chemin allant de n-1 à j en passant
intermédiairement un fois par chacune des villes de J, la dernière
ville intermédiaire traversée étant i.
Donc F[J][j] est le minimum de x quand i décrit l'ensemble J. */
#include<stdio.h>
#define n 4
#define nn (1<<(n-1))
int d[n][n]={{0,3,2,4},
             {3,0,2,5},
             {2,2,0,3},
             {4,5,3,0}}, f[nn][n];
int main()
{ int J,i,j,x;
 for(j=0;j<n-1;j++) f[0][j]=d[n-1][j];
 for(J=1;J<nn;J++) for(j=0;j<n;j++) if((1<<j)&~J) if(j<n-1||J==nn-1)
 { f[J][j]=1000;
   for(i=0;i<n;i++) if((1<<i)&J)
   if(x=f[J-(1<<i)][i]+d[i][j], x<f[J][j]) f[J][j]=x;
 }
 for(J=nn-1,j=n-1;J;j=i,J-=1<<j)
 { for(i=0;i<n;i++) if((1<<i)&J) if(f[J-(1<<i)][i]+d[i][j]==f[J][j]) break;
   printf("d[%d][%d]=%d ",j,i,d[i][j]);
 }
 printf("d[%d][%d]=%d   %d\n",j,n-1,d[n-1][j],f[nn-1][n-1]);
 getchar();
 getchar();
 return 0;
}