[不指定 2005/11/23 19:25 | by turbozv ]
计算机解决问题的本质就是搜索,说通俗一点就是尝试各种可能的情况,然后比较找出所需的解。我是从高一开始接触信息学竞赛的,竞赛和工程不一样,要求的是好的算法和在非常短的时间内实现,而工程要求的是稳定性可控和可测。说句实话,高二NOI'98(杭州)以后,我基本上没有再研究过搜索算法,很惭愧,这里贴出我高中的笔记,希望对大家有所帮助。


搜索算法分类:
1)盲目搜索:回溯法、广度优先、深度优先、双向广度优先、分支定界等
2)启发式搜索:A*、分段A*、博弈树等


回溯法:搜索算法的一种控制策略,亦是求解特殊性计数题或较复杂的枚举题中使用频率最高的一种算法,属基础算法,需优化后才能满足解题需要。

常用优化策略:
A)设定阀值,依次扩展节点
B)对处理过的节点不保留


广度优先、双向广度优先算法:解决最优化问题,盲目搜索无智力,一般都用双向广度优先算法。
需要注意的是:
A)双向广度优先算法,使用两头向中间扩展的队列
B)若产生重复节点的几率小,则可以取消判重
C)节点输出用递归:
void Print(int n)
{
   if (n > Queue[n]) printf("%dn", Queue[n].data);
   if (Queue[n] <> 0) Print(Queue[n].from);
   if (n < Queue[n]) printf("%dn", Queue[n].data);
}
单向输出: Print(F);
双向输出: Print(Queue[i].From); Print(i); // i为重合节点
D)扩展节点不是机械的按照正方向一层再逆方向一层,两个方向交替扩展的方法,而是选择节点个数较少的那个方向先扩展,这样就克服了两个方向节点生成速度不平衡的缺点(广度优先搜索的最大困难就是节点膨胀成指数级增长)


分支定界法:试题并未指定目标状态,而是给出约束条件和求某个目标函数的最小要求。
采用分支定界法题目的特点:
A)设置了一个下届prim--目前为止的最优解。在分支定界中,每扩展一个节点,都要重新评估下界,若子节点中相关于目标函数的域值小于下界,才取该域值为新下界,并几下子节点信息
B)设定了一个界变量。在分支定界法中,必须按照目标函数的要求设计变量,作为分支标准,每扩展一个节点之前,都要根据当时已扩展情况计算界变量
C)搜索方式与广度搜索类似(队列)


A*算法:(这个内容好想Job Hunting的时候一般不会考察(游戏界人士除外),所以不费口水了)
………………


各类搜索算法联系图
深度优先------------------>分支定界
         |---->启发式-->A*(修改A*)
广度优先------------------>双向广度


小结
>>深度优先(回溯法):适用于求所有解或普通解,没有智力,对空间要求不大,是一种最自然的走迷宫方法
>>广度优先:适用于求最优解,没有智力,对空间要求很大(必须存储所有节点)
>>A*(修改A*):是启发性搜索的最优化版本(不放弃“坏”节点),适用于求最优解
>>分支定界:是深度优先的最优化版本,是一种简单的求最优解的算法,逆同样可以将你的智慧放在剪枝函数>>中,它继承了深度优先的空间要求小的优点(完全放弃“坏”节点,类似“贪心法”)
>>双向广度:一定程度上降低了广度优先的空间要求大的弊端,尽管没有智力,也不失一种很好的求最优解算法


搜索算法的选择方法
A)根据题目要求和各类算法的适用范围,将不可行的算法抛弃
B)根据题目的规模,将某些不适用与大规模试题的算法抛弃
C)分析问题,找到问题的特点,如果找到了启发函数,就可以使用启发的解法解决
D)如果进一步找到更多关于问题的信息,也许可以使用数学算法(构造法)解决


转载请注明出处,谢谢!
学习 | 评论(1) | 引用(0) | 阅读(13877)
liw
2005/11/30 00:53
生日快乐,ZV
管理员 回复于 2005/11/30 04:12
Thanks, Wood~
分页: 1/1 第一页 1 最后页