《十滴水参考算法》由会员分享，可在线阅读，更多相关《十滴水参考算法（19页珍藏版）》请在金锄头文库上搜索。
1、浅谈十滴水人工智能搜索测试此搜索算法平均比网上能搜索到的同类算法答案每局优02 滴水，未出现过答案劣于网 上同类算法的情况，可能存在一些小漏洞导致的答案偏差，欢迎广大神犇指正。核心思想：先对确定劣质的搜索树进行剪枝，然后通过类人工智能的方法向分析出的能得到最优解的概率大的方向进行搜索，通过分析函数来构造搜索方向，通过状态树调控函数来调控状态树的平均规模，来统筹时间和准确度，通过智能构造答案序列函数来对搜索成果进行最大限度的优化，由于最优解的不唯一性和大量性，选择抛弃搜索全部状态而选用概率性全局剪枝的方法，在小概率选择期望值小的方向，绝对优势概率选择预估最优方向的基础上，通过剪去不理想的局面进行
2、非确定性搜索，虽然不能保证搜索到的解全是最优的，但是由于人工智能的方法对搜索方向，搜索树，答案序列的处理，将随机搜索的错误概率降到了非常低的状态，此算法搜索时间和搜索精确地类似的成反比，通过多次实验调试后的人工智能参数，证明搜索到非最优解的概率与剪枝率成对数关系并稳定到千分之一，并且所得的答案与标准答案差超过 1 的概率小到百万分之一。本算法的核心函数；1、渗透蚁群算法遗传算法思想的概率性淘汰和创新函数2、渗透模糊图像识别思想的获取水滴图像密集度参数函数3、智能答案序列启发式优化函数4、智能调控搜索树状态函数5、智能交互式判断函数6、十滴水模拟函数主要流程：输入数据- 获取当前局面的价值评价-
3、 抽取状态样本- 搜索出一个解- 搜索树智能调控- 智能优化解到局部最优解-输出数据算去详解 下面我来详细讲解一下核心函数的思想方法和特殊的智能处理：一、输入函数本部分加入了大量的特判来对付极端数据对程序的危害，也是本程序最简单的部分，加入的 特判有：输入越界判断，输入非去字符判断二、输出函数本部分是所有函数中第二简单的函数，本部分先判断不需要操作的局面，之后是输出20组 答案序列，在每个序列以坐标方式输出后，会对局面进行模拟来使得用于选择一种喜欢的顺 序进行操作三、启发函数一：密集度模糊式启发函数本函数为搜索的核心优化函数，通过反映一个坐标点周围所影响水滴的加权密集程度的量化 参数，来统筹安
4、排搜索顺序和概率性剪枝，程序能根据此函数返回的价值分数来向更有可能 获得最优解的方向进行搜索。本函数的核心思想是如何计算一个点所在坐标的密集度，定义 一个坐标点所影响的范围为上下左右所接触到的第一个存在水且在地图边界之内的水滴坐 标，按照二维几何正态分布函数图象加权的个体水滴数参数进行综合计算，本函数运用动态 规划的方法，在0（n八2*step）的时间内统计结果，step为预测影响的步数，本函数设计step 为 3 步，代表意义为统计每个水滴坐标点3 步之内所影响范围的加权综合评估分数。由于 step=1 时的个体影响坐标是离散的，故可以较为精确的统计图象的密集度。定义：价值评估值二工（区域权
5、重*个体水滴量）一次加权设定为010121010中心权重为 2，周边影响权重为 1，进行 3 步动规后的密集度权重为（有重叠）：000010000000454000006152515600041542524215401525527452255104154252421540006152515600000454000000010000本方法所构成的函数加权树状图分布趋向可大概表示为（中心点权值最大，经过中继点个数 越多权值越小）：（此图反映的是无穷大边界时的密集度影响范围趋向图，红色点表示有水滴的坐标点，蓝色 线表示影响路径）（通过上图可以清楚地看到此函数反应的密集度与中心点到周边点的曼哈顿距离无
6、关，而是 与直接影响有关，是比较准确的）（附加两个附加型启发函数二、三，这两个函数在本算法中均未使用，因为经测试效果不如 以一种启发函数理想,第二种为单纯的静态区域权值，不如动态计算密集度参数效果好，第 三种启发函数为单纯的平均权值随机搜索模型）三、 旋转抽样函数 本函数体现遗传算法和蚁群算法的概率性选择和淘汰变异思想，采用的是经典的轮 盘方法来构造答案序列和搜索方向序列，为人工智能搜索主函数提供指向性参考，核心思想 为依照适应度的价值评估进行加权随机抽取。四、答案智能优化处理函数 本算法为加强搜索的速度提供了强有力的保障，作用是当搜索出一组答案序列时，此算法会 智能的对序列进行优化和变异，使
7、传入此函数的答案序列进化到一个与基准序列元素相同结 构顺序不同的优质答案传出，核心思想是先根据贪心思路进行合理的显性的构造，使得答案 序列中先筛选出一组子序列满足最优性，之后对剩下的序列进行随机概率性淘汰进化，为了 避免枚举所有可行序列而发生的局部卡死，本算法通过调用随机生成序列辅函数的方式对剩 余序列进行随机智能构造和定向淘汰和进化，之后将得到的同元素不同结构的优质序列进行 返回。为了更大的满足用户的需求，同解答案保留尽量按照升序排列的序列。五、搜索树动态调控函数 本函数的作用是根据预估的搜索树最大深度来扩大或缩小每个局面所需讨论状态总量，对搜 索总状态数维持产生平稳的趋向，来宏观调控时间与
8、精确地的矛盾，此处采用二分法将搜索 状态总量趋向于平衡点，本算法设计每个深度状态的讨论总量与此状态的价值评估成近似正 比，与此状态的已有花费成近似反比。六、人工智能搜索主函数 这是搜索的主函数，调用到了上述的所有智能启发函数，加入了上节剪枝，分治不相干区域连通块剪枝的方法进行概率搜索，拥有统计最终答案序列的功能。下面是源码：#include#include#include#include#include#include#include#includeusing namespace std;/智能核心参数cons t int popula tion=30;/初始种群样本总量cons t doub
9、le scales4 = 3.0,2.0,1.2,1.0;/梯度权重参数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;/全局搜索Al离散映射基准表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.
10、,2.,2.;/Al 离散函数映射基准表 int Al_argumen t5 = 0,1,2,9,16;/本体估价参数cons t int Predic tion_s tep=3;/智能预测步数上限cons t int Al_value5 = 0,1,2,9,16;/本体估价参数cons t int Gradien t_Parame ter2 = 2,1;/梯度估价参数cons t int Expec ted_S tat e=2147000000;/搜索状态总量上限/定义结构体struct statusint x;int y;int deraction;int state;int number
11、;struct coordinateint x;int y;struct 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,Answe r_Number=Max_Deep_Ceiling+12,contest=0;sheet answerpopulation,test_list;int move42=0,1,1,0,0,
12、-1,-1,0;int map_test66,Sum_Number;double map_value66;/声明函数void map_value_build();/构建棋盘权值函数void draw(int Deep);/调试打表函数bool Check_Deep_Finish(in t);/检测终止局面函数void draw(in t);/打印地图函数bool check(s tat us);/检测可行性辅助函数int fill(in t,in t,in t);/填充水滴模拟函数int Value_Calcula tor(in t,in t,in t,in t);/估价函数辅助计算器void
13、 AI_Con tr ol_Tree();/搜索树动态调控函数sit ua tion Ini tail_Value_Mapl(in t,in t&);/密集度模糊式启发函数 situat ion Ini tail_Value_Map2(in t,in t&);/个体样本&区域梯度式启发函数 sit ua tion Ini tail_Value_Map3(in t,in t&);/随机化搜索式启发函数 shee t Ro tat ion_Sample(in t,in t,in t);/旋转抽样函数 shee t Random_Answer(shee t&,in t);/构建答案序列辅函数 she
14、e t answer_sor t(shee t,in t&);/答案智能优化处理函数int Artif icial_in telligen t_search(in t);/人工智能搜索主函数void map_ tes t_build();/构建备用图void Ge t_Sum_Number();/上界获取辅助函数void Ini tail_Value_Map_check();/图像模糊分析检测器void Rotatio n_Sample_check();/R otatio n_Sample 检测器void Pre trea tmen t();/预处理函数void Inpu t();/ 输入函数void Out pu t();/ 输出函数int main()Pretreatment();Input();map_value_build(); map_test_build(); Get_Sum_Number();Artificial_intelligent_search(0);coutendlendlendlendl最终答案：endl;Output();return 0;
