TSP問題をiZ-Cで解いてみる。

TSP問題をiZ-Cで解いてみる。
------------------------------------------------------------------------------
time ./tsp 1 $(seq 0 99 |shuf |head -n 12)
Solution 7
128: 45, 36, 14, 15, 9, 48, 59, 78, 67, 56, 71, 80
. . . . . . . . . 4
. . . . 2 3 . . . .
. . . . . . . . . .
. . . . . . 1 . . .
. . . . . 0 . . 5 .
. . . . . . 9 . . 6
. . . . . . . 8 . .
. 10 . . . . . . 7 .
11 . . . . . . . . .
. . . . . . . . . .
^C

/**************************************************************************
* TSP ロケーション番号を引数として与える.
**************************************************************************/
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include "iz.h" //gcc -lm
int DISP;
int DIM = 10, CITY_N;
int *city, *loc_x, *loc_y;
CSint **QR, **DIST, *cost;
/**************************************************************************/
int criteria(int index, int val){
// return val;
int x0, y0, x1, y1, dx, dy;
x0 = index == 0 ? loc_x[val] : loc_x[cs_getValue(QR[index - 1])];
y0 = index == 0 ? loc_y[val] : loc_y[cs_getValue(QR[index - 1])];
x1 = loc_x[val]; y1 = loc_y[val];
dx = x1 -x0; dy = y1 -y0;
return (int)(100.0 * sqrt*1
return i;
}
return -1;
}
/**************************************************************************/
IZBOOL My_cs_minimize(CSint **allvars, int nbVars, CSint* (*findFreeVar)(CSint **allvars, int nbVars),
CSint *cost, void (*found)(CSint **allvars, int nbVars, CSint *cost)) {
char gFirst, g;

// gFirst = g = cs_search(allvars, nbVars, findFreeVar);
gFirst = g = cs_searchCriteria(allvars, nbVars, findFreeVarIndex, criteria);

while (g) {
int currentCost = cs_getMin(cost);
found(allvars, nbVars, cost);
cs_restoreAll();
// g = (cs_LT(cost, currentCost) && cs_search(allvars, nbVars, findFreeVar));
g = (cs_LT(cost, currentCost) && cs_searchCriteria(allvars, nbVars, findFreeVarIndex, criteria));
}
return gFirst;
}
/**************************************************************************/
void printSolution(CSint **allvars, int nbVars, CSint *cost) {
int i, val;
char sep;
static int NbSolutions = 0;

if (DISP == 0){
printf("Solution %3d : ", ++NbSolutions);

printf("%3d:", cs_getValue(cost));
for (i = 0; i < nbVars; i++) {
val = cs_getValue(allvars[i]);
if*2;
for (i = 0; i < nbVars; i++) {
val = cs_getValue(allvars[i]);
if*3;
for (i = 0; i < DIM*DIM; i++) {
board[i] = -1;
}
int n = 0;
for (i = 0; i < nbVars; i++) {
board[city[cs_getValue(allvars[i])]] = n++;
}
for (i = 0; i < DIM*DIM; i++) {
if(board[i] == -1){
printf("%3c", '.');
}
else {
printf("%3d", board[i]);
}
if*4;

DISP = atoi(argv[1]);
CITY_N = argc - 2;
city=(int *)malloc(CITY_N * sizeof(int));
loc_x=(int *)malloc(CITY_N * sizeof(int));
loc_y=(int *)malloc(CITY_N * sizeof(int));
for(i = 0; i < CITY_N; i++){
city[i] = atoi(argv[2 + i]);
loc_x[i] = city[i] % DIM;
loc_y[i] = city[i] / DIM;
}

QR = (CSint **)malloc(CITY_N * sizeof(CSint *));
DIST = (CSint **)malloc(CITY_N * sizeof(CSint *));

for(i = 0; i < CITY_N; i++){
QR[i] = cs_createCSint(0, CITY_N - 1);
}

CSint *CITY_X0, *CITY_X1, *CITY_Y0, *CITY_Y1;
CSint *DIS_X, *DIS_Y;
for(i = 0; i < CITY_N; i++){
CITY_X0 = cs_Element(QR[(i == 0 ? CITY_N : i) - 1], &loc_x[0], CITY_N);
CITY_Y0 = cs_Element(QR[(i == 0 ? CITY_N : i) - 1], &loc_y[0], CITY_N);
CITY_X1 = cs_Element(QR[i], &loc_x[0], CITY_N);
CITY_Y1 = cs_Element(QR[i], &loc_y[0], CITY_N);
DIS_X = cs_Sub(CITY_X1, CITY_X0);
DIS_Y = cs_Sub(CITY_Y1, CITY_Y0);
DIST[i] = cs_Add(cs_Mul(DIS_X,DIS_X), cs_Mul(DIS_Y, DIS_Y));
cs_GT(DIST[i], 0);
}

cs_AllNeq(&QR[0], CITY_N);
cost = cs_Sigma(&DIST[0], CITY_N);

cs_printf("QR: %A\n", QR, CITY_N);
cs_printf("DIST: %A\n", DIST, CITY_N);

if (DISP == 1){
printf("\033[2J\033[0;0f"); // clear screen
}

// cs_findAll(&CELL[0], DIM*DIM, cs_findFreeVarNbConstraints, printSolution);
// cs_minimize(&QR[0], CITY_N, cs_findFreeVar, cost, printSolution);
// cs_minimize(&QR[0], CITY_N, cs_findFreeVarNbConstraints, cost, printSolution);
My_cs_minimize(&QR[0], CITY_N, cs_findFreeVarNbElements, cost, printSolution);

cs_printStats();
printf("Elapsed Time = %g s\n", (double) (clock() - t0) / CLOCKS_PER_SEC);
time(&nowtime); printf("%s", ctime(&nowtime));
cs_end();
return EXIT_SUCCESS;
}

*1:double)(dx*dx + dy*dy)));
// return dx*dx + dy*dy;
}
/**************************************************************************/
int findFreeVarIndex(CSint **allvars, int nbVars) {
for (int i = 0; i < nbVars; i++) {
// for (int i = nbVars - 1; i >= 0; i--) {
if (cs_isFree(allvars[i]

*2:i+1) % nbVars == 0) sep = '\n';
else sep = ',';
printf("%3d%c", city[val], sep);
}
}
else {
printf("\033[0;0f");
printf("\nSolution %3d\n", ++NbSolutions);
printf("%3d: ", cs_getValue(cost

*3:i+1) % nbVars == 0) sep = '\n';
else sep = ',';
printf("%3d%c", city[val], sep);
}
int *board =(int *)malloc(DIM*DIM * sizeof(int

*4:i+1) % DIM == 0) putchar('\n');
}
}
}
/**************************************************************************/
/**************************************************************************/
int main(int argc, char **argv) {
int i;
clock_t t0 = clock();
time_t nowtime;

cs_init();
time(&nowtime); printf("%s", ctime(&nowtime