最佳优先搜索和A*搜索之间有什么区别？

在我的教科书中,我注意到这两种算法几乎完全相同,我试图理解它们之间的主要区别.

教科书使用A*以与最佳优先搜索相同的方式遍历此示例.

任何帮助,将不胜感激.

最佳优先搜索算法基于具有最低启发式值(通常称为贪婪)的启发式函数f(n)= h来访问下一状态.它不考虑到该特定状态的路径的成本.它所关心的只是当前状态的下一个状态具有最低的启发式.

A*搜索算法基于特征f(n)= h + g访问下一状态,其中h分量与最佳优先搜索中应用的启发式相同,但是g分量是从初始状态到特定状态的路径.因此,它不会选择具有最低启发式值的下一个状态,而是在考虑它的启发式和到达该状态的成本时给出最低值.

在上面的示例中,当您从Arad出发时,您可以直接前往锡比乌(253公里)或Zerind(374公里)或蒂米什瓦拉(329公里).在这种情况下,两种算法都选择Sibiu,因为它具有较低的值f(n)= 253.

现在你可以扩展到Arad(366公里)或Oradea(380公里)或Faragas(178公里)或Rimnicu Vilcea(193公里).对于最好的第一次搜索,Faragas将具有最低f(n)= 178但是A*将具有Rimnicu Vilcea f(n)= 220 + 193 = 413其中220是从Arad(140 + 80)到达Rimnicu的成本而193是来自Rimnicu到布加勒斯特,但对于Faragas,它将更多为f(n)= 239 + 178 = 417.

所以现在很明显你可以看到最好的第一个是贪心算法,因为它会选择具有较低启发式但总体成本较高的状态,因为它不考虑从初始状态到达该状态的成本