/* gcc -g wf.cpp -o fw ワーシャル-フロイド法 (ダイクストラは個別ルートでは早いが、先に全ルート計算しておくなら、 こっちの方法の法が速いこともある) 参考：ゼオスTTのブログ http://zeosutt.hatenablog.com/entry/2015/05/05/045943 */ #include <stdio.h> int d[5][5]; // d[i][k]：ノードiからノードkへの距離 int via[5][5]; // d[i][k]の間にある(少くとも1つの)中継ノード // 中継パスの表示ルーチン(再帰呼出し用) void printPath1_aux(int begin, int end) { if (via[begin][end] == begin) { if (begin != end) printf("%d -> ", begin); return; } printPath1_aux(begin, via[begin][end]); printPath1_aux(via[begin][end], end); } // 中継パスの表示ルーチン void printPath1(int start, int goal) { printPath1_aux(start, via[start][goal]); printPath1_aux(via[start][goal], goal); printf("%d\n", goal); } int main(void) { // 変数の初期化 for(int i = 0; i < 5; i++){ for(int j = 0; j < 5; j++){ d[i][j] = 99999999; // 距離の初期化(でっかい値を入力しておく(INT_MAXは足し算の時に桁上がりが起こるので使わない) via[i][j] = i; // ノードiからノードkへの経由値の初期化 } } // 確認用の表示 printf("\n[STEP1]\n"); for(int i = 0; i < 5; i++){ for(int k = 0; k < 5; k++){ printf("d[%d][%d]):%d\t",i,k,d[i][k]); printf("via[%d][%d]):%d\n",i,k,via[i][k]); } } //// ここからは実際の距離を手書き for(int i = 0; i < 5; i++){ d[i][i] = 0; //// 同じノードへの距離は0になるので、上書き } d[0][2] = 1; // ノード0からノード2までの距離 1 を上書き d[2][0] = 1; // その逆順(さぼってはダメ) d[0][1] = 2; // ノード0からノード1までの距離 2 を上書き d[1][0] = 2; // その逆順 d[0][4] = 6; d[4][0] = 6; d[1][2] = 4; d[2][1] = 4; d[2][3] = 4; d[3][2] = 4; d[3][4] = 2; d[4][3] = 2; // 確認用の表示 printf("\n[STEP2]\n"); for(int i = 0; i < 5; i++){ for(int k = 0; k < 5; k++){ printf("d[%d][%d]):%d\t",i,k,d[i][k]); printf("via[%d][%d]):%d\n",i,k,via[i][k]); } } // 経路長計算 for (int k =0; k < 5; k++){ for (int i =0; i < 5; i++){ for(int j = 0; j < 5; j++){ if(d[i][j] > d[i][k] + d[k][j]){ d[i][j] = d[i][k] + d[k][j]; via[i][j] = k; //更新処理 } } } } // 計算結果 printf("\n[STEP3]\n"); for(int i = 0; i < 5; i++){ for(int k = 0; k < 5; k++){ printf("d[%d][%d]):%d\t",i,k,d[i][k]); printf("via[%d][%d]):%d\n",i,k,via[i][k]); } } // 経路パス表示 printf("\n[Path]\n"); for(int i = 0; i < 5; i++){ for(int k = 0; k < 5; k++){ printf("d[%d][%d]: ",i,k); printPath1(i, k); } } }
/* gcc -g wf3.cpp -o fw3 ワーシャル-フロイド法(その3) スタックオーバーフローが怖いのと処理が遅くなりそうなので、「再帰呼出し」を使わない方法 (http://www.kobore.net/diary_techno/?date=20180306) 参考：ゼオスTTのブログ http://zeosutt.hatenablog.com/entry/2015/05/05/045943 */ #include <stdio.h> int d[5][5]; // d[i][k]：ノードiからノードkへの距離 int next[5][5]; // ノードi から ノードj への最短経路における i の1つ後のノード int main(void) { // 変数の初期化 for(int i = 0; i < 5; i++){ for(int j = 0; j < 5; j++){ d[i][j] = 99999999; // 距離の初期化(でっかい値を入力しておく(INT_MAXは足し算の時に桁上がりが起こるので使わない) next[i][j] = j; // ノードi から ノードj への最短経路における i の1つ後のノード } } // 確認用の表示 printf("\n[STEP1]\n"); for(int i = 0; i < 5; i++){ for(int k = 0; k < 5; k++){ printf("d[%d][%d]):%d\t",i,k,d[i][k]); printf("next[%d][%d]):%d\n",i,k,next[i][k]); } } //// ここからは実際の距離を手書き for(int i = 0; i < 5; i++){ d[i][i] = 0; //// 同じノードへの距離は0になるので、上書き } d[0][2] = 1; // ノード0からノード2までの距離 1 を上書き d[2][0] = 1; // その逆順(さぼってはダメ) d[0][1] = 2; // ノード0からノード1までの距離 2 を上書き d[1][0] = 2; // その逆順 d[0][4] = 6; d[4][0] = 6; d[1][2] = 4; d[2][1] = 4; d[2][3] = 4; d[3][2] = 4; d[3][4] = 2; d[4][3] = 2; // 確認用の表示 printf("\n[STEP2]\n"); for(int i = 0; i < 5; i++){ for(int k = 0; k < 5; k++){ printf("d[%d][%d]):%d\t",i,k,d[i][k]); printf("next[%d][%d]):%d\n",i,k,next[i][k]); } } // 経路長計算 for (int k =0; k < 5; k++){ for (int i =0; i < 5; i++){ for(int j = 0; j < 5; j++){ if(d[i][j] > d[i][k] + d[k][j]){ d[i][j] = d[i][k] + d[k][j]; next[i][j] = next[i][k]; //更新処理 } } } } // 計算結果 printf("\n[STEP3]\n"); for(int i = 0; i < 5; i++){ for(int k = 0; k < 5; k++){ printf("d[%d][%d]):%d\t",i,k,d[i][k]); printf("next[%d][%d]):%d\n",i,k,next[i][k]); } } // 経路パス表示 printf("\n[Path]\n"); for(int i = 0; i < 5; i++){ for(int k = 0; k < 5; k++){ int cur; printf("d[%d][%d]: ",i,k); for (cur = i; cur != k; cur = next[cur][k]){ printf("%d -> ", cur); } printf("%d\n", k); } } }
■ダイクストラ法 開始時間:82[ms] 終了時間:33139[ms] ■ワーシャル-フロイド法(その3) 開始時間:84[ms] 終了時間:91[ms] 速度比率 4722.428571 倍
/* gcc -g ql_test.cpp -o ql_test 強化学習(Q-Learning)を理解する為に、中学→高校→大学の学歴を使ってみた */ #include <stdio.h> #include <stdlib.h> typedef enum period{ BIRTH = 0, JUNIOR_HIGH = 1, HIGH = 2, COLLEGE = 3, SUPER_COLLEGE = 4 }PERIOD; typedef struct state{ struct state* future_state[2]; // 未来へのパス(取り敢えず2つほど) PERIOD period; int q; }STATE; STATE* change_state(STATE* p_state) { if ((double)rand()/RAND_MAX < 0.3){ // ε:0.3 if ((double)rand()/RAND_MAX < 0.5){ // 半々 return p_state->future_state[0]; } else{ return p_state->future_state[1]; } } else { if (p_state->future_state[0]->q > p_state->future_state[1]->q){ return p_state->future_state[0]; } else{ return p_state->future_state[1]; } } } void q_renewal(STATE* p_state) { int dummy_q; if (p_state->period == SUPER_COLLEGE){ p_state->q += 0.1 * (1000- p_state->q); // α:0.1 報酬の源泉:年収1000万円 } else if (p_state->period != COLLEGE){ if (p_state->future_state[0]->q > p_state->future_state[1]->q){ dummy_q = p_state->future_state[0]->q; } else { dummy_q = p_state->future_state[1]->q; } p_state->q += 0.1 * (0.9 * dummy_q - p_state->q); // α:0.1 γ:0.9 } return; } void q_display(STATE* p_state) { for (int i =0; i < 15 ; i++){ printf("%d,", p_state->q); p_state++; } printf("\n"); return; } int main() { srand(13); // 初期設定 //STATE* state; STATE state[15]; state[0].period = BIRTH; state[0].future_state[0] = &(state[1]); state[0].future_state[1] = &(state[2]); state[1].period = JUNIOR_HIGH; state[1].future_state[0] = &(state[3]); state[1].future_state[1] = &(state[4]); state[2].period = JUNIOR_HIGH; state[2].future_state[0] = &(state[5]); state[2].future_state[1] = &(state[6]); state[3].period = HIGH; state[3].future_state[0] = &(state[7]); state[3].future_state[1] = &(state[8]); state[4].period = HIGH; state[4].future_state[0] = &(state[9]); state[4].future_state[1] = &(state[10]); state[5].period = HIGH; state[5].future_state[0] = &(state[11]); state[5].future_state[1] = &(state[12]); state[6].period = HIGH; state[6].future_state[0] = &(state[13]); state[6].future_state[1] = &(state[14]); state[7].period = COLLEGE; state[8].period = COLLEGE; state[9].period = COLLEGE; state[10].period = SUPER_COLLEGE; state[11].period = COLLEGE; state[12].period = COLLEGE; state[13].period = COLLEGE; state[14].period = COLLEGE; for (int i = 0; i < 15; i++){ state[i].q = (int)rand() % 100; } printf("誕生,A中学,B中学,C高校,D高校,E高校,F高校,G大学,H大学,I大学,J大学,K大学,L大学,M大学,N大学\n"); STATE* s = state; //q_display(s); q_display(state); for (int i = 0; i < 1000; i++){ // 300:学習回数 STATE* s = state; // 初期値に戻しているだけ do{ s = change_state(s); q_renewal(s); }while( (s->period != COLLEGE) && (s->period != SUPER_COLLEGE)); q_display(state); } printf("\n[after]\n"); //q_display(s); q_display(state); }
/* google Mapの座標値から距離を求めるルーチン 2018-03-21(水) 14:41:31 gcc -c location_calc.cpp */ #include <math.h> typedef struct location{ // ちなみに X,Y 軸座標は、→に＋ ↑に＋ double longitude; // 経度 東経 139.691 X軸 double latitude; // 緯度 北緯 35.698 Y軸 } LOCATION; #define rad2deg(a) ((a)/M_PI * 180.0) /* rad を deg に換算するマクロ関数 */ #define deg2rad(a) ((a)/180.0 * M_PI) /* deg を rad に換算するマクロ関数 */ double distance_km(LOCATION* A, LOCATION* B, double *rad_up) { double earth_r = 6378.137; double loRe = deg2rad(B->longitude - A->longitude); // 東西 double laRe = deg2rad(B->latitude - A->latitude); // 南北 double EWD = cos(deg2rad(A->latitude))*earth_r*loRe; // 東西距離 double NSD = earth_r*laRe; //南北距離 double distance = sqrt(pow(NSD,2)+pow(EWD,2)); *rad_up = atan2(NSD, EWD); return distance; } LOCATION* new_location(LOCATION* D, double diff_p_x, double diff_p_y) { double earth_r = 6378.137; double loRe = diff_p_x / earth_r / cos(deg2rad(D->latitude)); // 東西 double laRe = diff_p_y / earth_r; // 南北 double diff_lo = rad2deg(loRe); // 東西 double diff_la = rad2deg(laRe); // 南北 static LOCATION C; C.longitude = D->longitude + diff_lo; // 東西 C.latitude = D->latitude + diff_la; // 南北 return &C; } double diff_longitude(double diff_p_x, double latitude) { double earth_r = 6378.137; // ↓ これが正解だけど、 double loRe = diff_p_x / earth_r / cos(deg2rad(latitude)); // 東西 // 面倒なので、これで統一しよう(あまり差が出ないしね) //double loRe = diff_p_x / earth_r / cos(deg2rad(35.700759)); // 東西 double diff_lo = rad2deg(loRe); // 東西 return diff_lo; // 東西 } double diff_latitude(double diff_p_y) { double earth_r = 6378.137; double laRe = diff_p_y / earth_r; // 南北 double diff_la = rad2deg(laRe); // 南北 return diff_la; // 南北 }