最近老師給了一個題目，說是研究一個正常矩陣任意概率置點概率下，雙向導通（x,y）的概率（要求有自然邊界條件，也就是可以從0->length-1），用代碼敲了一下demo，結果發現有個好有趣的結果：不同大小的矩陣，導通概率從某一個概率上升，點越多，上升程度越快（斜率越大），但是都會在（0.592...，35%個點導通）左右相交，符合ziff論文的結果。

　　其實這個結果是統計學的一個結果，不過我們還沒學概率論，這個神奇的結論我還不能證明（不過這個證明也之能證明二維的，對于三維以上只能通過模擬得出）。

　　這個結果對于不同的圖都有不同的結果，我模擬的這個是最簡單的圖（自然邊界條件矩形圖）。

　　下面是demo，沒有什么特別的算法，也就是DFS稍微優化一下。

1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 #include <time.h> 5 #define MARTIX_SIZE 256 6 #define NP 6 7 8 using namespace std; 9 10 typedef struct _tempset 11 { 12 bool flag;//是否被訪問過 13 bool dir_x;//規定x一個方向 14 bool dir_y;//規定x一個方向 15 bool is_dot;//是否是一個節點 16 }Set; 17 typedef struct _group 18 { 19 int particle_sum; 20 bool Link_px; 21 bool Link_py; 22 }Group; 23 typedef struct _temp_recur 24 { 25 int x, y, dir; 26 }T_Group; 27 typedef int Position; 28 29 void Inivilize(Set ***const, T_Group **const,Position **const,Position **const); 30 Set **ReFresh_Martix(Set **const, int *const, Position *const, Position *const, int); 31 void Draw_The_Gragh(Set **const); 32 void Destory(Set **const, T_Group *, Position *, Position *); 33 void If_Cls(void); 34 void Show(const int, const int, const int, const double,FILE *); 35 void DFS_Martix(Set **, const int, const int, T_Group *const, Group *, Position *const, Position *const); 36 37 static double poss[NP] = { 0.590, 0.5925, 0.5926, 0.5927, 0.5928, 0.5930}; 38 39 static pair<int,int>direction[4]; 40 41 void Inivilize(Set ***const martix_tmp, 42 T_Group **const G_Stack, Position **const Mark_x, Position **const Mark_y) 43 { 44 /*函數名: Inivilize 45 *調用者函數: void main(void) 46 *函數形參: martix_tmp（矩陣指針） 47 G_Stack（偽遞歸棧堆指針） 48 Mark_x，Mark_y（GPA優化的斷層標記數組指針） 49 *函數功能: 初始化 50 *返回值： 無 51 */ 52 *martix_tmp = (Set **)malloc(sizeof(Set *)*MARTIX_SIZE); 53 Set *Zone = (Set *)malloc(sizeof(Set)*MARTIX_SIZE*MARTIX_SIZE); 54 for (int i = 0; i < MARTIX_SIZE; i++) 55 (*martix_tmp)[i] = &Zone[i*MARTIX_SIZE]; 56 57 *G_Stack = (T_Group *)malloc(sizeof(T_Group)*MARTIX_SIZE*MARTIX_SIZE);//整形最大值 58 *Mark_x = (Position *)malloc(sizeof(Position)*MARTIX_SIZE); 59 *Mark_y = (Position *)malloc(sizeof(Position)*MARTIX_SIZE); 60 61 //............................................... 62 srand((unsigned)time(NULL)); 63 direction[0].first = -1; direction[0].second = 0; 64 direction[1].first = 1; direction[1].second = 0; 65 direction[2].first = 0; direction[2].second = -1; 66 direction[3].first = 0; direction[3].second = 1; 67 } 68 69 Set **ReFresh_Martix(Set **const Martix, int *const sum_particle, 70 Position *const Mark_x, Position *const Mark_y, int k) 71 { 72 /*函數名: ReFresh_Martix 73 *調用者函數: void main(void) 74 *函數形參: Martix（矩陣指針） 75 sum_particle（新產生的粒子數） 76 Mark_x，Mark_y（GPA優化的斷層標記數組指針） 77 k（以第k個概率產生點） 78 *函數功能: 給矩陣產生點，以及賦值 79 *返回值： Martix（矩陣指針） 80 */ 81 int tmp; 82 memset(Mark_x, 0, sizeof(Position)*MARTIX_SIZE); 83 memset(Mark_y, 0, sizeof(Position)*MARTIX_SIZE); 84 for (int i = 0; i < MARTIX_SIZE; i++) 85 { 86 for (int j = 0; j < MARTIX_SIZE; j++) 87 { 88 tmp = rand(); 89 Martix[i][j].flag = tmp < RAND_MAX * poss[k] ? 1 : 0; 90 Martix[i][j].dir_y = 0; Martix[i][j].dir_x = 0;//強行規定一個方向 91 Martix[i][j].is_dot = 0; 92 if (Martix[i][j].flag) 93 { 94 (*sum_particle)++; 95 Mark_x[j]++; Mark_y[i]++; 96 Martix[i][j].is_dot = 1; 97 } 98 } 99 } 100 return Martix; 101 } 102 103 void Destory(Set **const Martix, T_Group *G_Stack, Position *Mark_x, Position *Mark_y) 104 { 105 /*函數名: Destory 106 *調用者函數: void main(void) 107 *函數形參: Martix（矩陣指針） 108 G_Stack（偽遞歸棧堆指針） 109 Mark_x，Mark_y（GPA優化的斷層標記數組指針） 110 *函數功能: 銷毀 111 *返回值： 無 112 */ 113 free(Martix[0]);//去掉集體分配的首地址就可以了 114 free(Martix); 115 free(G_Stack);//銷毀遞歸棧堆 116 free(Mark_x); free(Mark_y);//銷毀點集 117 } 118 119 void If_Cls(void) 120 { 121 /*函數名: If_Cls 122 *調用者函數: void main(void) 123 *函數形參: 無 124 *函數功能: 詢問是否清屏 125 *返回值： 無 126 */ 127 char choice; 128 printf("Do you want to clean the screen?(Y or N)"); 129 while (1) 130 { 131 choice = getchar(); 132 if (choice == 'Y') 133 { 134 system("cls"); 135 return; 136 } 137 else if (choice == 'N') 138 return; 139 else 140 { 141 puts("Error Input!Please enter again!\n"); 142 fflush(stdin); 143 } 144 } 145 } 146 147 void Show(const int k, const int link_group_sum, const int loop, const double max_poss, FILE *fp) 148 { 149 /*函數名: Show 150 *調用者函數: void main(void) 151 *函數形參: k（以第k個概率產生點） 152 link_group_sum（聯通集團個數） 153 loop（循環次數） 154 max（聯通最大點個數） 155 p_sum（所有聯通集團的粒子總數） 156 fp（指向data.txt的文件指針） 157 *函數功能: 顯示當前概率集團信息，并且把數據寫入data.txt中 158 *返回值： 無 159 */ 160 puts("===============================================================================\n"); 161 printf("\a%cEcho %d:\nPossibility of %.4f\nThe linked graphs` sum is %d\nAccount for %.2f%% in %d graghs\n", 162 16, k + 1, poss[k], link_group_sum, 100 * (double)link_group_sum / (double)loop, loop); 163 printf("The possibility of(max linked points/sum points)accounts for %.2f%%\n", 100 * max_poss); 164 printf("\n"); 165 166 if (fp != NULL) 167 { 168 fprintf(fp, "===============================================================================\n"); 169 fprintf(fp, "%cEcho %d:\nPossibility of %.4f\nThe linked graphs` sum is %d\nAccount for %.2f%% in %d graghs\n", 170 7, k + 1, poss[k], link_group_sum, 100 * (double)link_group_sum / (double)loop, loop); 171 fprintf(fp, "The possibility of(max linked points/sum points)accounts for %.2f%%\n", 100 * max_poss); 172 fprintf(fp, "\n"); 173 } 174 } #include "plug.h"static bool x_full, y_full;int main(void)//森林火災項目的計算連通性的概率 {int loop, sum_particle, link_group_sum, max_particle_sum;double max_poss, poss_tmp; Set **martix = NULL; //矩陣 Group tmp; T_Group *G_Stack; //范圍太大，不用遞歸，手動直接開大棧提高效率Position *Mark_x = NULL, *Mark_y = NULL; //Gpa優化標記數組FILE *fp = NULL; //文件指針//......................................................................................Inivilize(&martix, &G_Stack, &Mark_x, &Mark_y); //初始化while (1){printf("Please enter the times of the loops(The martix`s size is %d*%d)\n(The program will stop until you input zero)\n", MARTIX_SIZE, MARTIX_SIZE);while (1){scanf("%d", &loop);if (loop >= 0)break;puts("DO NOT try to input a negative loop");system("cls");puts("Please enter the time of the loop(break until you input 0)");}if (loop == 0) break;fflush(stdin);puts("The Date will be written in ""data.txt"" in the folder of this program\n");if ((fp = fopen("data.txt", "r")) == NULL)puts("""data.txt"" doesn`t exsit,the program will create a new one\n");fp = fopen("data.txt", "a+");time_t c1 = clock(); //這里先得到一個循環開始的時間for (int k = 0; k < NP; k++){link_group_sum = 0; max_poss = 0;/*DFS: 遞歸每一個概率，和每一張圖，然后每一個點深度優先搜索看是否聯通*GPA優化：如果Mark數組出現斷層，則此圖一定不連通(x_full和y_full)*/for (int i = 0; i < loop; i++){sum_particle = 0; x_full = 1; y_full = 1; martix = ReFresh_Martix(martix, &sum_particle, Mark_x, Mark_y, k);max_particle_sum = 0;for (int y = 0; y < MARTIX_SIZE && x_full && y_full; y++){for (int x = 0; x < MARTIX_SIZE && x_full && y_full; x++){if (martix[y][x].flag){DFS_Martix(martix, x, y, G_Stack, &tmp, Mark_x, Mark_y);if (tmp.Link_px && tmp.Link_py){link_group_sum++;if (tmp.particle_sum > max_particle_sum)max_particle_sum = tmp.particle_sum;}}}}poss_tmp = (double)max_particle_sum / (double)sum_particle;max_poss = poss_tmp > max_poss ? poss_tmp : max_poss;}Show(k, link_group_sum, loop, max_poss, fp); //聯通的概率（loop個圖），聯通的時候最大聯通集團粒子數 }time_t c2 = clock(); //得到循環結束的時間（ms）printf("The program has run %lldms\n\n", c2 - c1); fclose(fp); //記得關閉文件流system("pause"); If_Cls(); } Destory(martix, G_Stack, Mark_x, Mark_y); //銷毀棧組 fflush(stdin);system("cls"); system("pause");return 0; }void DFS_Martix(Set **martix, const int st_x, const int st_y, T_Group *const G_Stack, Group *Part_Group, Position *const Mark_x, Position *const Mark_y) {/*函數名: DFS_Martix*調用者函數: void main(void)*函數形參: martix（矩陣）st_x，st_y（開始坐標橫縱坐標）G_Stack（偽遞歸棧堆）Part_Group（集團參數指針）Mark_x，Mark_y（GPA優化的斷層標記數組）*函數功能: DFS搜索聯通集團*返回值： 無*/bool If_Push, //出入棧標志if_link_y = 0, if_link_x = 0; //圖是否聯通標志bool round_dir_x = 0, round_dir_y = 0, //環圖指向標記：規定沿著某個軸沿一個方向突然發生反轉時，某個方向就會被標記1 tmp_dir_x, tmp_dir_y; int dir_tmp, particle_sum = 0, //粒子數top = 0; //棧頂位 Position dir_x, dir_y;T_Group tmp;//......................................................................................//初始化棧..........martix[st_y][st_x].flag = 0; martix[st_y][st_x].dir_x = 0; martix[st_y][st_x].dir_y = 0;Mark_x[st_x]--; Mark_y[st_y]--;tmp.x = st_x, tmp.y = st_y; tmp.dir = dir_tmp = 0;G_Stack[top++] = tmp; particle_sum++;//.................. Part_Group->Link_px = 0;Part_Group->Link_py = 0;while (top != 0){If_Push = 0;tmp = G_Stack[top - 1]; //讀取棧頂元素,以及棧頂元素環圖兩個指向標記round_dir_x = martix[tmp.y][tmp.x].dir_x;round_dir_y = martix[tmp.y][tmp.x].dir_y;//每彈出一個點，就把該節點的x和y做標記,直接從上一個搜索方向之后開始搜索for (int i = dir_tmp; i < 4; i++){dir_x = tmp.x + direction[i].first;tmp_dir_x = (dir_x < 0 || dir_x == MARTIX_SIZE) ? !round_dir_x : round_dir_x;dir_x = (dir_x + MARTIX_SIZE) % MARTIX_SIZE; //循環坐標 dir_y = tmp.y + direction[i].second;tmp_dir_y = (dir_y < 0 || dir_y == MARTIX_SIZE) ? !round_dir_y : round_dir_y;dir_y = (dir_y + MARTIX_SIZE) % MARTIX_SIZE; //循環坐標if (martix[dir_y][dir_x].is_dot && !martix[dir_y][dir_x].flag){//如果環圖指向標記出現相反，則圖已經聯通if (!if_link_x)if_link_x = martix[dir_y][dir_x].dir_x == tmp_dir_x ? 0 : 1;if (!if_link_y)if_link_y = martix[dir_y][dir_x].dir_y == tmp_dir_y ? 0 : 1;}if (martix[dir_y][dir_x].flag){If_Push = 1;Mark_x[dir_x]--; Mark_y[dir_y]--;round_dir_x = tmp_dir_x; round_dir_y = tmp_dir_y;martix[dir_y][dir_x].flag = 0;martix[dir_y][dir_x].dir_x = round_dir_x; martix[dir_y][dir_x].dir_y = round_dir_y;if (!Mark_x[dir_x]) x_full = 0;if (!Mark_y[dir_y]) y_full = 0;tmp.x = dir_x; tmp.y = dir_y; tmp.dir = i;G_Stack[top++] = tmp; particle_sum++;break;}}dir_tmp = 0; //這里一定要初始化為0，否則接下來的點就無法搜索其他方向if (!If_Push) //如果沒有可以入棧的，那說明開始遞歸了，pop棧頂 {top--;dir_tmp = tmp.dir; //定義為當前點上一次出去的點的方向 }}if (particle_sum >= MARTIX_SIZE){Part_Group->Link_px = if_link_x;Part_Group->Link_py = if_link_y;}Part_Group->particle_sum = particle_sum; }

?

轉載于:https://www.cnblogs.com/Philip-Tell-Truth/p/5060061.html

總結

以上是生活随笔為你收集整理的网络导通概率的研究的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。