#include <iostream> #include <stdlib.h> #include <limits.h> const int N = 10; int distance [N] [N]; bool visitee [N]; int meilleurTrajet [N + 1]; int meilleurCout; void plusCourtTrajet (int depth, int coutChemin, int trajet [N + 1]); void voyageur () { int trajet [N + 1]; for (int i = 0; i < N; i++) visitee [i] = false; visitee [0] = true; trajet [0] = 0; meilleurCout = INT_MAX; plusCourtTrajet (1, 0, trajet); } void plusCourtTrajet (int depth, int coutChemin, int trajet [N + 1]) { if (depth == N) { trajet [N] = 0; coutChemin += distance [trajet [N - 1]] [0]; if (coutChemin < meilleurCout) { meilleurCout = coutChemin; for (int i = 0; i <= N; i++) meilleurTrajet [i] = trajet [i]; } } else for (int i = 1; i < N; i++) if (!visitee [i]) { trajet [depth] = i; visitee [i] = true; plusCourtTrajet (depth + 1, coutChemin + distance [trajet [depth - 1]] [i], trajet); visitee [i] = false; } } int main () { for (int i = 0; i < N; i++) { distance [i] [i] = 0; for (int j = 0; j < i + 1; j++) { std::cerr << distance [i] [j] << ","; } for (int j = i + 1; j < N; j++) { distance [i] [j] = rand () % 1000; distance [j] [i] = distance [i] [j]; std::cerr << distance [i] [j] << ","; } std::cerr << std::endl; } voyageur (); std::cerr << std::endl; for (int i = 0; i < N; i++) std::cerr << meilleurTrajet [i] << ","; std::cerr << std::endl << meilleurCout << std::endl; }