Problème
Un coursier part de la ville 0, visite chaque autre ville exactement une fois puis revient à la ville 0. distances[i][j] représente le coût pour aller de i à j. Avec au plus 15 villes, une programmation dynamique avec masques de bits (Held–Karp) sur les ensembles visités est suffisamment rapide.
Implémentez shortest_tour(distances).
Entrée
distances : une matrice n × n des coûts de trajet ; distances[i][i] = 0.
Sortie
Retournez le coût du circuit le moins cher.
Contraintes
1 ≤ n ≤ 15 ; 0 ≤ coût ≤ 1 000 000
Exemples
Entrée :
distances = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
Sortie attendue :
expected = 80Entrée :
std::vector<std::vector<long long>> distances = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
Sortie attendue :
long long expected = 80;Entrée :
long[][] distances = new long[][] {
new long[] {0, 10, 15, 20},
new long[] {10, 0, 35, 25},
new long[] {15, 35, 0, 30},
new long[] {20, 25, 30, 0}
};
Sortie attendue :
long expected = 80;Explication
0→1→3→2→0 coûte 10 + 25 + 30 + 15 = 80, la tournée la moins chère.
Entrée :
distances = [
[0]
]
Sortie attendue :
expected = 0Entrée :
std::vector<std::vector<long long>> distances = {
{0}
};
Sortie attendue :
long long expected = 0;Entrée :
long[][] distances = new long[][] {
new long[] {0}
};
Sortie attendue :
long expected = 0;Explication
Avec une seule ville il n'y a nulle part où aller : 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Comme le nombre de villes est petit, essaie de suivre quelles villes ont été visitées plutôt que d’énumérer tous les trajets directement.
Indice 2
Utilise une programmation dynamique sur les sous-ensembles de villes et garde le meilleur coût pour finir dans chaque ville avec cet ensemble visité.
Indice 3
Fais attention à partir de la ville 0 et à y revenir, et à gérer les cas où certains chemins sont très coûteux mais restent valides.
Complexité attendue
temps O(n^2 2^n), espace supplémentaire O(n 2^n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.