是*返回一个常数fscore这些条件下预期？如果是的话我怎么抢七好？ [英] Is A* returning a constant fscore expected under these conditions? If so how do I tie break better?

问题描述

编辑：我回答我自己的问题。我不能张贴作为一个答案，因为我有小于10代表。我已经包含它作为下~~~~~~~~~~线的编辑。

我相信这个问题并不需要一个code样品，因为它是对的算法。不是一个具体的实施。

假设有节点的每一个都连接到四个相邻边缘与重量的一种（即没有对角运动）的网格。所使用的试探法是曼哈顿距离。开始是在左上角，并且目标是在右下角。

自然地，算法将有利于展开节点向右或向下移动。每个这样的节点的fScore将是恒定的，因为当这些试探值被一个，从开始增加一的距离减小。这意味着有一个非常大的数量，在开放列表具有相同优先级的节点。在它们所探索的顺序是的平分决胜条件下使用的结果。

目前我绑根据我检查的节点的顺序上休息。这意味着如果一个节点的所有邻居都优先将留待>下来>右键>顶级等于fScores。

在这个例子情况下这会导致我的A *打开一个非常大的数量的节点。它首先打开每个节点下去，如果可能的话，如果这是不可能的不言而喻的权利。如果没有这些选项都是可能再次开始从开集的最老的节点（通常是不好的，因为它旁边的开始。

我觉得我的情况下需要一个更好的打破平局结构F-分数相等。任何人都可以提出一个对我？

请参阅上一个8x8格这个例子：

  0 =开节点
C =封闭节点
S =启动
G =目标

小号█
   ██
      █
     ██
██
█
  ███
████摹

节点正在扩大的fScore是：14
SO█
Ø██
      █
     ██
██
█
  ███
████摹

节点正在扩大的fScore是：14
SO█
CO██
Ø█
     ██
██
█
  ███
████摹

节点正在扩大的fScore是：14
SO█
CO██
CO█
Ø██
██
█
  ███
████摹

节点正在扩大的fScore是：14
SO█
CO██
CO█
CO██
██
█
  ███
████摹

节点正在扩大的fScore是：14
SO█
CO██
CO█
CCO██
█O█
█
  ███
████摹

节点正在扩大的fScore是：14
SO█
CO██
CO█
CCO██
█CO█
█O
  ███
████摹

节点正在扩大的fScore是：14
SO█
CO██
CO█
CCO██
█CO█
█CO
 O███
████摹

节点正在扩大的fScore是：14
SO█
CO██
CO█
CCO██
█CO█
█CO
OC███
█O███摹

节点正在扩大的fScore是：14
SO█
CO██
CO█
CCO██
█CO█
█CO
OC███
█C███摹

节点正在扩大的fScore是：14
SO█
CO██
CCO█
CCO██
█CO█
█CO
OC███
█C███摹

节点正在扩大的fScore是：14
SO█
COO██
CCCO█
CCO██
█CO█
█CO
OC███
█C███摹

节点正在扩大的fScore是：14
SO█
COO██
CCCCO█
CCOO██
█CO█
█CO
OC███
█C███摹

节点正在扩大的fScore是：14
SO█
COO██
CCCCO█
CCOCO██
█COO█
█CO
OC███
█C███摹

节点正在扩大的fScore是：14
SO█
COO██
CCCCO█
CCOCO██
█COCO█
█COO
OC███
█C███摹

节点正在扩大的fScore是：14
SO█
COO██
CCCCO█
CCOCO██
█COCO█
█COCO
OC█O██
█C███摹

节点正在扩大的fScore是：14
SO█
COO██
CCCCO█
CCOCO██
█COCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SO█
COO██
CCCCO█
CCOCO██
█CCCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SO█
COO██
CCCCO█
CCCCO██
█CCCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCO█
COO██
CCCCO█
CCCCO██
█CCCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCO█
COO██
CCCCO█
CCCCO██
█CCCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCCO█
COO██
CCCCO█
CCCCO██
█CCCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCCC█
COO██
CCCCO█
CCCCO██
█CCCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCCC█
CCO██
CCCCO█
CCCCO██
█CCCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCCC█
CCO██
CCCCO█
CCCCC██
█CCCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCCC█
CCC██
CCCCO█
CCCCC██
█CCCO█
█COCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCCC█
CCC██
CCCCO█
CCCCC██
█CCCO█
█CCCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCCC█
CCC██
CCCCO█
CCCCC██
█CCCCO█
█CCCO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCCC█
CCC██
CCCCO█
CCCCC██
█CCCCC█
█CCCOO
OC█C██
█C███摹

节点正在扩大的fScore是：14
SCCCC█
CCC██
CCCCO█
CCCCC██
█CCCCC█
█CCCOCO
OC█C█O█
█C███摹

节点正在扩大的fScore是：14
SCCCC█
CCC██
CCCCO█
CCCCC██
█CCCCC█
█CCCOCO
OC█C█CO█
█C███O摹

节点正在扩大的fScore是：14
SCCCC█
CCC██
CCCCO█
CCCCC██
█CCCCC█
█CCCOCO
OC█C█CO█
█C███COG

节点正在扩大的fScore是：14
SCCCC█
CCC██
CCCCO█
CCCCC██
█CCCCC█
█CCCOCO
OC█C█CO█
█C███CCG

节点正在扩大的fScore是：14
SCCCC█
░CC██
░░░░O█
CCC░C██
█CC░░░█
█CCCO░O
OC█C█░O█
█C███░░G
 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 更好地平分决胜的条件找到了！

我使用的std :: priority_queue实现我的开放节点列表。它把上面的最大元素，并要求您定义的比较函数实现的＆lt;运营商。我想至少fScore在上面，所以我定义了一个比较，它是>运算符。

我曾经有：

 类compareNode {
上市：
    布尔运算符（）（map_node * N1，map_node * N2）{
        如果（N 1＆GT; fScore＆GT; = N 2  - ＆GT; fScore）返回true;
        否则返回false;
};
 

现在我做了一个新的比较函数。根据我的直觉，我们要看好是远从一开始我抢七支持具有高gScores节点的节点。如果同时gScore和节点的fScore是相同的余返回true（这隐含有利于最近添加到队列的节点）

 类compareNode {
上市：
    布尔运算符（）（map_node * N1，map_node * N2）{
        如果（N 1＆GT; fScore == N 2  - ＆GT; fScore）{
            如果（N 1＆GT; gScore == N 2  - ＆GT; gScore）返回true;
            否则返回（N 1＆GT; gScore＆LT; N 2＆GT; gScore）;
        }
        否则返回（N 1＆GT; fScore＆GT; N 2＆GT; fScore）;
    }
};
 

请参阅此8x8的地图使用旧的打破平局方法，其次是新的平分决胜方法的结果。

老方法：

 节点的fScore被扩展为：14
S░░░░O█
CCO█░O█
█C█O░O█
OCO█░O██
OCO█░░O█
OCO██░█
OCOOO░O
█CCC█░░G

最短路径找到了！种子生成此图：13975683
 

新方法：

 节点的fScore被扩展为：14
SO█
░░O██
█░██
O░C███
O░C██
O░C██O█
O░░░░░O
█CCC█░░G

最短路径找到了！种子生成这张地图：1397568369
 

解决方案

您可以使用有界放松（也称为A * -Epsilon在一些书籍）。

A *的Epsilon计算 F（V）= G（V）+（1 + EPS）H（V）。

如果你使用非常小的小量的价值，你是不是失去了最优A *提供，同时还赢得决胜局，根据 G（V）。
在示例，其中 F（V）= F（U）所有 V，U - 这个变化A *会导致行为类似于DFS - 你将有利于 h的较小值（） - 这意味着更大的 Tg值（），在这方面，这意味着第一个探索的分支就可以。

同样，F你设置小量为负值非常接近于0，你同样会得到一个决胜局利于 H（V） - 这将导致类似于BFS行为

EDIT: 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.

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.

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.

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.

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.

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

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!

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.

I used to have:

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

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);
    }
};

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

Old 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

New Method:

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

解决方案

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

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

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.

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.

这篇关于是*返回一个常数fscore这些条件下预期？如果是的话我怎么抢七好？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！