统一成本搜索算法

Question

我只是在书和维基百科上阅读它,但仍然不理解它100%.

如果有人能用一两个例子来解释,我真的很感激.

谢谢

Answer 1

假设我正在看地图,在城市附近寻找披萨店.我可以使用一些不同的策略:

• 广度优先搜索(BFS):看看我的街区周围的同心圆块,向外越来越远,直到我找到一个披萨店.这将给我一个最近我的街区的比萨饼店,就像乌鸦一样.
• 深度优先搜索(DFS):沿着道路走,直到我走到死路,然后回溯.最终将搜索所有可能的分支,所以如果那里有一个披萨店,那么我会找到它,但它可能不会非常接近我的块.
• 统一成本搜索(UCS):说某些街道上的交通状况不好,而且我对这座城市非常熟悉.对于任何给定的位置,我可以说我需要多长时间从我的街区到达那里.所以,看看地图,首先我搜索所有需要1分钟或更短时间才能到达的区块.如果我还没有找到披萨店,我会搜索所有需要1至2分钟才能到达的街区.我重复这个过程,直到我找到一个披萨店.这将给我一个比萨饼的地方,距离我的街区最近的车程.就像BFS看起来像同心圆一样,UFS看起来像一个等高线图.

通常,您将使用优先级队列实现UCS,以按成本最低的顺序搜索节点.