用C＃实现A *算法（了解伪代码）

Question

我正试图在C＃中实现A *算法。我已经建立街道（egdes）和streetcorners（节点），我有一个像坐标的大图：

10 50 Streetname 50 70 

这里10 50是一个节点，具有定向边缘（Streetname）到节点50 70。你可以找到两个节点与毕达哥拉斯之间的距离。

我想以此为榜样：

我有问题的理解8号线和13〜15。希望有人能告诉这是什么意思。

节点

public class Node 
{ 
    public string name { get; private set; }    // Name of the node 
    public Node parent { get; set; }    // parent to the current node 
    public bool visited { get; set; }    // visited, to check if node has been vsisited 

    public int x { get; set; }      // x cordinate of the node (street corner) 
    public int y { get; set; }      // y cordinate of the node (street corner) 

    public double g { get; set; }    // Distance from start to this node 
    public double h { get; set; }    // Heuristic (guess) distance from this node to goal 
    public double f { get; set; }    // Disstance from start + heuristic distance 

    public List<Edge> neighbors = new List<Edge>();   // All succesors to node 

    public Node(string name, int x, int y) 
    { 
     this.name = name; 
     this.x = x; 
     this.y = y; 
    } 

    public void calculate_G_Cost(Node other) 
    { 
     g = other.getG() + Math.Sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y)); 
    } 

    public double getG() 
    { 
     return g; 
    } 

    public double GetH() 
    { 
     return h; 
    } 
} 

边缘

public class Edge 
{ 
    public Node node { get; set; } 
    public string streetName { get; set; } 

    public Edge(Node v, string street) 
    { 
     node = v; 
     streetName = street; 
    } 
} 

A *搜索

public void search(Node root, Node goal) 
    { 
     // Open list 
     SimplePriorityQueue<Node> openList = new SimplePriorityQueue<Node>(); 

     // Closed list 
     List<Node> closedList = new List<Node>(); 

     // Put starting node into openList 
     openList.Enqueue(root, Convert.ToSingle(root.f)); 

     // Inizialize currentNode object 
     Node currentNode; 

     while (openList.Count > 0) 
     { 
      currentNode = openList.Dequeue(); 
      currentNode.visited = true; 

      if (currentNode.Equals(goal)) 
      { 
       // Stop algorithm 
       Console.WriteLine("Goal node has been found"); 
       break; 
      } 

      // Calculate g cost from current and set parent 
      foreach (var neighbor in currentNode.neighbors) 
      { 
       neighbor.node.calculate_G_Cost(currentNode);   // Calculate G 
       neighbor.node.parent = currentNode;      // Set parent 
       neighbor.node.h = 0;         // Calculate H 
       neighbor.node.f = neighbor.node.g + neighbor.node.h; // Calculate F 


       // If neighbor node is in openList 
       if (openList.Contains(neighbor.node)) { 

       } 

       // If neighbor node is in closedList 
       if (closedList.Contains(neighbor.node)) 
       { 

       } 
      } 

      closedList.Add(currentNode); 
      Console.WriteLine(currentNode.name + " has been added to closeList"); 
     } 

    } 

我知道我使用的0启发式值，whic小时，这使得这是一个最好的首先搜索的方法，但会增加我的估计。

Answer 1

我会尽力将其分解为定义和推理。

OPEN列表

这是节点的列表需要被处理。

实施不应该简单地要求从该列表中的下一个节点，而是请求/删除与最低f得分的节点，因为它代表了最有可能的候选者将首先到达目的地（A *存在的点以尽可能少的节点遍历，同时仍然具有最佳路径）。

接班人

这些通常被称为neighbors和表示被直接连接到电流节点（从开放列表所采取的）节点。这些节点如何连接取决于您的实施。

如果具有相同位置的继任者一个节点是在为f比后继较低的开放清单，请跳过此继任

我想你混淆了分离的A的部分*算法在这里。

如果OPEN列表中不存在，您应该将后继/邻居添加到OPEN列表中。

而且，您应该在分配/替换它之前评估其值为G。如果该节点的值已经小于新计算的值，则不要将G值分配给该节点，只需转到下一个邻居即可。这处理了对同一节点有多个路径的场景，但是之前的路径已经更有效了。

如果具有相同的位置后继节点是在其中为f比后继较低封闭列表，则跳过此后继

通常，如果后继/邻居处于关闭列表中，则跳过它。

我知道我使用的0

你真的应该不是一个启发价值。至少你应该计算从该节点到目的节点/位置的基本/真实距离。

我建议考虑看看维基百科页面上的伪 - https://en.wikipedia.org/wiki/A*_search_algorithm