现在的位置: 首页 > 综合 > 正文

IDA*算法

2013年05月05日 ⁄ 综合 ⁄ 共 1987字 ⁄ 字号 评论关闭

IDA*算法A*算法和迭代加深算法的结合。

 

迭代加深算法是在dfs搜索算法的基础上逐步加深搜索的深度,它避免了广度优先搜索占用搜索空间太大的缺点,也减少了深度优先搜索的盲目性。它主要是在递归搜索函数的开头判断当前搜索的深度是否大于预定义的最大搜索深度,如果大于,就退出这一层的搜索,如果不大于,就继续进行搜索。这样最终获得的解必然是最优解。

 

而在A*算法中,我们通过使用合理的估价函数,然后在获得的子节点中选择fCost最小的节点进行扩展,以此完成搜索最优解的目的。但是A*算法中,需要维护关闭列表和开放列表,需要对扩展出来的节点进行检测,忽略已经进入到关闭列表中的节点(也就是所谓的已经检测过的节点),另外也要检测是否与待扩展的节点重复,如果重复进行相应的更新操作。所以A*算法主要的代价花在了状态检测和选择代价最小节点的排序上,这个过程中占用的内存是比较大的,一般为了提高效率都是使用hash进行重复状态检测。

 

IDA*算法具有如下的特点:(

综合了A*算法的人工智能性和回溯法对空间的消耗较少的优点,在一些规模很大的搜索问题中会起意想不到的效果。它的具体名称是Iterative Deepening A*, 1985年由Korf提出。该算法的最初目的是为了利用深度搜索的优势解决广度A*的空间问题,其代价是会产生重复搜索。归纳一下,IDA*的基本思路是:首先将初始状态结点的H值设为阈值maxH,然后进行深度优先搜索,搜索过程中忽略所有H值大于maxH的结点;如果没有找到解,则加大阈值maxH,再重复上述搜索,直到找到一个解。在保证H值的计算满足A*算法的要求下,可以证明找到的这个解一定是最优解。在程序实现上,IDA*要比
A*
方便,因为不需要保存结点,不需要判重复,也不需要根据H值对结点排序,占用空间小 
而这里在IDA*算法中也使用合适的估价函数,来评估与目标状态的距离。

在一般的问题中是这样使用IDA*算法的,当前局面的估价函数值+当前的搜索深度
>
预定义的最大搜索深度时,就进行剪枝。

这个估计函数的选取没有统一的标准,找到合适的该函数并不容易,但是可以大致按照这个原则:在一定范围内加大各个状态启发函数值的差别

http://blog.csdn.net/urecvbnkuhbh_54245df/article/details/5856756

http://www.cnblogs.com/steady/archive/2011/01/16/1936551.html

http://hi.baidu.com/wangz_j/item/d0c40e815026955b27ebd9f4

http://blog.sina.com.cn/s/blog_71fda43501011uhv.html

http://blog.csdn.net/sdj222555/article/details/7233928

http://www.cnblogs.com/liyongmou/archive/2010/07/19/1780861.html

 

康托排序+IDA*

http://www.cnblogs.com/liyongmou/archive/2010/07/19/1780861.html

http://www.cnblogs.com/liyongmou/archive/2010/07/16/1778830.html

康托展开的公式

把一个整数X展开成如下形式:

X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!

其中,a为整数,并且0<=a[i]<i(1<=i<=n)


康托展开的应用实例

{1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个。123 132 213 231 312 321 。

代表的数字 1 2 3 4 5 6 也就是把10进制数与一个排列对应起来。

他们间的对应关系可由康托展开来找到。

如我想知道321是{1,2,3}中第几个大的数可以这样考虑:

第一位是3,当第一位的数小于3时,那排列数小于321 如 123、 213 ,小于3的数有1、2 。所以有2*2!个。再看小于第二位2的:小于2的数只有一个就是1,所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个。所以321是第6个大的数。 2*2!+1*1!+1*0!就是康托展开。

再举个例子:1324是{1,2,3,4}排列数中第几个大的数:第一位是1小于1的数没有,是0个 0*3! 第二位是3小于3的数有1和2,但1已经在第一位了,所以只有一个数2 1*2! 。第三位是2小于2的数是1,但1在第一位,所以有0个数 0*1! ,所以比1324小的排列有0*3!+1*2!+0*1!=2个,1324是第三个大数。

抱歉!评论已关闭.