最佳优先搜索和A *搜索有什么区别? [英] What's the difference between best-first search and A* search?

问题描述

在我的教科书中，我注意到这两种算法的工作原理几乎完全相同，我试图了解它们之间的主要区别是什么.

In my text book I noticed that both these algorithms work almost exactly the same, I am trying to understand what's the major difference between them.

教科书使用 A * 遍历此示例，就像使用最佳优先搜索一样.

The textbook traversed this example using A* the same way it did with best-first search.

任何帮助将不胜感激.

推荐答案

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

Best-first search algorithm visits next state based on heuristics function f(n) = h with lowest heuristic value (often called greedy). It doesn't consider cost of the path to that particular state. All it cares about is that which next state from the current state has lowest heuristics.

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

A* search algorithm visits next state based on heristics f(n) = h + g where h component is same heuristics applied as in Best-first search but g component is path from the initial state to the particular state. Therefore it doesn't chooses next state only with lowest heuristics value but one that gives lowest value when considering it's heuristics and cost of getting to that state.

在上面的示例中，当您从阿拉德(Arad)开始时，您可以选择 直达锡比乌(253公里)或泽林德(374公里)或蒂米什瓦拉(329公里). 在这种情况下，两种算法都选择Sibiu，因为它的值较低f(n)= 253.

In your example above when you start from Arad you can go either straight to Sibiu (253km) or to the Zerind(374km) or Timisoara(329km). In this case both algorithms choose Sibiu as it has lower value f(n) = 253.

现在您可以将状态扩展回阿拉德(366km)或 Oradea(380公里)或Faragas(178公里)或Rimnicu Vilcea(193公里).对于最佳 首先搜索Faragas的f(n)= 178最低，但是 A * 令Rimnicu Vilcea f(n)= 220 + 193 = 413，其中220是 从阿拉德(140 + 80)到林姆尼库(Rimnicu)，而193是从林姆尼库(Rimnicu)到 布加勒斯特，但对于法拉加斯来说，f(n)= 239 + 178 = 417.

Now you can expand to either state back to Arad(366km) or Oradea(380km) or Faragas(178km) or Rimnicu Vilcea(193km). For best first search Faragas will have lowest f(n) = 178 but A* will have Rimnicu Vilcea f(n) = 220 + 193 = 413 where 220 is cost of getting to Rimnicu from Arad (140+80) and 193 is from Rimnicu to Bucharest but for Faragas it will be more as f(n) = 239 + 178 = 417.

所以现在您可以清楚地看到 best-first 是贪婪算法，因为它会选择具有较低启发式但总成本较高的状态，因为它不考虑从初始状态进入该状态的成本

So now clearly you can see best-first is greedy algorithm because it would choose state with lower heuristics but higher overall cost as it doesn't consider cost of getting to that state from initial state

这篇关于最佳优先搜索和A *搜索有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！