A*算法介绍

import heapq
class PriorityQueue:  def __init__(self):  self._queue = []  self._index = 0  def push(self, item, priority):  heapq.heappush(self._queue, (-priority, self._index, item))  self._index += 1  def pop(self):  return heapq.heappop(self._queue)[-1]
def heuristic(a, b):(x1, y1) = a(x2, y2) = breturn abs(x1 - x2) + abs(y1 - y2)# 曼哈顿距离def a_star_search(start, goal, graph):frontier = PriorityQueue()frontier.put(start, 0)came_from = {}cost_so_far = {}came_from[start] = Nonecost_so_far[start] = 0while not frontier.empty():current = frontier.get()if current == goal:breakfor next in graph.neighbors(current):new_cost = cost_so_far[current] + graph.cost(current, next)if next not in cost_so_far or new_cost < cost_so_far[next]:cost_so_far[next] = new_costpriority = new_cost + heuristic(goal, next)frontier.put(next, priority)came_from[next] = currentreturn came_from, cost_so_far

题目描述

八数码问题

代码实现

import heapq
goal="123804765"
gx=[-1,0,0,0,1,2,2,2,1] # gx[t]存储数字t在目标状态中的行索引
gy=[-1,0,1,2,2,2,1,0,0] # gy[t]存储数字t在目标状态中的列索引
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def f(s:str):res=0for i in range(len(s)):t=int(s[i])if(t):res+=abs(i/3-gx[t])+abs(i%3-gy[t])return res
def a_star(start:str="123804765"):d={}d[start]=0q=[]heapq.heappush(q,(f(start),start))while q:_,s=heapq.heappop(q)if(s==goal):return d[s]k=s.find('0')x,y=k//3,k%3for i in range(4):nx=x+dx[i]ny=y+dy[i]if(nx>=0 and nx<3 and ny>=0 and ny<3):t=nx*3+nynew_s=list(s)new_s[k],new_s[t]=new_s[t],new_s[k]new_s=''.join(new_s)if(new_s not in d):d[new_s]=d[s]+1heapq.heappush(q,(d[new_s]+f(new_s),new_s))return -1s=input()
print(a_star(s))