Pour représenter un circuit hamiltonien nous utilisons un tableau de size_t ainsi que la longeur du circuit.
size_t n = input("Number of vertices: ");
size_t sol[n];
La matrice des coûts est représentée par un tableau de intà deux dimensions. Cette matrice est générée de manière pseudo-aléatoire.
int **createCost(size_t n, FILE *fd);
Les algorithmes gloutons recherchent des solutions uniquement en autorisant des modifications qui améliorent la solution actuelle. Dans le cas d’une fonction à optimiser, il est possible que l’évaluation de la fonction ne soit pas monotone. Dans ce cas, il sera forcément nécessaire de dégrader les solutions pour espérer atteindre un meilleur résultat, cette dégradation peut être crée en générant de nouvelles solutions aléatoires (première partie du TP) ou en modifiant aléatoirement la solution optimale (deuxième partie).
Dans un premier temps, un générateur aléatoire de circuit hamiltonien vous est fourni.
Loading content...
Dans le cas où les arcs représentent des distances euclidiennes nous pouvons prouver qu’il est possile d’améliorer un circuit en décroisant les arcs. Nous prenons le cas suivant :
digraph {
node[shape=point];
A [pos="0,0!"];
B [pos="4,-2!"];
C [pos="4,0!"];
D [pos="0,-2!"];
O [pos="2,-1!"];
node[shape=none]
A_label [pos="-0.2,0!", label="A"];
B_label [pos="4.2,-2!", label="B"];
C_label [pos="4.2,0!", label="C"];
D_label [pos="-0.2,-2!", label="D"];
O_label [pos="2,-0.6!", label="O"];
splines=false;
edge[arrowhead=none];
A -> C [style="dashed"];
D -> B [style="dashed"];
A -> O; O -> B;
C -> O; O -> D;
}
Nous souhaitons montrer que la somme des coûts de $(A, C)$ + $(B, D)$ est inférieure à la somme des coût de $(A, B)$ + $(C, D)$.
Dans le cas d’un problème euclidien, pour tout triangle $XYZ$.
graph {
splines=false;
X [pos="0,0!",shape=point];
X_label [pos="-0.2,0!",shape=none,label="X"];
Y [pos="2,1!",shape=point];
Y_label [pos="2,1.2!",shape=none,label="Y"];
Z [pos="3,0!",shape=point];
Z_label [pos="3.2,0!",shape=none,label="Z"];
X -- Y -- Z -- X;
}
Nous avons :
$$ \begin{aligned} XZ \le XY + YZ \\ XY \le XZ + ZY \\ YZ \le YX + XZ \end{aligned} $$
(La droite est la plus courte distance).
Dans notre cas, si nous prenons le triangle supérieur $AOC$, nous avons alors $AC \le AO + OC$.
digraph {
node[shape=point];
A [pos="0,0!"];
B [pos="4,-2!"];
C [pos="4,0!"];
D [pos="0,-2!"];
O [pos="2,-1!"];
node[shape=none]
A_label [pos="-0.2,0!", label="A"];
B_label [pos="4.2,-2!", label="B"];
C_label [pos="4.2,0!", label="C"];
D_label [pos="-0.2,-2!", label="D"];
O_label [pos="2,-0.6!", label="O"];
splines=false;
edge[arrowhead=none];
A -> C [style="dashed", color=red];
D -> B [style="dashed"];
A -> O [color=red]; O -> B;
C -> O [color=red]; O -> D;
}
De même pour le triangle inféreur, nous avons alors $BD \le BO + OD$.
digraph {
node[shape=point];
A [pos="0,0!"];
B [pos="4,-2!"];
C [pos="4,0!"];
D [pos="0,-2!"];
O [pos="2,-1!"];
node[shape=none]
A_label [pos="-0.2,0!", label="A"];
B_label [pos="4.2,-2!", label="B"];
C_label [pos="4.2,0!", label="C"];
D_label [pos="-0.2,-2!", label="D"];
O_label [pos="2,-0.6!", label="O"];
splines=false;
edge[arrowhead=none];
A -> C [style="dashed"];
D -> B [style="dashed", color=red];
A -> O; O -> B [color=red];
C -> O; O -> D [color=red];
}
En ajoutant $AC$ et $BD$ nous avons donc:
$$ AC + BD \le AO + OC + BO + OD \iff AC + BD \le AB + CD $$
$\square$
Le coût du nouveau chemin peut être calculé à partir de l’ancien chemin modifier de l’écart entre $AC + BD$ et $AB + CD$.
typedef struct {
size_t i;
size_t j;
} Pair;
int greedyLS(int total, size_t n, size_t *solution, const int **cost) {
// Insert your code for greedily improving solution here!
while(true) {
int best = 0;
Pair swap_indices;
for (size_t i = 0; i < n; i++) {
for (size_t j = i + 2; j <= n; j++) {
// Cout de AB + CD - (AC + BD)
int benefit = cost[solution[i]][solution[(i + 1) % n]] + cost[solution[j % n]][solution[(j + 1) % n]] -
cost[solution[i]][solution[j % n]] - cost[solution[(i + 1) % n]][solution[(j + 1) % n]];
if (benefit > best) {
best = benefit;
swap_indices.i = i + 1;
swap_indices.j = j;
}
}
}
if (best == 0) break;
total -= best;
// permute swap_indices.
}
return total;
}
Dans cette fonction nous recherchons la paire $(i,j)$ maximisant la fonction: $$ f(i, j) = coût(i, i + 1) + coût(j, j + 1) - coût(i, j) - coût(i + 1, j + 1) $$ afin de décroiser en premier les arcs qui permettent de puls améliorer la solution.
Pour décroiser les arcs $(i, i+ 1)$ et $(j, j + 1)$ il ne suffit pas d’inverser les noeuds $i + 1$ et $j$ en effet, nous avions un chemin de cette forme:
digraph {
node[shape=point];
A [pos="0,0!"];
B [pos="4,-2!"];
C [pos="4,0!"];
D [pos="0,-2!"];
A -> B;
C -> D;
D -> A;
B -> C;
}
Alors qu’avec l’inversion des noeuds nous obtenons un circuit comme cela :
digraph {
node[shape=point];
A [pos="0,0!"];
B [pos="4,-2!"];
C [pos="4,0!"];
D [pos="0,-2!"];
A -> B [style="dashed",arrowhead=none];
A -> C [color=red];
C -> D [style="dashed",arrowhead=none];
B -> D [color=red];
D -> A;
B -> C;
}
La partie droite du circuit est à l’envers du nouveau circuit crée. Il faut donc inverser la séquence $i + 1, j$. Pour se faire il suffit d’observer la position des valeurs dans la solution initial et la nouvelle solution.
$$ \begin{array}{|c|c|c||c|c|c|c|c|c|c|c||c|c|c|} \hline 0 & 1 & … & i & i + 1 & i + 2 & i + 3 & … & j - 2 & j - 1 & j & j + 1 & … & n- 1 \\ \hline \end{array} $$
$$ \begin{array}{|c|c|c||c|c|c|c|c|c|c|c||c|c|c|} \hline 0 & 1 & … & i & j & j - 1 & j - 2 & … & i + 3 & i + 2 & i + 1 & j + 1 & … & n- 1 \\ \hline \end{array} $$
Cette transformation peut facilement être effectuée avec :
void swap(size_t *array, size_t x, size_t y) {
size_t tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
// In: int greedyLS(int total, size_t n, size_t *solution, const int **cost);
while (swap_indices.i < swap_indices.j) {
swap(solution, swap_indices.i % n, swap_indices.j % n);
swap_indices.i++;
swap_indices.j--;
}
La combinaison de la génération aléatoire et de l’amélioration Gloutonne permet d’avoir une première solution. Nous pouvons cependant réfléchir à la manière dont sont générés les solutions aléatoires.
En effet, au lieu de repartir d’une solution totalement aléatoire, une idée pourrait être de réutiliser la meilleure solution obtenue. Les nouvelles instances seraient alors générées à partir d’une version perturbée de la nouvelle instance. Ce raisonnement part du principe que les optimums locaux sont proches de l’optimal global.
Loading content...