#define repeat(n) for(size_t _ = 0; _ < n; _++)
#define min(lhs, rhs) ((lhs < rhs) ? lhs : rhs)
void swap(size_t *array, size_t x, size_t y) {
size_t tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
Pour modéliser ce problème nous utilisons les entiers non signés usize pour représenter les noeuds. Les coûts sont représentés par
une valeur signées sur 32 bits (i32).
Loading content...
Pour modéliser notre chemin, nous utilisons deux listes, la liste des noeuds vus (appartenant au chemin parcouru) et la liste des noeuds non vus.
Loading content...
La première partie du TP consiste à générer l’ensemble des permutations possible pour $n$ sommets. Pour ce faire, nous utilisons une fonction récursive qui travaille en deux étapes. Lors de la première étape nous ajoutons un des sommets de l’ensemble $non\_vus$ à l’ensemble des sommets $vus$, nous effectuons ensuite l’appel recursif. Au retour de cet appel, nous enlevons le dernier sommet de l’ensemble $vus$ pour le remettre dans l’ensemble $non\_vus$ puis nous passons au noeud suivant. La condition d’arrêt est que l’ensemble des $non\_vus$ est vide.
void permut(size_t visited[], size_t nbVisited, size_t notVisited[], size_t nbNotVisited, int length) {
if (nbNotVisited == 0) {
for (size_t i = 0; i < nbVisited; i++) printf("")
printf("%d", length + cost[visited[nbVisited - 1]][0]);
nbCalls++;
} else {
nbCalls++;
for (size_t i = 0; i < nbNotVisited; i++) {
visited[nbVisited] = notVisited[i];
swap(notVisited, i, nbNotVisited - 1);
permut(visited, nbVisited + 1, notVisited, nbNotVisited - 1,
length + cost[visited[nbVisited - 1]][visited[nbVisited]]);
swap(notVisited, i, nbNotVisited - 1);
}
}
}
Une fois la génération des chemins effectuée, il suffit de calculer la longueur du chemin en ajoutant le cout de l’arc partant du dernier sommet non vus (avant l’ajout du nouveau noeud) vers le dernier sommet non vus (après l’ajout du nouveau noeud). On veillera également à ne pas oublier d’ajouter le cout de l’arc partant du dernier des sommets vus vers le noeud $0$ lors d’une récursion terminale.
void permut(size_t visited[], size_t nbVisited, size_t notVisited[], size_t nbNotVisited, int length) {
if (nbNotVisited == 0) {
printf("%d", length + cost[visited[nbVisited - 1]][0]);
nbCalls++;
} else {
nbCalls++;
for (size_t i = 0; i < nbNotVisited; i++) {
visited[nbVisited] = notVisited[i];
swap(notVisited, i, nbNotVisited - 1);
permut(visited, nbVisited + 1, notVisited, nbNotVisited - 1,
length + cost[visited[nbVisited - 1]][visited[nbVisited]]);
swap(notVisited, i, nbNotVisited - 1);
}
}
}
void permut(size_t visited[], size_t nbVisited, size_t notVisited[], size_t nbNotVisited, int length, int *best) {
if (nbNotVisited == 0) {
*best = min(*best, length + cost[visited[nbVisited - 1]][0]);
nbCalls++;
} else {
nbCalls++;
for (size_t i = 0; i < nbNotVisited; i++) {
visited[nbVisited] = notVisited[i];
swap(notVisited, i, nbNotVisited - 1);
permut(visited, nbVisited + 1, notVisited, nbNotVisited - 1,
length + cost[visited[nbVisited - 1]][visited[nbVisited]], best);
swap(notVisited, i, nbNotVisited - 1);
}
}
}
is_crossingbool is_crossing(size_t visited[], size_t nbVisited) {
size_t i = nbVisited - 2;
bool is_crossing = false;
for (size_t j = 0; j < nbVisited - 1; j++) {
int old_cost = cost[visited[i]][visited[i + 1]] + cost[visited[j]][visited[j + 1]];
int new_cost = cost[visited[i]][visited[j]] + cost[visited[i + 1]][visited[j + 1]];
if (old_cost > new_cost) {
is_crossing = true;
break;
}
}
return is_crossing;
}
void permut(size_t visited[], size_t nbVisited, size_t notVisited[], size_t nbNotVisited, int length, int *best) {
if (nbNotVisited == 0) {
*best = min(*best, length + cost[visited[nbVisited - 1]][0]);
nbCalls++;
} else {
nbCalls++;
for (size_t i = 0; i < nbNotVisited; i++) {
visited[nbVisited] = notVisited[i];
swap(notVisited, i, nbNotVisited - 1);
if (!is_crossing(visited, nbVisited + 1)) {
permut(visited, nbVisited + 1, notVisited, nbNotVisited - 1,
length + cost[visited[nbVisited - 1]][visited[nbVisited]], best);
}
swap(notVisited, i, nbNotVisited - 1);
}
}
}
Boundint bound(size_t visited[], size_t nbVisited, size_t notVisited[], size_t nbNotVisited) {
size_t lastVisited = visited[nbVisited - 1];
if (nbNotVisited == 0) return cost[lastVisited][0];
int l = INT_MAX;
for (size_t i = 0; i < nbNotVisited; i++) {
l = min(l, cost[lastVisited][notVisited[i]]);
}
int sum_li = 0;
for (size_t i = 0; i < nbNotVisited; i++) {
int li = cost[notVisited[i]][0];
for (size_t j = 0; j < nbNotVisited; j++) {
if (i != j) {
li = min(li, cost[notVisited[i]][notVisited[j]]);
}
}
sum_li += li;
}
return l + sum_li;
}
void permut(size_t visited[], size_t nbVisited, size_t notVisited[], size_t nbNotVisited, int length, int *best) {
if (nbNotVisited == 0) {
*best = min(*best, length + cost[visited[nbVisited - 1]][0]);
nbCalls++;
} else if (length + bound_prim(visited, nbVisited, notVisited, nbNotVisited) < *best) {
nbCalls++;
for (size_t i = 0; i < nbNotVisited; i++) {
visited[nbVisited] = notVisited[i];
swap(notVisited, i, nbNotVisited - 1);
if (!is_crossing(visited, nbVisited + 1)) {
permut(visited, nbVisited + 1, notVisited, nbNotVisited - 1,
length + cost[visited[nbVisited - 1]][visited[nbVisited]], best);
}
swap(notVisited, i, nbNotVisited - 1);
}
}
}
typedef u_int64_t set;
bool contains(set s, size_t element) {
return (s & (1ul << element)) != 0;
}
void add(set *s, size_t element) {
*s |= (1ul << element);
}
int prim(size_t visited[], size_t nbVisited, size_t notVisited[], size_t nbNotVisited) {
set P = 0ul;
int c[nbVisited + nbNotVisited];
int length = 0;
add(&P, notVisited[0]);
for (size_t i = 0; i < nbNotVisited; i++) {
c[notVisited[i]] = cost[notVisited[0]][notVisited[i]];
}
repeat(nbNotVisited - 1) {
size_t si = 0;
int c_min = INT_MAX;
for (size_t i = 0; i < nbNotVisited; i++) {
if (!contains(P, notVisited[i]) && c[notVisited[i]] < c_min) {
si = i;
c_min = c[notVisited[i]];
}
}
add(&P, notVisited[si]);
length += c_min;
for (size_t j = 0; j < nbNotVisited; j++) {
if (!contains(P, notVisited[j])) {
c[notVisited[j]] = min(c[notVisited[j]], cost[notVisited[si]][notVisited[j]]);
}
}
}
return length;
}
int bound_prim(size_t visited[], size_t nbVisited, size_t notVisited[], size_t nbNotVisited) {
size_t lastVisited = visited[nbVisited - 1];
if (nbNotVisited == 0) return cost[lastVisited][0];
int minVisitedToNotVisited = INT_MAX;
int minNotVisitedToZero = INT_MAX;
for (size_t i = 0; i < nbNotVisited; i++) {
minVisitedToNotVisited = min(minVisitedToNotVisited, cost[lastVisited][notVisited[i]]);
minNotVisitedToZero = min(minNotVisitedToZero, cost[notVisited[i]][0]);
}
return minVisitedToNotVisited + prim(visited, nbVisited, notVisited, nbNotVisited) + minNotVisitedToZero;
}
void* qsort_arg = 0;
int comparison(const void *lhs, const void *rhs) {
size_t t_lhs = *(size_t *) lhs;
size_t t_rhs = *(size_t *) rhs;
size_t last = *(size_t *) qsort_arg;
return cost[last][t_lhs] - cost[last][t_rhs];
}
void permut(size_t visited[], size_t nbVisited, size_t notVisited[], size_t nbNotVisited, int length, int *best) {
...
qsort_arg = (void *) &visited[nbVisited - 1];
qsort(sorted_not_visited, nbNotVisited, sizeof(size_t), comparison);
...
}