TP Branch & Bound pour le voyageur de commerce (2023)

Fonctions utilitaires

#define repeat(n) for(size_t _ = 0; _ < n; _++)
#define min(lhs, rhs) (((lhs) < (rhs)) ? (lhs) : (rhs))

inline
void swap(size_t * const array, const size_t x, const size_t y) {
    const size_t tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
}

Implémentation

Génération des permutations

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[], const size_t nbVisited, size_t notVisited[], const size_t nbNotVisited, const 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);
        }
    }
}

Calcul de la longueur des différents chemin

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[], const size_t nbVisited, size_t notVisited[], const size_t nbNotVisited, const 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);
        }
    }
}

Calcul du chemin de coût minimal

void permut(size_t visited[], const size_t nbVisited, size_t notVisited[], const size_t nbNotVisited, const int length, int * const 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);
        }
    }
}

Fonction is_crossing

bool is_crossing(const size_t visited[], const size_t nbVisited) {
    const size_t i = nbVisited - 2;
    bool is_crossing = false;
    for (size_t j = 0; j < nbVisited - 1; j++) {
        const int old_cost = cost[visited[i]][visited[i + 1]] + cost[visited[j]][visited[j + 1]];
        const 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);
        }
    }
}

Fonction Bound

int 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);
        }
    }
}

Prim

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;
}

Tri

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);
  ...
}