このプログラムは、複数の沢山ある経路(ベクトル)が存在している時に、ある出発点と終着点(ベクトル)を与えた時に、沢山ある経路を繋いで、出発から終着までを繼ぐ複数の経路を選びだすプログラムである。 ベクトルは、緯度、軽度、時間 の出発と到着を示す6要素で示される 3次元ベクトルである。 現時点のこのプログラムでは、緯度、軽度、時間は100x100x100の 格子状のいずれかの2点を結んで、ベクトルとしている。 プログラムは以下のようになっている。 [Step.1] まず1000～5000くらの経路ベクトルを乱数で作る [Step.2] 出発と到着のベクトル(旅程ベクトル)を一つ作る(ここでは乱数で) [Step.3] 旅程ベクトルに近い経路ベクトルを一つ選ぶ [Step.4] 旅程ベクトルの両端のベクトル(ここでは2つできる)を新しい旅程 ベクトルとして、経路ベクトルを選ぶ→ これを、選べる経路ベクトルがなくなるまで、繰り返す。 [Step.5] このようにして選び出された経路ベクトルを、出発から近い順番に表示する高速化と省メモリもあるが、それ以上に、最終的に経路ベクトルがいくつ選択されるのか分からないので、すべて動的メモリを使っている。 その為、処理が恐しく面倒くさい それと、ベクトルが視認できないと、訳が分からんので、とても簡単な3Dルーチンも作ってある。 「こんなもの、もう二度と作りたくないので、今のうちに退避しておく」
/* gcc 2_simple_sa.c -o 2_simple_sa -lm */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> float distance(int *point1, int *point2) { int dx = point1[0] - point2[0], dy = point1[1] - point2[1]; return sqrt(dx * dx + dy * dy); } float totalDistance(int **points, int length) { int i; float total = 0.0; for (i = 1; i < length; i++) { total += distance(points[i], points[i - 1]); } total += distance(points[0], points[length - 1]); return total; } void swap(int **array, int index1, int index2) { int *tmp; tmp = array[index1]; array[index1] = array[index2]; array[index2] = tmp; } float frand() { return (float)rand()/(float)RAND_MAX; } int shouldChange(float delta, float t) { if (delta <= 0) return 1; if (frand() < exp(- delta / t)) return 1; return 0; } void sa(int **route, int numberOfCities, float initialT, float finalT, int n, float coolingRate) { int currentIterations, randomIndex1, randomIndex2, i; float t, currentTotalDistance, newTotalDistance; currentTotalDistance = totalDistance(route, numberOfCities); for (t = initialT; t > finalT; t *= coolingRate) { for (i = 0; i < n; i++) { randomIndex1 = rand() % numberOfCities; randomIndex2 = rand() % numberOfCities; swap(route, randomIndex1, randomIndex2); newTotalDistance = totalDistance(route, numberOfCities); if (shouldChange(newTotalDistance - currentTotalDistance, t)) { currentTotalDistance = newTotalDistance; } else { swap(route, randomIndex1, randomIndex2); } } } } int **buildRoute(int mapData[][2], int numberOfCities) { int **route = calloc(numberOfCities, sizeof(&mapData[0][0])), i; for (i = 0; i < numberOfCities; i++) { route[i] = mapData[i]; } return route; } void printJSONRoute(int **route, int numberOfCities) { int i; printf("[\n"); for (i = 0; i < numberOfCities - 1; i++) { printf(" [%d, %d],\n", route[i][0], route[i][1]); } printf(" [%d, %d]\n", route[i][0], route[i][1]); printf("]\n"); } int main(void) { int n = 1000, numberOfCities = 51, mapData[][2] = {{37,52},{49,49},{52,64},{20,26},{40,30},{21,47},{17,63},{31,62},{52,33},{51,21},{42,41},{31,32},{5,25},{12,42},{36,16},{52,41},{27,23},{17,33},{13,13},{57,58},{62,42},{42,57},{16,57},{8,52},{7,38},{27,68},{30,48},{43,67},{58,48},{58,27},{37,69},{38,46},{46,10},{61,33},{62,63},{63,69},{32,22},{45,35},{59,15},{5,6},{10,17},{21,10},{5,64},{30,15},{39,10},{32,39},{25,32},{25,55},{48,28},{56,37},{30,40}}, **route = buildRoute(mapData, numberOfCities); float initialT = 100.0, finalT = 0.8, coolingRate = 0.9; srand((unsigned)time(NULL)); printf("%f\n", totalDistance(route, numberOfCities)); sa(route, numberOfCities, initialT, finalT, n, coolingRate); printf("%f\n", totalDistance(route, numberOfCities)); printJSONRoute(route, numberOfCities); return 0; }