最佳优先搜索和 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.

任何帮助将不胜感激.

推荐答案

Best-first search 算法基于启发式函数访问下一个状态f(n) = h with最低启发式值(通常称为贪婪).它不考虑通往该特定状态的路径成本.它只关心当前状态的下一个状态具有最低的启发式.

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.

现在您可以扩展到任一状态回到阿拉德(366 公里)或Oradea(380km) 或 Faragas(178km) 或 Rimnicu Vilcea(193km).最好的首先搜索 Faragas 将具有最低的 f(n) = 178 但 A* 将有 Rimnicu Vilcea f(n) = 220 + 193 = 413 其中 220 是成本从 Arad 到 Rimnicu (140+80) 和 193 是从 Rimnicu 到布加勒斯特，但对于 Faragas 而言，它会更像 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.

所以现在您可以清楚地看到最佳优先是贪婪算法，因为它会选择启发式较低但总体成本较高的状态，因为它不考虑从初始状态到达该状态的成本

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屋！