启发式搜索算法学习之A* & ID_A*
文中提及的一些观点和理论，并非全部个人原创，而是自己的总结和心得， 仅供个人学习编程使用！
启发式搜索算法从听说有这个名字开始到正真学习她，应该间隔了一年多的时间吧！当我接触他之后，就有种相见恨晚的感觉！因为她完美的剪枝思想，不仅弥补了通常盲目搜索算法的不足，提高了程序的运行效率，而且给了我一种处理搜索问题的“优化思想”！
下面就让我简单的说一下个人对两种启发式搜索算法，A*和ID_A*算法的理解。开始之前，先推荐比较好的几份资料。
-
《A*算法详解》 Sunway；个人认为他的这篇介绍性的文章写的非常到位，由浅入深的带领我们进入A*算法的世界。强烈建议，学习启发搜索先看这篇文章。（推荐
） - 《A*算法》(ppt) 尚福华； 从理论层面上分析了A*算法的正确性。很值得我们在学了A*算法一段时间之后，回过来分析和思考的。（推荐♦♦♦♦♦）
- 《算法艺术与信息学竞赛》（刘如佳，黄亮 著）P168。介绍的比较笼统，适合有一定基础的人来体会。
先给出一个A*算法的模型Sunway。
Best_First_Search() {
Open = [起始节点S0]; Closed = [NULL];
while (Open表非空) {
从Open中取得一个节点X，并从OPEN表中删除。
if (X是目标节点) {
求得一组最优路径PATH；返回路径PATH；
}
for (每一个X的子节点Y) {
if (Y不在OPEN表和CLOSE表中) {
求Y的估价值；并将Y插入OPEN表中；//还没有排序
}
else
if (Y在OPEN表中) {
if (Y的估价值小于OPEN表的估价值)
更新OPEN表中的估价值；
}
else {//Y在CLOSE表中
if (Y的估价值小于CLOSE表的估价值) {
更新CLOSE表中的估价值；
从CLOSE表中移出节点，并放入OPEN表中；
}
}
}//end for
将X节点插入CLOSE表中；
按照估价值f()将OPEN表中的节点排序；
}//end while
}//end func
谈到A* 算法，就要涉及到三个函数：估价函数f() = 实际代价函数g() + 启发函数 h();
对于状态空间中的某个节点n定义：f*(n)为初始节点src， 约束警告过节点n到达目标节点的最小代价值（f(n)是对f(n)的一个估价，因此成为估价函数）。则f*(n)应包含两部分：一是：从目标节点到达节点N时的最小代价，记为g*() (g() 是g*()的一个上界)；另外一部分是从节点n到达目标节点的最小代价，记为h*(), (因为h()使我们事先无法知晓的，所以，我们用h()来估计，因此，称为估价函数h())。所以，g()是对g*()的一个估价，h()是对h*()的一个估价。
对于实际代价函数g()，我们在搜索到当前节点的时候，有可能最小代价的路径还没有找到，所以 有g() >= g*(), 即 g() 是g*()的一个上界。
对于估价函数g(), 这里要重点介绍一下了，尚福华的ppt里面说的很清晰，这里就引用一下。h(n)的单调限制：
在A*算法中，每当扩展一个节点n时，都需要检查其子节点是否已在Open表或Closed表中。对于那些已在Open表中的子节点，需要决定是否调整指向其父节点的指针；对于那些已在Closed表中的子节点，除了需要决定是否调整其指向父节点的指针外，还需要决定是否调整其子节点的后继节点的父指针。这就增加了搜索的代价。如果我们能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，就没有必要再去检查其后继节点是否已在Closed表中，原因是Closed表中的节点都已经找到了通往该节点的最佳路径。为满足这一要求，我们需要启发函数h(n)增加单调性限制。
对任意节点ni及其任意子节点nj, 都有 h(ni) <= h(nj) + c(ni, nj); 其中c (ni,,nj)是节点ni到其子节点nj的边代价，则称h(n)满足单调限制。满足此性质的启发函数h()，我们称她是相容（consistent）。
下面是加了H(n)单调性优化的伪代码（黑皮书P170）：
Procedure Expand(State: StateType);
Begin
for i := 1 to OperandCount(State) do
Begin
NewState := DoOperand(State, i);
NewState.h := CalculateH(NewState);
NewState.g := State.g + 1;
NewState.f := NewState.g + NewState.h;
NewState.f := State;
NewState.LastOp := OperandCount;
i := FindInsertTableTwo(NewState); // 在表二中查找，找不到就插入
If i = 0 then
InsertToTableOne(NewState);
ELse if NewState.f < State[i].f then // 新状态优于原状态就替换。
ReplaceInTableOne(NewState, i);
End;
End;
procedure Astar(depth: integer);
begin
Calculate of InitialState;
TableOne := [InitialState]; // 表一：待扩展节点集
TableTwo := [initialState]; // 表二：待扩展和已扩展节点集
ok := false;
while not ok and not TableOne Empty do // 没有找到解且待扩展节点非空
begin
State := ExtractMinInTableOne; // 找f值最小的待扩展节点
If IsAnswer(State) then // 找到解并输出解
Begin
PrintState(state);
ok := true;
End
Else Expand(State); //扩展节点
End;
If not Ok then NoAnswer;
End;
由此， 一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是：
1）搜索树上存在着从起始点到终了点的最优路径。
¤2）问题域是有限的。
¤3）所有结点的子结点的搜索代价值>0。
¤4）h(n)<=h*(n) （h*(n)为实际问题的代价值）。
当此四个条件都满足时，一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法，并一定能找到最优解。简单的来说就两句话：
1. 启发函数是随着深度的增加，是单调不递减的；
2. 估价函数随着深度的增加，也是单调不递减的；
迭代加深+启发函数 = ID_A*
Procedure IDAstar(StartState);
Begin
PathLimit := H(startState) -1; //限定每次搜索的最大深度，初始值为初始状态h();
Success := false;
Repeat
inc(PathLimit);
StartState.g = 0;
Push(OpenStack, StartState);
Repeat
CurrentState := Pop(OpenStack);
If Solution(CurrentState) then // 判定当前状态是否是目的状态
Success = True; // 是的话，玲标记为真。
Else if PathLimit >= CurrentState.g = H(CurrentState) then
ForEach Child(CurrentState) do // 计算所有子状态的f()并入列。
Push(OpenState, Child(CurrentState));
Untill Success or empty of OpenStack
Untill Success or ResourceLimitsReached;
End;
运用迭代加深对深度的限制 和 A*算法的启发函数，结合两个算法的优点，便得到了这个算法。他的优势：
不需要判重（深搜的的特点），省去了hash值设定的烦恼；
不需要排序，省去了堆排序的烦恼，只用到栈，实现简单；
空间的需求较之A*算法，大大减少。因为每次都是规定的最大深度，因此，这个解是最优的。
后记：将在下一节，结合具体的实例，说明这两种算法的好处。并进行一个简单的对比。
- 无匹配
Copyright © 2007
2019年2月06日 13:50
推荐是推荐了，但《A*算法》(ppt) 尚福华哪里可以找到？
2024年1月14日 17:27
Interested in playing online casino Or want to know new online casino promotions lighterandlocal Online casino reviews Answer every casino you want to kno
2024年1月17日 13:59
Your post offers confirmed beneficial to me personally. It’s very informative and you’re simply certainly extremely knowledgeable in this region. You have opened up my eye to be able to various views on this particular matter together with interesting and strong content.
2024年1月17日 14:30
Hi I found your site by mistake when i was searching yahoo for this acne issue, I must say your site is really helpful I also love the design, its amazing!. I don’t have the time at the moment to fully read your site but I have bookmarked it and also add your RSS feeds. I will be back in a day or two. thanks for a great site.
2024年1月17日 14:52
Fantastic beat ! I would like to apprentice at the same time as you amend your web site, how can i subscribe for a blog web site? The account aided me a acceptable deal. I were a little bit acquainted of this your broadcast offered brilliant transparent idea|
2024年1月17日 14:55
Fantastic beat ! I would like to apprentice at the same time as you amend your web site, how can i subscribe for a blog web site? The account aided me a acceptable deal. I were a little bit acquainted of this your broadcast offered brilliant transparent idea|
2024年1月17日 15:15
i am out of the blue here. I discovered this board and I in discovering It genuinely supportive and it helped me out a ton. I want to introduce something back and help other people, for example, you helped me I think this is an informative post and it is very useful and knowledgeable. therefore. I would like to thank you for the efforts you have made in writing this article.
2024年1月17日 15:22
I just want to tell you that I am very new to blogging and definitely savored your page. Very likely I’m want to bookmark your website . You certainly have incredible articles. Thanks a bunch for revealing your web site.Appreciate it. Plenty of postings! https://canadiantoprxstore.com/# canada pharmacies without script
2024年1月17日 15:31
Confusing information, immense and outlandish structure, as offer especially finished with sharp examinations and thoughts, heaps of striking information and inspiration, the two of which I require, because of offer such an incredible information here
2024年1月17日 15:39
Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!THANKS!!!!! ntegrate AI-driven characters and dialogues to enhance user experiences in gaming applications
2024年1月17日 15:48
This is extremely intriguing substance! I have altogether delighted in perusing your focuses and have arrived at the resolution that you are ideal about a significant number of them. You are extraordinary What a good blog you have here. Please update it more often. This topics is my interest. Thank you. . .
2024年1月17日 15:51
I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work. Thanks for writing such a good article, I stumbled onto your blog and read a few post. I like your style of writing.
2024年1月17日 16:02
Excellent post. I was checking continuously this blog and I’m impressed! Very helpful information specially the last part :) I care for such information a lot. I was looking for this certain information for a long time. Thank you and best of luck.
2024年1月17日 16:10
You have a certified limit with regards to making one out of a benevolent substance. I like how you think and the manner in which you address your points of view in this article. I agree with your attitude. Thankful to you for sharing.
2024年1月17日 16:11
We are playground guard without advertising agency of Toto site.Please come to Playground Guard and enjoy betting on various sites such as Toto Site Safety Playground and Major Playground.The list of sites posted on our safe playground list is a list of sites where our watchdog has completed currency exchange and betting checks with multiple accounts for at least one month. is.
2024年1月17日 16:27
Hey would you mind sharing which blog platform you’re working with? I’m planning to start my own blog soon but I’m having a difficult time selecting between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something unique. P.S Sorry for getting off-topic but I had to ask!|
2024年1月17日 16:30
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own BlogEngine blog now. Really the blogging is spreading its wings rapidly. Your write up is a fine example of it.
2024年1月17日 16:39
Verygood nice paost. I just stumbled upon ayour weblog and wished to say that I’ve really enjoyed surfing around your blog posts. After all I will be subscribing to your feed and I hope you write again very soon!Some times its a pain in the ass to read wh
2024年1月17日 16:52
I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job! My friend mentioned to me your blog, so I thought I’d read it for myself. Very interesting insights, will be back for more!
2024年1月17日 16:54
It's strikingly a marvelous and satisfying piece of information. I am satisfied that you in a general sense enabled this strong data to us. On the off chance that it's not all that much burden stay us sway forward thusly. Thankful to you for sharing
2024年1月17日 17:03
Appreciative for the strengthening on the web diary posting! Fundamentally put your blog segment to my most esteemed blog list and will channel forward for additional updates. Basically expected to record a word to offer imperative because of you for those incredible tips.
2024年1月17日 17:03
My spouse and am enjoy your blog and locate the vast majority of your post’s to be able to be what exactly I’m searching for. can you present guest writers to compose content for you? We wouldn’t mind producing the post or elaborating upon some the subjects jots down concerning here. Once again, awesome weblog!
2024年1月17日 17:08
Your post offers confirmed beneficial to me personally. It’s very informative and you’re simply certainly extremely knowledgeable in this region. You have opened up my eye to be able to various views on this particular matter together with interesting and strong content.
2024年1月17日 17:24
Pleased to meet up with you! My title is Shonda and I enjoy it. Doing magic is what she enjoys performing. He is at the moment a production and distribution officer but he strategies on modifying it. Some time in the earlier he chose to stay in Louisiana.
2024年1月17日 17:42
Fantastic beat ! I would like to apprentice at the same time as you amend your web site, how can i subscribe for a blog web site? The account aided me a acceptable deal. I were a little bit acquainted of this your broadcast offered brilliant transparent idea|
2024年1月17日 18:41
Pleased to satisfy you! My identify is Loreta. Texas is wherever her household is. Interviewing is exactly exactly where my key profits will appear from but the promotion never ever arrives. The favored hobby for my young youngsters and me is kayaking and now I’m trying to generate dollars with it.
2024年1月17日 18:57
Took me time to read all the comments, but I really enjoyed the article. It proved to be Very helpful to me and I am sure to all the commenters here! It’s always nice when you can not only be informed, but also entertained!
2024年1月17日 19:04
Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!THANKS!!!!! ntegrate AI-driven characters and dialogues to enhance user experiences in gaming applications
2024年1月17日 19:19
I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work. Thanks for writing such a good article, I stumbled onto your blog and read a few post. I like your style of writing.
2024年1月17日 19:34
Great post full of useful tips! My site is fairly new and I am also having a hard time getting my readers to leave comments. Analytics shows they are coming to the site but I have a feeling “nobody wants to be first”. Hi there, I found your blog via Google while searching for such kinda informative post and your post looks very interesting for me.
2024年1月17日 19:43
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own BlogEngine blog now. Really the blogging is spreading its wings rapidly. Your write up is a fine example of it.
2024年1月17日 20:08
Nice blog right here! Additionally your website loads up fast! What web host are you the use of? Can I get your associate hyperlink in your host? I desire my web site loaded up as quickly as yours I feel a lot more people need to read this, very good info
2024年1月17日 20:21
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own BlogEngine blog now. Really the blogging is spreading its wings rapidly. Your write up is a fine example of it.
2024年1月17日 20:29
i am out of the blue here. I discovered this board and I in discovering It genuinely supportive and it helped me out a ton. I want to introduce something back and help other people, for example, you helped me I think this is an informative post and it is very useful and knowledgeable. therefore. I would like to thank you for the efforts you have made in writing this article.
2024年1月17日 20:34
I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job! My friend mentioned to me your blog, so I thought I’d read it for myself. Very interesting insights, will be back for more!
2024年1月17日 20:54
Great post full of useful tips! My site is fairly new and I am also having a hard time getting my readers to leave comments. Analytics shows they are coming to the site but I have a feeling “nobody wants to be first”. Hi there, I found your blog via Google while searching for such kinda informative post and your post looks very interesting for me.
2024年1月17日 21:12
his is my first time i visit here. I found so many entertaining stuff in your blog, especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the leisure here! Keep up the excellent work.
2024年1月17日 21:17
i am out of the blue here. I discovered this board and I in discovering It genuinely supportive and it helped me out a ton. I want to introduce something back and help other people, for example, you helped me I think this is an informative post and it is very useful and knowledgeable. therefore. I would like to thank you for the efforts you have made in writing this article.