/*-----------------------------------------------------------------------
* pvccoco-02
*
* Dans cette version : simple "2-opt" appliqué au 8 balles
* Voir les fichier README.francais et COPYING
*
* Auteur : Alexandre AUPETIT (aaupetit@club-internet.fr)
* Web : http://home.alex.tuxfamily.org/pvc.html
* http://home.alex.tuxfamily.org/pvc/robotique/coconut.html
*
* Important : Ce logiciel est soumis à la licence de logiciel libre GPL
*-----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>
#define NB_BALLES 8
#define MAX_LENLINE 255
double pos_x[NB_BALLES+1]; // tableau des position en X des balles (en 0 : pos initiale du robot)
double pos_y[NB_BALLES+1]; // tableau des position en Y des balles (en 0 : pos initiale du robot)
int parcours[NB_BALLES+1]; // parcours (numéros des balles) (en 0 : pos initiale du robot)
double score_parcours; // coût du parcours == distance totale
// retourne un chiffre au hasard entre 0 et max
int hasard(int max) {
return (int)((rand()/(RAND_MAX + 1.0))*max);
}
// distance entre deux points dont les coordonnées sont définies dans pos_x et pos_y
// distance euclidienne
double distance_point(int point1, int point2) {
return sqrt((pos_x[point2]-pos_x[point1])*(pos_x[point2]-pos_x[point1])
+(pos_y[point2]-pos_y[point1])*(pos_y[point2]-pos_y[point1]));
}
// distance totale du parcours
// attention on prend en compte le parcours entre le robot et la première balle
// (parcours[0] à parcours[1]) mais on ne revient pas à la position initiale
// contrairement au PVC classique
double distance_parcours() {
int i;
double d=0;
for (i=1;i<NB_BALLES+1;i++) {
d+=distance_point(parcours[i-1], parcours[i]);
}
return d;
}
// affichage du parcours (et de son score) à l'écran
// avec aussi un message d'info
void affiche_parcours(char *message_info) {
int i;
printf("%s", message_info);
for (i=0;i<NB_BALLES+1;i++) {
printf("%d-", parcours[i]);
}
printf("(d=%lf)\n", score_parcours);
}
// initialisation de la position des balles par lecture du fichier pos.txt
// le fichier pos_balles.txt doit contenir les positions au format :
// x_robot;y_robot
// x_balle1;y_balle1
// x_balle2;y_balle2
// x_balle3;y_balle3
// ...
// x_balle8;y_balle8
void init_pos() {
FILE *ficPos;
char sLine[MAX_LENLINE + 1];
char *sPos;
int i;
ficPos=fopen("pos_balles.txt", "rt");
if (ficPos != NULL) {
i=0;
do {
fgets(sLine, MAX_LENLINE, ficPos);
sPos = strtok(sLine, ";\n");
//printf("%s-\n",sPos);
if (sPos != NULL) {pos_x[i] = atoi(sPos);}
sPos = strtok(NULL, ";\n");
//printf("%s-\n",sPos);
if (sPos != NULL) {pos_y[i] = atoi(sPos);}
i++;
} while ( !feof(ficPos) );
if (i != NB_BALLES+2) {
printf("Erreur dans le nombre de villes du fichier pos.txt !");
exit(1);
}
} else {
printf("Erreur d'ouverture du fichier pos.txt !");
exit(1);
}
/*
// pour tester...
// position du robot
pos_x[0] = 0;
pos_y[0] = 0;
// position des balles
int i;
for (i=1;i<NB_BALLES+1;i++) {
pos_x[i] = i;
pos_y[i] = 0;
}
*/
}
// echange l'odre de parcours entre 2 balles
void echange_parcours(int ordre1, int ordre2) {
int inter;
inter=parcours[ordre2];
parcours[ordre2]=parcours[ordre1];
parcours[ordre1]=inter;
}
// renverse le parcours entre les balles i et j
// il s'agit de la transformation la plus simple d'un parcours
// voir graphiquement ce que ça représente
// c'est la transformation de base du 2-opt : le 2-change
void renverse_parcours(int i, int j) {
int a, b;
if (i < j) {
a = i;
b = j;
} else {
a = j;
b = i;
}
while (a < b) {
echange_parcours (a, b);
a++;
b--;
}
}
// initialise un parcours au hasard
void calcule_parcours_hasard() {
int i;
for (i=1;i<NB_BALLES+1;i++) {
parcours[i] = i;
}
int a,b;
for (i=1;i<NB_BALLES+1;i++) {
a=hasard(NB_BALLES)+1;
b=hasard(NB_BALLES)+1;
echange_parcours(a, b);
}
}
// --------------- 2-OPT --------------------------
// différence de cout du parcours si on renversait le parcours entre les balles i et j
// on "casse" 2 liens entre 2 balles et on les remplace par 2 autres
double difference_cout_2opt(int i, int j) {
if (j+1<NB_BALLES+1) {
return (distance_point(parcours[i], parcours[j+1])
+ distance_point(parcours[i-1], parcours[j])
- distance_point(parcours[i-1], parcours[i])
- distance_point(parcours[j], parcours[j+1]));
} else {
return (
distance_point(parcours[i-1], parcours[j])
- distance_point(parcours[i-1], parcours[i])
);
}
}
// calcule un parcours 2-opt, c'est à dire qu'aucune permutation
// de l'odre de parcours ne rend ce parcours plus court
void calcule_parcours_2opt() {
int i, j, modifie;
do {
modifie=0;
for (i=1;i<NB_BALLES+1;i++) {
for (j=i+1;j<NB_BALLES+1;j++) {
if (difference_cout_2opt(i, j) < 0.0) {
renverse_parcours(i, j);
modifie=1;
}
}
}
} while (modifie == 1);
}
// --------------- INSERTION-OPT --------------------------
// différence de longueur de trajet lorsqu'on isère i entre j et j+1
// attention aux conditions pour lesquelles ce gain est valide ( i+1<j ) ...
double difference_cout_insert(int i, int j) {
if (j+1<NB_BALLES+1) {
return (distance_point(parcours[i], parcours[j])
+ distance_point(parcours[i], parcours[j+1])
+ distance_point(parcours[i-1], parcours[i+1])
- distance_point(parcours[i-1], parcours[i])
- distance_point(parcours[i], parcours[i+1])
- distance_point(parcours[j], parcours[j+1]));
} else {
return (distance_point(parcours[i], parcours[j])
+ distance_point(parcours[i-1], parcours[i+1])
- distance_point(parcours[i-1], parcours[i])
- distance_point(parcours[i], parcours[i+1])
);
}
}
// différence de longueur de trajet lorsqu'on isère j entre i et i+1
double difference_cout_insert_inv(int i, int j) {
if (j+1<NB_BALLES+1) {
return (distance_point(parcours[i-1], parcours[j])
+ distance_point(parcours[i], parcours[j])
+ distance_point(parcours[j-1], parcours[j+1])
- distance_point(parcours[i-1], parcours[i])
- distance_point(parcours[j-1], parcours[j])
- distance_point(parcours[j], parcours[j+1]));
} else {
return (distance_point(parcours[i-1], parcours[j])
+ distance_point(parcours[i], parcours[j])
- distance_point(parcours[i-1], parcours[i])
- distance_point(parcours[j-1], parcours[j])
);
}
}
// insere la balle i entre j et j+1
// attention, il faut que i<j !!
void insert_parcours (int i, int j)
{
int a, b, i_temp;
a = i;
b = j;
i_temp = parcours[a];
while (a < b) {
parcours[a] = parcours[a + 1];
a++;
}
parcours[b] = i_temp;
}
// insere la balle j entre i et i+1
// attention, il faut que i<j !!
void insert_inv_parcours (int i, int j)
{
int a, b, i_temp;
a = i;
b = j;
i_temp = parcours[b];
while (b > a) {
parcours[b] = parcours[b - 1];
b--;
}
parcours[a] = i_temp;
}
// calcule un parcours insert-opt, c'est à dire qu'aucune insertion
// d'une ville à un autre endroit du parcours ne rend ce parcours plus court
void calcule_parcours_insert() {
int i, j;
for (i=1;i<NB_BALLES+1;i++) {
for (j=i+2;j<NB_BALLES+1;j++) {
if (difference_cout_insert(i, j) < 0.0) {
insert_parcours(i, j);
} else {
if (difference_cout_insert_inv(i, j) < 0.0) {
insert_inv_parcours(i, j);
}
}
}
}
}
// prcédure qui combine de manière très efficace calcule_parcours_2opt et calcule_parcours_insert
// Le parcours résultant est 2-opt et insertion-opt
void calcule_parcours_2opt_et_insert() {
int i, j, modifie;
do {
modifie=0;
//2-opt
for (i=1;i<NB_BALLES+1;i++) {
for (j=i+1;j<NB_BALLES+1;j++) {
if (difference_cout_2opt(i, j) < 0.0) {
renverse_parcours(i, j);
modifie=1;
}
}
}
// insert-opt
// (le 2-opt est prioritaire car il conduiut à de meilleures solutions,
// d'où la condition modifie==0
for (i=1;(i<NB_BALLES+1)&&(modifie==0);i++) {
for (j=i+2;(j<NB_BALLES+1)&&(modifie==0);j++) {
if (difference_cout_insert(i, j) < 0.0) {
insert_parcours(i, j);
modifie=1;
} else {
if (difference_cout_insert_inv(i, j) < 0.0) {
insert_inv_parcours(i, j);
modifie=1;
}
}
}
}
} while (modifie == 1);
}
// ----------------------------------------------------------------------------
// prog principal
// ----------------------------------------------------------------------------
int main(int argc, char *argv[]) {
int i, nb_essais;
srand (time (NULL));
nb_essais=1;
if (argc == 2) {
nb_essais=atoi(argv[1]);
} else {
if (argc != 1) {
printf("Erreur dans le nombre d'arguments !\n");
printf("Usage : pvccoco [Nb d'essais]\n");
exit(1);
}
}
init_pos();
for (i=0;i<nb_essais;i++) {
calcule_parcours_hasard();
score_parcours=distance_parcours();
affiche_parcours("Chemin aléatoire : ");
calcule_parcours_2opt_et_insert();
score_parcours=distance_parcours();
affiche_parcours("Après optimisation : ");
}
return 0;
}