十滴水參考算法

1、淺談十滴水一一人工智能搜索測試此搜索算法平均比網(wǎng)上能搜索到的同類算法答案每局優(yōu)02滴水，未出現(xiàn)過答案劣于網(wǎng) 上同類算法的情況，可能存在一些小漏洞導(dǎo)致的答案偏差，歡迎廣大神犇指正。核心思想：先對確定劣質(zhì)的搜索樹進行剪枝，然后通過類人工智能的方法向分析出的能得到最優(yōu)解的概 率大的方向進行搜索，通過分析函數(shù)來構(gòu)造搜索方向，通過狀態(tài)樹調(diào)控函數(shù)來調(diào)控狀態(tài)樹的 平均規(guī)模，來統(tǒng)籌時間和準(zhǔn)確度，通過智能構(gòu)造答案序列函數(shù)來對搜索成果進行最大限度的 優(yōu)化，由于最優(yōu)解的不唯一性和大量性，選擇拋棄搜索全部狀態(tài)而選用概率性全局剪枝的方 法，在小概率選擇期望值小的方向，絕對優(yōu)勢概率選擇預(yù)估最優(yōu)方向的基礎(chǔ)上，通過剪去不 理

2、想的局面進行非確定性搜索，雖然不能保證搜索到的解全是最優(yōu)的，但是由于人工智能的 方法對搜索方向，搜索樹，答案序列的處理，將隨機搜索的錯誤概率降到了非常低的狀態(tài)， 此算法搜索時間和搜索精確地類似的成反比，通過多次實驗調(diào)試后的人工智能參數(shù)，證明搜 索到非最優(yōu)解的概率與剪枝率成對數(shù)關(guān)系并穩(wěn)定到千分之一，并且所得的答案與標(biāo)準(zhǔn)答案差 超過1的概率小到百萬分之一。本算法的核心函數(shù)；1、滲透蟻群算法遺傳算法思想的概率性淘汰和創(chuàng)新函數(shù)2、滲透模糊圖像識別思想的獲取水滴圖像密集度參數(shù)函數(shù)3、智能答案序列啟發(fā)式優(yōu)化函數(shù)4、智能調(diào)控搜索樹狀態(tài)函數(shù)5、智能交互式判斷函數(shù)6、十滴水模擬函數(shù)主要流程：輸入數(shù)據(jù)-獲取當(dāng)前局

3、面的價值評價-抽取狀態(tài)樣本-搜索出一個解-搜索樹智能調(diào)控-智能優(yōu)化解到局部最優(yōu)解-輸出數(shù)據(jù)算法詳解下面我來詳細講解一下核心函數(shù)的思想方法和特殊的智能處理：一、輸入函數(shù)本部分加入了大量的特判來對付極端數(shù)據(jù)對程序的危害，也是本程序最簡單的部分，加入的 特判有：輸入越界判斷，輸入非法字符判斷二、輸出函數(shù)本部分是所有函數(shù)中第二簡單的函數(shù)，本部分先判斷不需要操作的局面，之后是輸出20組 答案序列，在每個序列以坐標(biāo)方式輸出后，會對局面進行模擬來使得用于選擇一種喜歡的順 序進行操作三、啟發(fā)函數(shù)一：密集度模糊式啟發(fā)函數(shù)本函數(shù)為搜索的核心優(yōu)化函數(shù)，通過反映一個坐標(biāo)點周圍所影響水滴的加權(quán)密集程度的量化 參數(shù)，來統(tǒng)

4、籌安排搜索順序和概率性剪枝，程序能根據(jù)此函數(shù)返回的價值分?jǐn)?shù)來向更有可能 獲得最優(yōu)解的方向進行搜索。本函數(shù)的核心思想是如何計算一個點所在坐標(biāo)的密集度，定義 一個坐標(biāo)點所影響的范圍為上下左右所接觸到的第一個存在水且在地圖邊界之內(nèi)的水滴坐 標(biāo)，按照二維幾何正態(tài)分布函數(shù)圖象加權(quán)的個體水滴數(shù)參數(shù)進行綜合計算，本函數(shù)運用動態(tài) 規(guī)劃的方法，在O（nA2*step）的時間內(nèi)統(tǒng)計結(jié)果，step為預(yù)測影響的步數(shù)，本函數(shù)設(shè)計step 為3步，代表意義為統(tǒng)計每個水滴坐標(biāo)點3步之內(nèi)所影響范圍的加權(quán)綜合評估分?jǐn)?shù)。由于 step=1時的個體影響坐標(biāo)是離散的，故可以較為精確的統(tǒng)計圖象的密集度。定義：價值評估值=Z區(qū)域權(quán)重*個

5、體水滴量）一次加權(quán)設(shè)定為010121010中心權(quán)重為2,周邊影響權(quán)重為1，進行3步動規(guī)后的密集度權(quán)重為（有重疊）：000010000000454000006152515600041542524215401525527452255104154252421540006152515600000454000000010000本方法所構(gòu)成的函數(shù)加權(quán)樹狀圖分布趨向可大概表示為（中心點權(quán)值最大，經(jīng)過中繼點個數(shù) 越多權(quán)值越?。海ù藞D反映的是無窮大邊界時的密集度影響范圍趨向圖，紅色點表示有水滴的坐標(biāo)點，藍色 線表示影響路徑）（通過上圖可以清楚地看到此函數(shù)反應(yīng)的密集度與中心點到周邊點的曼哈頓距離無關(guān)，而是 與直

6、接影響有關(guān)，是比較準(zhǔn)確的）（附加兩個附加型啟發(fā)函數(shù)二、三，這兩個函數(shù)在本算法中均未使用，因為經(jīng)測試效果不如 以一種啟發(fā)函數(shù)理想，第二種為單純的靜態(tài)區(qū)域權(quán)值，不如動態(tài)計算密集度參數(shù)效果好，第 三種啟發(fā)函數(shù)為單純的平均權(quán)值隨機搜索模型）三、旋轉(zhuǎn)抽樣函數(shù)本函數(shù)體現(xiàn)遺傳算法和蟻群算法的概率性選擇和淘汰變異思想，采用的是經(jīng)典的輪 盤方法來構(gòu)造答案序列和搜索方向序列，為人工智能搜索主函數(shù)提供指向性參考，核心思想 為依照適應(yīng)度的價值評估進行加權(quán)隨機抽取。四、答案智能優(yōu)化處理函數(shù)本算法為加強搜索的速度提供了強有力的保障，作用是當(dāng)搜索出一組答案序列時，此算法會 智能的對序列進行優(yōu)化和變異，使傳入此函數(shù)的答案序列

7、進化到一個與基準(zhǔn)序列元素相同結(jié) 構(gòu)順序不同的優(yōu)質(zhì)答案傳出，核心思想是先根據(jù)貪心思路進行合理的顯性的構(gòu)造，使得答案 序列中先篩選出一組子序列滿足最優(yōu)性，之后對剩下的序列進行隨機概率性淘汰進化，為了 避免枚舉所有可行序列而發(fā)生的局部卡死，本算法通過調(diào)用隨機生成序列輔函數(shù)的方式對剩 余序列進行隨機智能構(gòu)造和定向淘汰和進化，之后將得到的同元素不同結(jié)構(gòu)的優(yōu)質(zhì)序列進行 返回。為了更大的滿足用戶的需求，同解答案保留盡量按照升序排列的序列。五、搜索樹動態(tài)調(diào)控函數(shù)本函數(shù)的作用是根據(jù)預(yù)估的搜索樹最大深度來擴大或縮小每個局面所需討論狀態(tài)總量，對搜 索總狀態(tài)數(shù)維持產(chǎn)生平穩(wěn)的趨向，來宏觀調(diào)控時間與精確地的矛盾，此處采用

8、二分法將搜索 狀態(tài)總量趨向于平衡點，本算法設(shè)計每個深度狀態(tài)的討論總量與此狀態(tài)的價值評估成近似正 比，與此狀態(tài)的已有花費成近似反比。六、人工智能搜索主函數(shù)這是搜索的主函數(shù)，調(diào)用到了上述的所有智能啟發(fā)函數(shù)，加入了上節(jié)剪枝，分治不相干區(qū)域連通塊剪枝的方法進行概率搜索，擁有統(tǒng)計最終答案序列的功能。下面是源碼：#include#include#include#include#include#include#include#includeusing namespace std;/智能核心參數(shù)const int population=30;/初 始種群樣本總量const double scales4=3.0

9、,2.0,1.2,1.0;/梯 度權(quán)重參數(shù)const int Max_Deep_Ceiling=99;/constintvalue_number_mappingMax_Deep_Ceiling=36,36,36,36,36,36,36,36,36,36,36,36,36,36,36;/全局搜索AI離散映射基準(zhǔn)表doubleState_TreeMax_Deep_Ceiling+1=72.,60.,26.,22.,18.,15.,12.,9.,7.,6.,5.,5.,4.,4.,4.,3.,3.,3.,3.,2.,2.,2.,2.,2.,2.,2.,2.,2.,2.,2.,2.;/AI 離散函數(shù)映

10、射基準(zhǔn)表int AI_argument5=0,1,2,9,16;/本 體估價參數(shù)const int Prediction_step=3;智能預(yù)測步數(shù)上限const int AI_value5=0,1,2,9,16;/本 體估價參數(shù)const int Gradient_Parameter2=2,1;/梯 度估價參數(shù)const int Expected_State=2147000000;/搜索狀態(tài)總量上限/定義結(jié)構(gòu)體struct statusint x;int y;int deraction;int state;int number;struct coordinateint x;int y;str

11、uct sheetcoordinate coorMax_Deep_Ceiling;int total;int additional;struct situationint map66;/定義變量intMaxDeep=Max_Deep_Ceiling,i,j,k,l,mapMax_Deep_Ceiling66,answer_tot=0,Answer_Numbe r=Max_Deep_Ceiling+12,contest=0;sheet answerpopulation,test_list;int move42=0,1,1,0,0,-1,-1,0;int map_test66,Sum_Number

12、;double map_value66;/聲明函數(shù)void map_value_build();/構(gòu)建棋盤權(quán)值函數(shù)void draw(int Deep);/調(diào)試打表函數(shù)bool Check_Deep_Finish(int);/檢測終止局面函數(shù)void draw(int);/打 印地圖函數(shù)bool check(status);/檢測可行性輔助函數(shù)int fill(int,int,int);/填 充水滴模擬函數(shù)int Value_Calculator(int,int,int,int);/估 價函數(shù)輔助計算器void AI_Control_Tree();/艘索樹動態(tài)調(diào)控函數(shù)situation Ini

13、tail_Value_Map1(int,int&);/密 集度模糊式啟發(fā)函數(shù)situation Initail_Value_Map2(int,int&);/個 體樣本 & 區(qū)域梯度式啟發(fā)函數(shù)situation Initail_Value_Map3(int,int&);/隨 機化搜索式啟發(fā)函數(shù)sheet Rotation_Sample(int,int,int);/旋 轉(zhuǎn)抽樣函數(shù)sheet Random_Answer(sheet&,int);/構(gòu)建答案序列輔函數(shù)sheet answer_sort(sheet,int&);答案智能優(yōu)化處理函數(shù)int Artificial_intelligent_se

14、arch(int);/A 工智能搜索主函數(shù)void map_test_build();/構(gòu)建備用圖void Get_Sum_Number();/上界獲取輔助函數(shù)void Initail_Value_Map_check();/圖像模糊分析檢測器void Rotation_Sample_check();/Rotation_Sample 檢測器void Pretreatment();/預(yù)處理函數(shù)void Input();/輸入函數(shù)void Output();/輸出函數(shù)int main()Pretreatment();Input();map_value_build();map_test_build()

15、;Get_Sum_Number();Artificial_intelligent_search(0);coutendlendlendlendl最終答案：:endl;Output();return 0;void map_value_build()/構(gòu)建棋盤權(quán)值函數(shù)int i,j,k;for(i=0;i=5;i+)for(j=0;j=5;j+)map_valueij=3;for(k=0;k=2;k+)for(i=0;i=2;i+)for(j=2-i+k;j=3+i-k;j+)map_valueij-;map_value5-ij-;for(i=0;i=5;i+)for(j=0;j=5;j+)map_

16、valueij=scales(int)map_valueij;void draw(int Deep)/打 印地圖函數(shù)int i,j;coutendl;for(i=0;itest_list.total;i+)cout(test_list.coori.x+1,test_list.coori.y+1);coutendl;for(i=0;i=5;i+)for(j=0;j=5;j+)coutmapDeepij;coutendl;system(pause);bool check(status a)/檢測可行性輔助函數(shù)if(a.x5|a.y5)return false;elsereturn true;int

17、 fill(int Deep,int x,int y)/填 充水滴模擬函數(shù)int i,j,k,l,con=1;mapDeepxy+;if(mapDeepxy=4)return 0;queue q;status drop,ls;l=0;mapDeepxy=0;drop.x=x;drop.y=y;drop.number=0;drop.state=0;for(i=0;i0)drop=q.front();elsels.number=l;ls.state=0;for(i=0;i=5;i+)for(j=0;j4)mapDeepij=0;con+;ls.x=i;ls.y=j;for(k=0;kl)l=dro

18、p.number;ls.number=l;ls.state=0;for(i=0;i=5;i+)for(j=0;j4)mapDeepij=0;con+;ls.x=i;ls.y=j;for(k=0;k=3;k+)ls.deraction=k;q.push(ls);q.pop();i=drop.x+movedrop.deraction0;j=drop.y+movedrop.deraction1;if(drop.state=0)if(i5|j5)continue;if(mapDeepij0)mapDeepij+;elsedrop.state=1;drop.number+;q.push(drop);el

19、sedrop.state=0;drop.x=i;drop.y=j;drop.number+;if(check(drop)=true)q.push(drop);return con;int Value_Calculator(int map_number,int parameter,int x,int y)/估 價函數(shù)輔助計算器if(parameter=0)return (int)(map_number*parameter*map_valuexy);void AI_Control_Tree()搜索樹動態(tài)調(diào)控函數(shù)doubleCoefficient_left,Coefficient_right=Exp

20、ected_State/(Answer_Number+1)*State_Tree0),mid,pow =1.,pow2;int i,j;for(i=0;i0.0001)mid=(Coefficient_left+Coefficient_right)/2;pow2=1;j=0;for(i=0;iExpected_State)Coefficient_right=mid;j=1;break;if(j=0)Coefficient_left=mid;for(i=0;i=MaxDeep;i+)State_Treei=State_Treei*Coefficient_left;if(State_Treei=1

21、.01)State_Treei=1.01;situation Initail_Value_Map1(int Deep,int &sum)/密 集度模糊式啟發(fā)函數(shù)int i,j,k,l,t,p,Value_Min=2099999999,Average=0,Number=0;situation value_copy,value;coordinate coor664,ls,Max_coor;for(i=0;i=5;i+)for(j=0;j=5;j+)if(mapDeepij=0)value.mapij=0;for(k=0;k=3;k+)coorijk.x=-1;coorijk.y=-1;elseva

22、lue.mapij=AI_valuemapDeepij*Gradient_Parameter0;for(k=0;k=0&ls.y=0&ls.x=5&ls.y0)value.mapij+=AI_valuemapDeepls.xls.y*Gradient_Parameter1;coorijk.x=ls.x;coorijk.y=ls.y;l=1;break;ls.x+=movek0;ls.y+=movek1;if(l=0)coorijk.x=-1;coorijk.y=-1;for(t=1;t=Prediction_step;t+)value_copy=value;for(i=0;i=5;i+)for

23、(j=0;j=5;j+)for(k=0;k=0&coorijk.y=0)value.mapij+=value_copy.mapcoorijk.xcoorijk.y;for(i=0;i=5;i+)for(j=0;j0)Value_Min=min(Value_Min,value.mapij);Max_coor.x=0;Max_coor.y=0;k=value.map00;for(i=0;i=5;i+)for(j=0;j0)Number+;if(value.mapMax_coor.xMax_coor.yk)k=value.mapMax_coor.xMax_coor.y;Max_coor.x=i;Ma

24、x_coor.y=j;Average+=value.mapij;Average/=Number;for(i=0;i=5;i+)for(j=0;j0)value.mapij=value.mapij*value.mapij/Average;while(value.mapMax_coor.xMax_coor.y46340)for(i=0;i=5;i+)for(j=0;j=5;j+)value.mapij/=10;for(i=0;i=5;i+)for(j=0;j0)value.mapij=value.mapij*value.mapij/Average;sum=0;for(i=0;i=5;i+)for(

25、j=0;j=5;j+)sum+=value.mapij;return value;situation Initail_Value_Map2(int Deep,int &sum)/個 體樣本 / 區(qū)域梯度式啟發(fā)函數(shù)situation value;for(int i=0;i=5;i+)for(int j=0;j=5;j+)value.mapij=Value_Calculator(mapDeepij,AI_valuemapDeepij,i,j);sum+=value.mapij;situation Initail_Value_Map3(int Deep,int &sum)/隨 機搜索啟發(fā)函數(shù)situ

26、ation value;for(i=0;i=5;i+)for(j=0;j0)value.mapij=1;sum+=1;elsevalue.mapij=0;return value;sheet Rotation_Sample(int Deep,int AI_argument,int number)/旋 轉(zhuǎn)抽樣函數(shù) int i,j,k,l,sample,sum=0,remain=0;situation value;sheet list;memset(list.coor,0,sizeof(list.coor);list.total=0;value=Initail_Value_Map1(Deep,su

27、m);for(i=0;i=5;i+)for(j=0;j0)remain+;remain=min(remain,number);while(remain0)sample=rand()*rand()% sum+1;i=0;j=0;while(value.mapij5)j=0;i+;list.coorlist.total.x=i;list.coorlist.total.y=j;list.total+;sum-=value.mapij;value.mapij=0;remain-;list.total-;return list; sheet Random_Answer(sheet &list,int n

28、)/|構(gòu)建答案序列輔函數(shù) int i,j,tot;coordinate a40;tot=0;for(i=list.total-n;ilist.total;i+)atot=list.coori;tot+;for(i=list.total-n;ilist.total;i+)j=rand()% tot;list.coori=aj;tot-;aj=atot;sheet answer_sort(sheet list,int &Argument)/答案智能優(yōu)化處理函數(shù)int i,j,k,p,con,tot,pdMax_Deep_Ceiling;memset(pd,0,sizeof(pd);sheet ou

29、tput,output_copy;coordinate ls;output.total=list.total;tot=0;for(i=0;ilist.total;i+)if(map0list.coori.xlist.coori.y4)fill(0,list.coori.x,list.coori.y);output.coortot.x=list.coori.x;output.coortot.y=list.coori.y;pdi=1;tot+;k=0;for(i=0;ii;j-)if(output.coorj-1.xoutput.coorj.x)|(output.coorj-1.x=output.

30、coorj.x)&(output.coorj-1.youtput.coorj.y)ls=output.coorj-1;output.coorj-1=output.coorj;output.coorj=ls;for(i=0;ilist.total;i+)if(pdi=0)output.coortot.x=list.coori.x;output.coortot.y=list.coori.y;tot+;k+;p=0;for(int t=1;t=10;t+)con=0;Random_Answer(output,k);for(i=0;i=5;i+)for(j=0;j=5;j+)map0ij=map_te

31、stij;for(i=0;iSum_Number/3-con)Argument=Sum_Number/3-con;output_copy=output;/for(i=0;ioutput.total;i+)coutoutput.coori.x output.coori.yendl;/draw(0);if(Check_Deep_Finish(0)=false)continue;elsep=1;if(Argument=0)break;for(i=0;i=5;i+)for(j=0;j=5;j+)map0ij=map_testij;output=output_copy;output.additional

32、=Sum_Number/3-Argument;if(p=0)output.total=-1;return output; int Artificial_intelligent_search(int Deep)/A 工智能搜索主函數(shù) /draw(Deep);contest+;if(contest+rand()% 713)% 3000=0)cout,當(dāng)前已經(jīng)搜索的狀態(tài)量為：contestMaxDeep)return 0;if(Check_Deep_Finish(Deep)=true)l=99;MaxDeep=Deep;test_list_copy=test_list;test_list=answe

33、r_sort(test_list,l);if(test_list.total=0)if(test_list.total+lAnswer_Number)AI_Control_Tree();Answer_Number=test_list.total+l;answer_tot=0;if(answer_totpopulation)for(i=0;itest_list.total;i+)answeranswer_tot.coori.x=test_list.coori.x;answeranswer_tot.coori.y=test_list.coori.y;answeranswer_tot.total=t

34、est_list.total;answeranswer_tot.additional=test_list.additional;answer_tot+;test_list=test_list_copy;return 1;if(Deep=MaxDeep)return 0;list=Rotation_Sample(Deep,AI_argument,(int)State_TreeDeep);for(l=0;l=list.total;l+)k=5-mapDeeplist.coorl.xlist.coorl.y;for(i=0;i=5;i+)for(j=0;j=5;j+)mapk+Deepij=mapD

35、eepij;for(i=1;i=k;i+)test_list.coortest_list.total.x=list.coorl.x;test_list.coortest_list.total.y=list.coorl.y;test_list.total+;fill(k+Deep,list.coorl.x,list.coorl.y);Artificial_intelligent_search(k+Deep);for(i=1;i=k;i+)test_list.total-;return 0;void map_test_build()/構(gòu)建備用圖int i,j;for(i=0;i=5;i+)for(

36、j=0;j=5;j+)map_testij=map0ij;void Get_Sum_Number()/上界獲取輔助函數(shù)int i,j;for(i=0;i=5;i+)for(j=0;j0)Sum_Number+;void Initail_Value_Map_check()/圖像模糊分析檢測器situation s;s=Initail_Value_Map1(0,k);coutOKendl;for(i=0;i=5;i+)for(j=0;j=5;j+)couts.mapij ;coutendl;system(pause);void Rotation_Sample_check()/Rotation_Sample 檢測器int a5=0,1,2,5,16;char c66;sheet ls;for(;)ls=Rotation_Sample(0,a,36);for(i=0;i=5;i+)for(j=0;j=5;j+)cij=map0ij+48;for(i=0;ils.total;i+)cls.coori.xls.coori.y=*;for(i=0;i=5;i+)for(j=0;j=5;j+)coutcij;coutendl;system(pause);void P