在这些条件下，A* 是否会返回一个恒定的 fscore?如果是这样，我如何更好地打破领带? [英] Is A* returning a constant fscore expected under these conditions? If so how do I tie break better?

查看：15
本文介绍了在这些条件下，A* 是否会返回一个恒定的 fscore?如果是这样，我如何更好地打破领带?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我回答了我自己的问题.我无法将其发布为答案，因为我的代表不到 10 人.我已将其作为编辑包含在 ~~~~~~~~~~ 行下.

I answered my own question. I cant post it as an answer because I have less than 10 rep. I have included it as an edit under the line of ~~~~~~~~~~.

我相信这个问题不需要代码示例，因为它是关于算法的.不是具体的实现.

I believe this question does not require a code sample as it is about the algorithm. not a specific implementation.

假设您有一个节点网格，每个节点都连接到四个边权重为 1 的邻居(即没有对角线移动).使用的启发式是曼哈顿距离.起点在左上角，目标在右下角.

Suppose you have a grid of nodes each of which are connected to four neighbours with edge weight one (i.e. there is no diagonal movement). The heuristic being used is Manhattan distance. The start is in the upper left corner, and the goal is in the bottom right corner.

自然，算法会倾向于向右或向下扩展节点.每个这样的节点的 fScore 将是恒定的，因为当启发值减少 1 时，与开始的距离增加 1.这意味着开放列表中有大量具有相同优先级的节点.探索它们的顺序是所使用的打破平局条件的结果.

Naturally the algorithm will favour expanding nodes to the right or down. The fScore of each such node will be constant because while the heuristic value decreases by one, the distance from start increases by one. This means that there are a very large number of nodes in the open list with the same priority. The order in which they are explored is a result of the tie breaking conditions being used.

目前，我根据检查节点的顺序进行平局.这意味着如果一个节点的所有邻居都具有相同的 fScores，则优先级将是左>下>右>上.

Currently I tie break based on the order I check nodes in. That means if all neighbours of a node have equal fScores the priority would be left>down>right>top.

在示例情况下，这会导致我的 A* 打开大量节点.如果可能，它首先打开每个关闭的节点，如果不可能，它会正常运行.如果这两个选项都不可能，它会从开放集中最旧的节点重新开始(这通常很糟糕，因为它就在开始的旁边.

In the example situation this causes my A* to open a very large number of nodes. It first opens each node going down if possible, if that is not possible it goes right. If neither of those options are possible it starts again from the oldest node in the open set (which is usually bad because it is right next to the start.

我认为在 f 分数相等的情况下，我需要一个更好的打破平局的结构.谁能给我推荐一个?

I think I need a better tie-breaking structure in the case f-scores are equal. Can anyone suggest one to me?

在 8x8 网格上查看此示例:

See this example on an 8x8 grid:

0=open node
C=closed node
S=start
G=goal

S    █  
   ██   
      █ 
     █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
O  ██   
      █ 
     █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
O     █ 
     █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
O    █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CO   █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█O    █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█CO   █ 
█O      
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█CO   █ 
█CO     
 O█ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█CO   █ 
█CO     
OC█ █  █
█O███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█CO   █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CCO   █ 
CCO  █ █
█CO   █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCO  █ 
CCO  █ █
█CO   █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOO █ █
█CO   █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█COO  █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█COCO █ 
█COO    
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█COCO █ 
█COCO   
OC█O█  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█COCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCO  █  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCO █  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCO█  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCO██   
CCCCO █ 
CCCCC█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCO █ 
█CCCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCO█ 
█CCCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOO  
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOCO 
OC█C█O █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOCO 
OC█C█CO█
█C███O G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOCO 
OC█C█CO█
█C███COG

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOCO 
OC█C█CO█
█C███CCG

The fScore of the node being expanded is:14
SCCCC█  
░CC██   
░░░░O █ 
CCC░C█ █
█CC░░░█ 
█CCCO░O 
OC█C█░O█
█C███░░G

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~发现了更好的打破平局条件！

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Better tie breaking condition found!

我正在使用 std::priority_queue 来实现我的开放节点列表.它把最大的元素放在最上面，并要求你定义一个实现 < 的比较函数.操作员.我想要最少的 fScore，所以我定义了一个比较，即 > 运算符.

I am using the std::priority_queue to implement my open node list. It puts the greatest element on top, and requires that you define a comparison function that implements the < operator. I want the least fScore on top so I defined a comparison that is the > operator.

我曾经有过:

class compareNode {
public:
    bool operator()(map_node* n1, map_node* n2){
        if(n1->fScore  >= n2->fScore) return true; 
        else return false;      
};

现在我做了一个新的比较函数.根据我的直觉，我们希望支持离开始很远的节点，我支持具有高 gScore 的节点.如果一个节点的 gScore 和 fScore 相同，我将返回 true(这隐式支持最近添加到队列中的节点)

Now I made a new comparison function. Based on my intuition that we want to favour nodes that are far away from the start I tie break in favour of nodes that have high gScores. If both the gScore and the fScore of a node are the same I return true (which implicitly favours the node most recently added to the queue)

class compareNode {
public:
    bool operator()(map_node* n1, map_node* n2){
        if(n1->fScore  == n2->fScore){
            if(n1->gScore  == n2->gScore)return true;
            else return (n1->gScore  < n2->gScore);
        }
        else return (n1->fScore  > n2->fScore);
    }
};

使用旧的打破平局方法查看这张 8x8 地图的结果，然后是新的打破平局方法.

See the result of this 8x8 map using the old tie-breaking method, followed by the new tie breaking method.

旧方法:

The fScore of the node being expanded is:14
S░░░░O █
CCO█░O █
█C█O░O█ 
OCO█░O██
OCO█░░O█
OCO██░█ 
OCOOO░O 
█CCC█░░G

shortest path found! This map generated with seed: 13975683

新方法:

The fScore of the node being expanded is:14
SO     █
░░O█   █
█░█   █ 
O░C█  ██
O░C█   █
O░C██O█ 
O░░░░░O 
█CCC█░░G

shortest path found! This map generated with seed: 1397568369

推荐答案

您可以使用 Bounded放松(在某些书中也称为 A*-Epsilon).

You can use Bounded Relaxation (also known as A*-Epsilon in some books).

A* Epsilon 计算 f(v) = g(v) + (1+eps)h(v).

A* Epsilon calculates f(v) = g(v) + (1+eps)h(v).

根据 g(v)，如果您使用非常小的 epsilon 值，您不会失去 A* 提供的最优性，同时仍然获得决胜局.
在所有 v,u 的 f(v)=f(u) 示例中 - A* 的这种变体将导致类似于 DFS 的行为 - 您将支持 h() 的较小值 - 这意味着 g() 的较大值，在这种情况下，这意味着首先尽可能地探索分支.

If you use very small epsilon value, you are not loosing the optimality A* offers, while still gaining tie-breaker, according to g(v).
In examples where f(v)=f(u) for all v,u - this variation of A* will result in a behavior resembling DFS - you will favor smaller values of h() - which implies larger values of g(), and in this context this means first exploring branches as far as you can.

同样，如果您将 epsilon 设置为非常接近 0 的负值，您将同样得到一个偏向于 h(v) 的决胜局 - 这将导致行为类似于 BFS.

Similarly, f you set epsilon as a negative value very close to 0, you will similarly get a tie breaker favoring h(v) - and it will result in behavior similar to BFS.

这篇关于在这些条件下，A* 是否会返回一个恒定的 fscore?如果是这样，我如何更好地打破领带?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆