欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標題: 關于尋求最短路徑的一種算法、附件為算法的C/C++實現,歡迎下載 [打印本頁]
作者: ahyl    時間: 2019-5-17 11:25
標題: 關于尋求最短路徑的一種算法、附件為算法的C/C++實現,歡迎下載
最短路徑尋優

（以下關于Dijstra的說明，是借用算法與數據結構的發帖說明、侵權即刪）原帖鏈接最短路徑尋優如上圖所示、如何尋求從 A 出發到 G 點的最短路徑呢？Dijstra算法就是要求出這個最短的路徑；

讓我們來演示一下迪杰斯特拉的詳細過程：        第1步，創建距離表。表中的Key是頂點名稱，Value是從起點A到對應頂點的已知最短距離。        但是，一開始我們并不知道A到其他頂點的最短距離是多少，Value默認是無限大：

第2步，遍歷起點A，找到起點A的鄰接頂點B和C。從A到B的距離是5，從A到C的距離是2。把這一信息刷新到距離表當中：

第3步，從距離表中找到從A出發距離最短的點，也就是頂點C。第4步，遍歷頂點C，找到頂點C的鄰接頂點D和F（A已經遍歷過，不需要考慮�。。。。。。。。�！代碼編寫中就需要注意這一點）。從C到D的距離是6，所以A到D的距離是2+6=8；從C到F的距離是8，所以從A到F的距離是2+8=10。把這一信息刷新到表中：

接下來重復第3步、第4步所做的操作：第5步，也就是第3步的重復，從距離表中找到從A出發距離最短的點（C已經遍歷過，不需要考慮），也就是頂點B。第6步，也就是第4步的重復，遍歷頂點B，找到頂點B的鄰接頂點D和E（A已經遍歷過，不需要考慮）。從B到D的距離是1，所以A到D的距離是5+1=6，小于距離表中的8；從B到E的距離是6，所以從A到E的距離是5+6=11。把這一信息刷新到表中：

（在第6步，A到D的距離從8刷新到6，可以看出距離表所發揮的作用。距離表通過迭代刷新，用新路徑長度取代舊路徑長度，最終可以得到從起點到其他頂點的最短距離）第7步，從距離表中找到從A出發距離最短的點（B和C不用考慮），也就是頂點D。第8步，遍歷頂點D，找到頂點D的鄰接頂點E和F。從D到E的距離是1，所以A到E的距離是6+1=7，小于距離表中的11；從D到F的距離是2，所以從A到F的距離是6+2=8，小于距離表中的10。把這一信息刷新到表中：

第9步，從距離表中找到從A出發距離最短的點，也就是頂點E。第10步，遍歷頂點E，找到頂點E的鄰接頂點G。從E到G的距離是7，所以A到G的距離是7+7=14。把這一信息刷新到表中：

第11步，從距離表中找到從A出發距離最短的點，也就是頂點F。第10步，遍歷頂點F，找到頂點F的鄰接頂點G。從F到G的距離是3，所以A到G的距離是8+3=11，小于距離表中的14。把這一信息刷新到表中：

就這樣，除終點以外的全部頂點都已經遍歷完畢，距離表中存儲的是從起點A到所有頂點的最短距離。顯然，從A到G的最短距離是11。（路徑：A-B-D-F-G）
下面附上算法的C++實現
  1. // dijstra.cpp : 此文件包含 "main" 函數。程序執行將在此處開始并結束。
  2. //
  3. //利用狀態機來描述 dijstra算法
  4. //尋求最短路徑


  7. #include "pch.h"
  8. #include <iostream>

  10. using namespace std;

  12. typedef struct {
  13.         char nextPointName;
  14.         int  distance;
  15. }NEXT_POINT;

  17. typedef struct {
  18.         int                curVaule;
  19.         int                expandFlag;
  20.         char        name;
  21.         int                linkNum;
  22.         NEXT_POINT  nextPoint[5];
  23.         char        route[10] = {'A'};
  24. }POINT;

  26. POINT A = { 1000,0,'A' ,2,'B',5,'C',2};
  27. POINT B = { 1000,0,'B' ,2,'D',1,'E',6};
  28. POINT C = { 1000,0,'C' ,2,'D',6,'F',8};
  29. POINT D = { 1000,0,'D' ,2,'E',1,'F',2};
  30. POINT E = { 1000,0,'E' ,1,'G',7};
  31. POINT F = { 1000,0,'F' ,1,'G',3};
  32. POINT G = { 1000,0,'G' };


  35. void Dijkstra(POINT* startPoint, POINT* endPoint, POINT* piontArray, int pointNum);
  36. int main()
  37. {
  38.         POINT array[10] = { A,B,C,D,E,F,G };
  39.         Dijkstra(&A,&G,array,7);
  40.        
  41.         cout << "        最短路徑為        "<<G.route <<endl<<"        最短路徑長度為        "<< G.curVaule  << endl;
  42.         system("pause");
  43. }

  45. void Dijkstra(POINT* startPoint, POINT* endPoint, POINT* piontArray,int pointNum) {
  46.        
  47.         POINT unexpandPoint[20] = {0};
  48.        
  49.         int leftNum = pointNum;
  50.         POINT expandPoint=*(startPoint);       
  51.         int temp = 0;

  53.         for (int i = 0; i < pointNum; ++i) {
  54.                 unexpandPoint[i] = piontArray[i];
  55.         }
  56.         unexpandPoint[0].curVaule = 0;

  58.         while (1) {
  59.                 expandPoint = unexpandPoint[0];
  60.                 for (int i = 0; i < leftNum; ++i) {
  61.                         if (expandPoint.curVaule > unexpandPoint[i].curVaule) {
  62.                                 expandPoint = unexpandPoint[i];
  63.                                 temp = i;
  64.                         }
  65.                 }
  66.                 if (expandPoint.name == endPoint->name) {
  67.                         *(endPoint) = expandPoint;

  69.                         break;
  70.                 }       
  71.                 for (int i = 0; i < leftNum; ++i) {
  72.                         if (i > temp) {
  73.                                 unexpandPoint[i - 1] = unexpandPoint[i];
  74.                         }       
  75.                 }
  76.                 temp = 0;
  77.                 leftNum--;
  78.                 for (int i = 0; i < expandPoint.linkNum; ++i) {       
  79.                         for (int j = 0; j < leftNum; ++j) {
  80.                                 if (expandPoint.nextPoint[i].nextPointName == unexpandPoint[j].name) {
  81.                                         if (unexpandPoint[j].curVaule > expandPoint.nextPoint[i].distance + expandPoint.curVaule) {
  82.                                                 unexpandPoint[j].curVaule = expandPoint.nextPoint[i].distance+ expandPoint.curVaule;                                       
  83.                                         }
  84.                                         if (unexpandPoint[j].curVaule > 1000) {
  85.                                                 unexpandPoint[j].curVaule -= 1000;
  86.                                        
  87.                                         }

  89.                                         //路徑更新
  90.                                         for (int k = 0; k < 10; ++k) {
  91.                                                 unexpandPoint[j].route[k] = 0;                                                               
  92.                                         }
  93.                                         for (int k = 0; k < 10; ++k) {
  94.                                                 if (expandPoint.route[k] != 0) {
  95.                                                         unexpandPoint[j].route[k] = expandPoint.route[k];
  96.                                                 }
  97.                                                 else {
  98.                                                         unexpandPoint[j].route[k] = unexpandPoint[j].name;
  99.                                                         break;
  100.                                                 }
  101.                                         }                                                       
  102.                                 }                       
  103.                         }                                       
  104.                 }               

  106.         }
  107. }
  108. #if 0
  109. ##網上查找到的關于 dajstra 算法的較精簡的代碼例程

  111. #include<iostream>
  112. #include<cstring>
  113. #define INF 10000000
  114. using namespace std;
  115. int temp[2005][2005], dis[1005];
  116. void dijkstra(int n)
  117. {
  118.         int i, min, flag, j, vis[2005] = { 0 };
  119.         for (i = 1; i <= n; i++) dis[i] = temp[1][i];
  120.         for (i = 1; i < n; i++)
  121.         {
  122.                 min = INF;
  123.                 flag = 0;
  124.                 for (j = 2; j <= n; j++)
  125.                         if (min > dis[j] && !vis[j])
  126.                         {
  127.                                 min = dis[j];
  128.                                 flag = j;
  129.                         }
  130.                 vis[flag] = 1;
  131.                 for (j = 2; j <= n; j++)
  132.                 {
  133.                         if (dis[j] > min + temp[flag][j] && !vis[j])
  134.                                 dis[j] = min + temp[flag][j];
  135.                 }
  136.         }
  137. }
  138. int main()
  139. {
  140.         int t, i, n, k, m, diss;
  141.         while (cin >> t >> n)
  142.         {
  143.                 //memset(temp,INF,sizeof(temp));
  144.                 for (int i = 1; i <= 2000; i++) temp[i][i] = 0;
  145.                 for (int i = 1; i <= 2000; i++)
  146.                         for (int j = 1; j <= 2000; j++)
  147.                                 temp[i][j] = INF;
  148.                 for (int i = 1; i <= t; i++)
  149.                 {
  150.                         cin >> k >> m >> diss;
  151.                         if (diss < temp[k][m])
  152.                         {
  153.                                 temp[k][m] = diss;//雙向導通
  154.                                 temp[m][k] = diss;
  155.                         }
  156.                 }
  157.                 dijkstra(n);
  158.                 //for(int i=1;i<=t;i++) cout<<dis[i]<<endl;
  159.                 cout << dis[n] << endl;
  160.         }
  161.         return 0;
  162. }
  163. #endif

  165. typedef struct {
  166.         float x[2];     /* state: [0]-angle [1]-diffrence of angle, 2x1 */
  167.         float A[2][2];  /* X(n)=A*X(n-1)+U(n),U(n)~N(0,q), 2x2 */
  168.         float H[2][2];     /* Z(n)=H*X(n)+W(n),W(n)~N(0,r), 1x2   */
  169.         float q[2];     /* process(predict) noise convariance,2x1 [q0,0; 0,q1] */
  170.         float r[2][2];        /* measure noise convariance */
  171.         float p[2][2];  /* estimated error convariance,2x2 [p0 p1; p2 p3] */
  172.         float gain[2][2];  /* 2x1 */
  173.         float B[2];
  174. } kalman2_state;

  176. //z軸kalman濾波初始化，初始化時用
  177. // kalman2_init(&BaroAlt_klm);
  178. //輸入氣壓計高度，速度和慣性坐標下的加速度---------輸出高度和速度
  179. // kalman2_filter(&BaroAlt_klm, BaroAltoo, 0, az_c);

  181. void kalman2_init(kalman2_state *state)//, float *init_x, float (*init_p)[2]//×îºóÖ»Ðèµ÷ÊÔq[0],q[1];
  182. {
  183.         //    state->x[0]    = init_x[0];
  184.         //    state->x[1]    = init_x[1];
  185.         //    state->p[0][0] = init_p[0][0];
  186.         //    state->p[0][1] = init_p[0][1];
  187.         //    state->p[1][0] = init_p[1][0];
  188.         //    state->p[1][1] = init_p[1][1];
  189.         state->x[0] = 0;
  190.         state->x[1] = 0;
  191.         state->p[0][0] = 1;
  192.         state->p[0][1] = 0;
  193.         state->p[1][0] = 0;
  194.         state->p[1][1] = 1;
  195.         //          state->A       = {{1, 0.1}, {0, 1}};
  196.         state->A[0][0] = 1;
  197.         state->A[0][1] = 0.01;//1;//t¿É±ä  Á½¸öÎïÀíʱ¿ÌµÄ²î2ms      PID_PIT.I*0.27;//0.0027
  198.         state->A[1][0] = 0;
  199.         state->A[1][1] = 1;
  200.         //          state->H       = {1,0};
  201.         state->H[0][0] = 1;
  202.         state->H[0][1] = 0;//1
  203.         state->H[1][0] = 0;
  204.         state->H[1][1] = 0;
  205.         //    state->q       = {{10e-6,0}, {0,10e-6}};  /* measure noise convariance */               
  206.         state->q[0] = 5 * 10e-8;//5;//0.0001;//10e-7;//10e-7;
  207.         state->q[1] = 5 * 10e-8;//10e-6;//0.5;//0.0035;//5*10e-7;
  208.         state->r[0][0] = 1 * 10e-7;//10e-4;//52.4586;//0.1;//10e-3;//10e-7;  /* estimated error convariance */PID_ROL.D*
  209.         state->r[0][1] = 0;
  210.         state->r[1][0] = 0;
  211.         state->r[1][1] = 4 * 10e-4;
  212.         //    state->B               
  213.         state->B[0] = state->A[0][1] * state->A[0][1] / 2.0;
  214.         state->B[1] = state->A[0][1];
  215. }

  217. float kalman2_filter(kalman2_state *state, float x_weiyi, float x_speed, float a)//£¨¶þά¿¨¶ûÂüÂ˲¨£©Ö»±äÒ»¸ö£¬Ðè¸Ä½øλÒÆ¡¢ËÙ¶È,ÕæÕýµÄ¼ÓËٶȣ¨Ð޸ĺó£©
  218. {
  219.         float temp0 = 0.0f;
  220.         float temp1 = 0.0f;
  221.         float temp0_0 = 0.0f;
  222.         float temp0_1 = 0.0f;
  223.         float temp1_0 = 0.0f;
  224.         float temp1_1 = 0.0f;
  225.         float temp00 = 0.0f;
  226.         float temp01 = 0.0f;
  227.         float temp10 = 0.0f;
  228.         float temp11 = 0.0f;

  230.         /* Step1: Predict X(k+1)= A*X(k) +B*U(k)*/
  231.         state->x[0] = state->A[0][0] * state->x[0] + state->A[0][1] * state->x[1] + state->B[0] * a;//ת»»Íê×ø±ê·½¿ÉʹÓÃ
  232.         state->x[1] = state->A[1][0] * state->x[0] + state->A[1][1] * state->x[1] + state->B[1] * a;
  233.         /* Step2: Covariance Predict P(k+1)=A*P(k)*(A^T)+Q;*/
  234.         state->p[0][0] = (state->p[0][0] + state->p[1][0] * state->A[0][1]) + (state->p[0][1] + state->p[1][1] * state->A[0][1])*state->A[0][1] + state->q[0];
  235.         state->p[0][1] = state->p[0][1] + state->p[1][1] * state->A[0][1];//+state->q[0];
  236.         state->p[1][0] = state->p[1][0] + state->p[1][1] * state->A[0][1];//+state->q[1];
  237.         state->p[1][1] = state->p[1][1] + state->q[1];
  238.         /* Step3: Gain Measurement : gain = p * H^T * [r + H * p * H^T]^(-1), H^T means transpose.  µÚÈý¸ö¹«Ê½×ª»»*/
  239.         temp0_0 = (state->p[0][0] + state->r[0][0])*(state->p[1][1] + state->r[1][1]) - (state->p[0][1] + state->r[0][1])*(state->p[1][0] + state->r[1][0]);//ÕýÈ·//r¶Ô½ÇÕó
  240.         temp0_1 = (state->p[0][0] + state->r[0][0])*(state->p[1][1] + state->r[1][1]) - (state->p[0][1] + state->r[0][1])*(state->p[1][0] + state->r[1][0]);
  241.         temp1_0 = (state->p[0][0] + state->r[0][0])*(state->p[1][1] + state->r[1][1]) - (state->p[0][1] + state->r[0][1])*(state->p[1][0] + state->r[1][0]);
  242.         temp1_1 = (state->p[0][0] + state->r[0][0])*(state->p[1][1] + state->r[1][1]) - (state->p[0][1] + state->r[0][1])*(state->p[1][0] + state->r[1][0]);
  243.         temp00 = state->p[1][1] / temp0_0;
  244.         temp01 = -state->p[0][1] / temp0_1;
  245.         temp10 = -state->p[1][0] / temp1_0;
  246.         temp11 = state->p[0][0] / temp1_1;
  247.         state->gain[0][0] = state->p[0][0] * temp00 + state->p[0][1] * temp10;
  248.         state->gain[0][1] = state->p[0][0] * temp01 + state->p[0][1] * temp11;
  249.         state->gain[1][0] = state->p[1][0] * temp00 + state->p[1][1] * temp10;
  250.         state->gain[1][1] = state->p[1][0] * temp01 + state->p[1][1] * temp11;
  251.         /* Step4: Status Update : x(n|n) = x(n|n-1) + gain(n) * [z_measure - H(n)*x(n|n-1)]*/
  252.         state->x[0] = state->x[0] + state->gain[0][0] * (x_weiyi - state->x[0]) + state->gain[0][1] * (x_speed - state->x[1]); //ΪºÎÖ»ÓÃÒ»¸ö²ÎÊý
  253.         state->x[1] = state->x[1] + state->gain[1][0] * (x_weiyi - state->x[0]) + state->gain[1][1] * (x_speed - state->x[1]);
  254.         /* Step5: Covariance Update p: p(n|n) = [I - gain * H] * p(n|n-1)  ¸üÐÂp*/
  255.         temp0 = state->p[0][0];
  256.         temp1 = state->p[0][1];
  257.         state->p[0][0] = (1 - state->gain[0][0]) * state->p[0][0] - (state->gain[0][1] * state->p[1][0]);
  258.         state->p[0][1] = (1 - state->gain[0][0]) * state->p[0][1] - (state->gain[0][1] * state->p[1][1]);
  259.         state->p[1][0] = (1 - state->gain[1][1]) * state->p[1][0] - state->gain[1][0] * temp0;//state->p[0][0]
  260.         state->p[1][1] = (1 - state->gain[1][1]) * state->p[1][1] - state->gain[1][0] * temp1;//state->p[0][1]

  262.         return 1;
  263. }
復制代碼
全部資料51hei下載地址：
Dijstra.rar (3 KB, 下載次數: 9)
作者: ahyl    時間: 2019-5-17 11:26
想不到編輯之后、會亂成這個樣子



歡迎光臨 (http://m.raoushi.com/bbs/) Powered by Discuz! X3.1