algorithm - A* 是否返回在这些条件下预期的恒定 fscore？如果是这样，我如何更好地抢七？

Question

编辑:我回答了我自己的问题。我不能将其作为答案发布，因为我的代表少于 10 个。我已将其作为编辑包含在 ~~~~~~~~~~ 行下。

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

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

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

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

在示例情况下，这会导致我的 A* 打开大量节点。如果可能，它首先打开每个正在关闭的节点，如果不可能，它会继续运行。如果这些选项都不可行，它会从开放集中最旧的节点重新开始(这通常是不好的，因为它紧挨着开始。

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

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

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

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~发现更好的平局条件!

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

我曾经有过:

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(这隐含地支持最近添加到队列中的节点)

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 map 使用旧平分法的结果，然后使用新平分法。

旧方法:

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

Answer 1

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

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

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

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