[小明学算法]3.启发式搜索算法----A*算法之我见

1.算法介绍

a*算法是一种寻路算法,类似于图的广度优先遍历搜索.

2.基本概念

设计先两个集合CloseList和OpenList,CloseList表示已经走过的节点,OpenList中的节点表示所有我们可以选择的下一步节点.

3.计算步骤:

1.将起点设为当前节点,并创建OpenList和CloseList.

2.将当前节点从OpenList中删除,并加入到CloseList中.

3.遍历当前节点的可到达节点,不包括CloseList中的节点,记录为AroundList,

4.然后对每个AroundList中的节点进行估值,f(x)=g(x)+h(x)

　　①.计算g(x).g(x)是消耗记录值,表示走过的路程所需要消耗的值,为当前节点的g值加上与当前节点的距离值.同时需将估值节点的加入OpenList并将估值节点的父节点设为当前节点.

　　　　在计算g(x),需要注意若此节点已存在于OpenList中,而且新g(x)小于原g(x),则更改g(x)的值,并更改当此节点的父节点为当前节点,否则不做修改.

　　②h(x)其中,g(x)表示估值算法,计算其与目标位置距离的估值.

　　　　h(x)就是启发式搜索的估值函数,此函数写的越好,算法的效率就越高

5.若未到达目标节点,执行6,若到达目标节点,执行7

6.选择OpenList当中f(x)最小的点,设为当前节点,重复以上步骤2,3,4,5..

7.通过当前节点的父节点属性一直往上遍历,则得到目标路径节点的倒序排列.

4.代码实现

  1 using System.Collections.Generic;
  2 
  3 namespace 动态规划
  4 {
  5     internal class Program
  6     {
  7         readonly List<Node> OpenList = new List<Node>();
  8         readonly List<Node> CloseList = new List<Node>();
  9 
 10         List<Node> FindWayByAStart(Node startNode, Node endNode)
 11         {
 12             //1.将当前节点加入到CloseList中,并从OpenList中删除
 13             CloseList.Add(startNode);
 14             if (OpenList.Contains(startNode))
 15                 OpenList.Remove(startNode);
 16             //2.寻找当前节点所有可以到达的节点
 17             //且可到达的节点并不再CloseList中,则加入AroundList
 18             //TODO
 19             var aroundList = new List<Node>();
 20 
 21             //3.对AroundList中的每个节点计算f(x)=g(x)+h(x)的值
 22             foreach (Node curNode in aroundList)
 23             {      
 24                 if (!OpenList.Contains(curNode))
 25                 { 
 26                     //如果此节点不在OpenList中,正常估值
 27                     //将此节点加入到OpenList中,并将其父节点设为当前节点
 28                     curNode.G = GetGValue(curNode, startNode) + startNode.G;
 29                     curNode.H = GetHValue(curNode, endNode);
 30                     curNode.Parent = startNode;
 31                     OpenList.Add(curNode);
 32                 }
 33                 else
 34                 {  
 35                     //此节点在OpenList中
 36                     //若此节点的新估值g(x)小于之前的g(x),则更改g(x)的值,并重新赋值父节点
 37                     int newg = GetGValue(curNode, startNode)+startNode.G;
 38                     if (newg < curNode.G)
 39                     {
 40                         curNode.G = newg;
 41                         curNode.Parent = startNode;
 42                     }
 43                     //否则,不做操作
 44                 }
 45             }
 46 
 47             //4.若当前节点为目标节点则执行操作6
 48             if (startNode != endNode)
 49             {
 50                 //没有可走点却没找到终点,寻路失败
 51                 if (OpenList.Count == 0)
 52                 {
 53                     return new List<Node>();
 54                 }
 55 
 56                 Node nextNode = null;
 57                 //6.重复以上步骤
 58                 foreach (Node curNode in OpenList)
 59                 {
 60                     if (nextNode == null)
 61                     {
 62                         nextNode = curNode;
 63                     }
 64                     else if (nextNode.F >= curNode.F)
 65                     {
 66                         nextNode = curNode;
 67                     }
 68                 }
 69                 return FindWayByAStart(nextNode, endNode);
 70             }
 71             else
 72             {
 73                 //7.通过当前节点的父节点一层层往上遍历,得到目标路径节点的倒序排列.
 74                 List<Node> way = new List<Node>();
 75                 List<Node> backWay = new List<Node>();
 76                 Node curNode = startNode;
 77                 while (true)
 78                 {
 79                     backWay.Add(curNode);
 80 
 81                     if (curNode.Parent == null)
 82                     {
 83                         backWay.Remove(curNode);
 84                         backWay.Remove(startNode);
 85                         break;
 86                     }
 87                     else
 88                     {
 89                         curNode = curNode.Parent;
 90                     }
 91                 }
 92 
 93                 Node[] nodes = backWay.ToArray();
 94 
 95                 for (int i = nodes.Length - 1; i >= 0; i--)
 96                 {
 97                     way.Add(nodes[i]);
 98                 }
 99                 return way;
100             }
101    
102         }
103 
104         internal class Node
105         {
106             public int F {
107                 get { return G + H; }
108             }
109 
110             public int G;
111             public int H;
112 
113             public Node Parent;
114         }
115 
116         int GetGValue(Node a, Node b)
117         {
118             //TODO
119             return 0;
120         }
121 
122         int GetHValue(Node a, Node b)
123         {
124             //TODO
125             return 0;
126         }
127     }
128 }

View Code