A*算法

A*算法

启发式函数

启发式函数就是从起始点到目标点说需要耗费的总代价f(n)(就像自适应函数一样)

openTable和closeTable

  1. openTable就是未搜索的节点表
  2. closeTable就是一个已完成搜索的节点表

    按照一定的规则可以互相转换

    • 对于新的节点,也就是openTable和closeTable中均没有出现的状态,直接添加到open表中。
    • 对于已经添加的节点,openTable或者closeTable中已经有这个状态)若在openTable中,与原来的状态S0的f(n)比较,取最小的一个。若在closeTable中,分两种情况:
  3. closeTable的S0的f(n)大于S的,所以不做修改
  4. closeTable的S0的f(n)小于S的,将closeTable中的S0的f(n)更新,并且放入openTable中
    • 下一个节点搜索,选取openTable中f(n)的值的最小的作为下一个待搜素节点
    • 每次需要将带搜索的节点下一个所有的状态按照规则一二更新open表,close表,搜索完该节点后,移到close表中。


      八数码问题



  5. 读取初始状态和目标状态,并判断二者能否通过变换到达。
  6. 将初始节点压入OPEN表
  7. 取出OPEN表中估计值最小的节点,并放入CLOSE表
  8. 如果该节点不是目标节点,扩展该节点,将子节点放入OPEN表,并返回到第三步。
  9. 将该节点压入栈中,并将指针指向其父节点。
  10. 如果该节点的父节点不为空,返回到第五步。
  11. 如果栈不为空,出栈并输出该节点,直到栈为空
上一篇
下一篇

鄂公网安备 42082102000192号