A*算法——算法简介（附Python实现）

在本文中，我们尝试了解 A* 算法的概念及其重要性。它是启发式搜索算法之一，主要用于确定几种替代方案中哪种最有效地达到特定的目标状态。

什么是A*算法？

A*算法（发音为A-star）是“分支定界搜索算法”和“最佳搜索算法”结合动态规划原理的组合。A* 算法众所周知，因为它用于定位路径和图遍历。该算法被用于许多在线地图和游戏中。它使用通常由 f(X) 表示的启发式或评估函数来确定搜索访问树中节点的顺序。节点 N 的启发式函数定义如下：

f(N) = g(N)+h(N)

函数g是从起始节点到当前节点N的成本的度量，即，它是沿着到当前节点的最佳路径应用的规则的成本之和。函数h是从当前节点N到目标节点的额外成本的估计。这是利用有关问题领域的知识的地方。通常，A*算法被称为OR图/树搜索算法。

A*算法从起始节点开始逐步搜索所有路径，直到找到到达目标的最短路径。从给定节点开始，该算法扩展具有最低 f(x) 值的节点。它维护一组部分解决方案。扩展节点的未扩展叶子节点与相应的f值存储在队列中。该队列可以作为优先级队列来维护。

例子

让我们再次考虑一个八谜题的例子，并使用 A* 算法来解决它。简单评价函数f(x)定义如下：

f(x) = g(x)+h(X),

在哪里

h(X) = 在给定状态 X 下未处于目标位置的图块数量
g(X) = 搜索树中节点 X 的深度

给定

初始状态

让我们尝试通过在 g(x) 和 h(x) 的帮助下计算 f(x) 的值来开发解决此问题的搜索树。

搜索树

Python 中的实现

from copy import deepcopy
import numpy as np
import time
 
def bestsolution(state):
    bestsol = np.array([], int).reshape(-1, 9)
    count = len(state) - 1
    while count != -1:
        bestsol = np.insert(bestsol, 0, state[count]['puzzle'], 0)
        count = (state[count]['parent'])
    return bestsol.reshape(-1, 3, 3)
 
        
# checks for the uniqueness of the iteration(it).
def all(checkarray):
    set=[]
    for it in set:
        for checkarray in it:
            return 1
        else:
            return 0
 
 
# number of misplaced tiles 
def misplaced_tiles(puzzle,goal):
    mscost = np.sum(puzzle != goal) - 1
    return mscost if mscost > 0 else 0
 
 
def coordinates(puzzle):
    pos = np.array(range(9))
    for p, q in enumerate(puzzle):
        pos[q] = p
    return pos
 
 
# start of 8 puzzle evaluvation, using Misplaced tiles heuristics
def evaluvate_misplaced(puzzle, goal):
    steps = np.array([('up', [0, 1, 2], -3),('down', [6, 7, 8],  3),('left', [0, 3, 6], -1),('right', [2, 5, 8],  1)],
                dtype =  [('move',  str, 1),('position', list),('head', int)])
 
    dtstate = [('puzzle',  list),('parent', int),('gn',  int),('hn',  int)]
 
    costg = coordinates(goal)
    # initializing the parent, gn and hn, where hn is misplaced_tiles  function call  
    parent = -1
    gn = 0
    hn = misplaced_tiles(coordinates(puzzle), costg)
    state = np.array([(puzzle, parent, gn, hn)], dtstate)
 
   #priority queues with position as keys and fn as value.
    dtpriority = [('position', int),('fn', int)]
 
    priority = np.array([(0, hn)], dtpriority)
     
    while 1:
        priority = np.sort(priority, kind='mergesort', order=['fn', 'position'])      
        position, fn = priority[0]       
        # sort priority queue using merge sort,the first element is picked for exploring.                                          
        priority = np.delete(priority, 0, 0)                         
        puzzle, parent, gn, hn = state[position]
        puzzle = np.array(puzzle)
          
        blank = int(np.where(puzzle == 0)[0])   
       
        gn = gn + 1                            
        c = 1
        start_time = time.time()
        for s in steps:
            c = c + 1
            if blank not in s['position']:
                openstates = deepcopy(puzzle)         
                openstates[blank], openstates[blank + s['head']] = openstates[blank + s['head']], openstates[blank]
                
                if ~(np.all(list(state['puzzle']) == openstates, 1)).any():          
                    end_time = time.time()
                    if (( end_time - start_time ) > 2):
                        print(" The 8 puzzle is unsolvable \n")
                        break
                     
                    hn = misplaced_tiles(coordinates(openstates), costg) 
                    # generate and add new state in the list                    
                    q = np.array([(openstates, position, gn, hn)], dtstate)         
                    state = np.append(state, q, 0)
                    # f(n) is the sum of cost to reach node
                    fn = gn + hn                                        
                     
                    q = np.array([(len(state) - 1, fn)], dtpriority)
                    priority = np.append(priority, q, 0)
                     
                    if np.array_equal(openstates, goal):                      
                        print(' The 8 puzzle is solvable \n')
                        return state, len(priority)
                         
    return state, len(priority)
 
 
# initial state 
puzzle = []
 
puzzle.append(2)
puzzle.append(8)
puzzle.append(3)
puzzle.append(1)
puzzle.append(6)
puzzle.append(4)
puzzle.append(7)
puzzle.append(0)
puzzle.append(5)
 
#goal state       
goal = []
 
goal.append(1)
goal.append(2)
goal.append(3)
goal.append(8)
goal.append(0)
goal.append(4)
goal.append(7)
goal.append(6)
goal.append(5) 
 
 
state, visited = evaluvate_misplaced(puzzle, goal) 
bestpath = bestsolution(state)
print(str(bestpath).replace('[', ' ').replace(']', ''))
totalmoves = len(bestpath) - 1
print('\nSteps to reach goal:',totalmoves)
visit = len(state) - visited
print('Total nodes visited: ',visit, "\n")
      

输出：

执行

A* 的可接受性

如果对于任何图，搜索算法总是终止于从起始状态到目标状态的最佳路径（如果该路径存在），则该搜索算法是可接受的。我们之前已经看到，如果启发式函数“h”低估了从当前状态到目标状态的实际值，那么它必然会给出最优解，因此被称为容许函数。因此，我们可以说，如果 h 是可接受的启发式函数，则 A* 始终以最佳路径终止。

局限性

用于计算 h 的启发式技术的精度对执行 A* 搜索 (n) 的速度有重大影响。因此，存在复杂性问题。

概括

在本文中，我们学习了一种称为 A* 算法的最佳算法。该搜索算法有助于解决许多常见的寻路问题，如 N 皇后问题、0-1 背包问题、旅行商问题等。该算法以解决复杂问题而闻名，它也用于网络路由协议。它还有助于定义其他算法。它在人工智能领域有着广泛的应用。