我这里有一个有点有效的 A* 算法。它可以找到一条到达目的地的路径，但是，如果有更好的路径可用，它无法更新其路径。
例如：
s = start
e = end
x = wall
. = path
它正在这样做：
x
s......x e
.x .
.x .
.x.
.
我希望它能做到这一点：
x
s . x e
. x .
. x .
. x.
.
我需要的是图块（节点）将其父节点更改为 G 成本较低的节点（如果可用）。实现这一点的斗争是真实的。
非常感谢任何帮助，
干杯
map = [
['w','w','w','w','w'],
['w','w','x','w','w'],
['w','w','x','w','w'],
['w','w','x','w','w'],
['w','w','w','w','w'],
]
""" make copy of dict in the function! """
tile_data = {}
class Tile:
def __init__(self, pos, char):
self.pos = pos
self.char = char
self.parent = None
self.H = 0
self.G = float('inf')
self.F = 0
#Gen Tiles
for y in range(len(map)):
for x in range(len(map[0])):
char = map[y][x]
tile = Tile((x,y), char)
tile_data[(x,y)] = tile
def a_star(start, end, map):
unchecked_tiles = []
checked_tiles = []
# set start position
tile_data[start].parent = None
tile_data[start].pos = start
tile_data[start].G = 0
unchecked_tiles.append(tile_data[start])
while unchecked_tiles:
#Get the tile with lowest F score
current_tile = min(unchecked_tiles, key=lambda tile: tile.F)
#move tile to checked list
checked_tiles.append(current_tile)
unchecked_tiles.remove(current_tile)
# If the End is found return the path of parent tiles
if current_tile.pos == end:
path = []
while current_tile.parent is not None:
path.append(current_tile.pos)
# Sets current tile to parent tile
current_tile = current_tile.parent
for tile in path:
print(tile, ": F = ", tile_data[tile].F, ": G = ", tile_data[tile].G, ": H = ", tile_data[tile].H)
return path[::-1] # Return reversed path
# Gets valid neighbors for current tile
neighbors = []
for dir in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
#get tile pos
neighbor = (current_tile.pos[0] + dir[0], current_tile.pos[1] + dir[1])
#check if tile on map and is valid
if 0 <= neighbor[0] < len(map[0]) and 0 <= neighbor[1] < len(map) and tile_data[neighbor].char == 'w' and tile_data[neighbor] not in checked_tiles:
# Set parent for neighbors
tile_data[neighbor].parent = current_tile
# Add neighbor to lists
unchecked_tiles.append(tile_data[neighbor])
neighbors.append(neighbor)
for neighbor in neighbors:
# Set G cost (14 for diagonal, 10 for othogonal move + parent.G cost)
if tile_data[neighbor].pos[0] == current_tile.pos[0] or tile_data[neighbor].pos[1] == current_tile.pos[1]:
tile_data[neighbor].G = 10 + current_tile.G
else:
tile_data[neighbor].G = 14 + current_tile.G
if tile_data[neighbor].G < current_tile.G:
current_tile.parent = tile_data[neighbor].parent
# Set H cost (a**2 + b**2 = c**2)
tile_data[neighbor].H = ((neighbor[0] - end[0]) ** 2) + ((neighbor[1] - end[1]) ** 2)
# Set F cost (G + H)
tile_data[neighbor].F = tile_data[neighbor].H + tile_data[neighbor].G
print('finished')
a_star((0,2),(4,2),map)
问题是我将重复的邻居移动到 G 成本不正确的“未检查”图块。无论如何，这是一个有效的 A* 算法:)
'''
map = [
['w','w','w','w','w'],
['w','w','x','w','w'],
['w','w','x','w','w'],
['w','w','x','w','w'],
['w','w','w','w','w'],
]
""" make copy of dict in the function! """
tile_data = {}
class Tile:
def __init__(self, pos, char):
self.pos = pos
self.char = char
self.parent = None
self.H = 0
self.G = 0
self.F = 0
#Gen Tiles
for y in range(len(map)):
for x in range(len(map[0])):
char = map[y][x]
tile = Tile((x,y), char)
tile_data[(x,y)] = tile
def a_star(start, end, map):
unchecked_tiles = []
checked_tiles = []
# set start position
tile_data[start].parent = None
tile_data[start].pos = start
tile_data[start].G = 0
unchecked_tiles.append(tile_data[start])
while unchecked_tiles:
#Get the tile with lowest F score
current_tile = min(unchecked_tiles, key=lambda tile: tile.F)
#move tile to checked list
checked_tiles.append(current_tile)
unchecked_tiles.remove(current_tile)
# If the End is found return the path of parent tiles
if current_tile.pos == end:
path = []
while current_tile.parent is not None:
path.append(current_tile.pos)
# Sets current tile to parent tile
current_tile = current_tile.parent
for tile in path:
print(tile, ": F = ", tile_data[tile].F, ": G = ", tile_data[tile].G, ": H = ", tile_data[tile].H)
return path[::-1] # Return reversed path
# Gets valid neighbors for current tile
neighbors = []
for dir in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
#get tile pos
neighbor = (current_tile.pos[0] + dir[0], current_tile.pos[1] + dir[1])
#check if tile on map and is valid
if 0 <= neighbor[0] < len(map[0]) and 0 <= neighbor[1] < len(map) and tile_data[neighbor].char == 'w' and tile_data[neighbor] not in checked_tiles:
if tile_data[neighbor] not in unchecked_tiles:
# Add neighbor to lists
unchecked_tiles.append(tile_data[neighbor])
neighbors.append(neighbor)
# Set parent for neighbors
tile_data[neighbor].parent = current_tile
for neighbor in neighbors:
# Set G cost (14 for diagonal, 10 for othogonal move + parent.G cost)
if tile_data[neighbor].pos[0] == current_tile.pos[0] or tile_data[neighbor].pos[1] == current_tile.pos[1]:
tile_data[neighbor].G = 10 + current_tile.G
else:
tile_data[neighbor].G = 14 + current_tile.G
if tile_data[neighbor].G < current_tile.G:
current_tile.parent = tile_data[neighbor].parent
if tile_data[neighbor].pos[0] == current_tile.pos[0] or tile_data[neighbor].pos[1] == current_tile.pos[1]:
current_tile.G = tile_data[neighbor].G + 10
else:
current_tile.G = tile_data[neighbor].G + 14
# Set H cost (a**2 + b**2 = c**2)
tile_data[neighbor].H = ((neighbor[0] - end[0]) ** 2) + ((neighbor[1] - end[1]) ** 2)
# Set F cost (G + H)
tile_data[neighbor].F = tile_data[neighbor].H + tile_data[neighbor].G
print('finished')
a_star((0,2),(4,2),map)
'''
def aStarSearch(problem: SearchProblem, heuristic=None):
"""Search the node that has the lowest combined cost and heuristic first."""
"*** YOUR CODE HERE ***"
class Node:
def __init__(self, state, parent=None):
self.state = state
self.parent = parent
self.g = 0
self.h = 0
self.f = 0
def __repr__(self):
return "Node(state=%s, g=%s, h=%s, f=%s)" % (self.state, self.g, self.h, self.f)
print("There is A* start",problem.getStartState())
start=problem.getStartState()
openSet=[]
closeSet=[]
openSet.append(start)
while (openSet):
current=openSet.pop(0)
print("current:",current)
if problem.isGoalState(current):
path = reconstruct_path(curren)
return path
closeSet.append(current)
print("In Close set we add current value",current)
successors=problem.getSuccessors(current)
print("There we add s",successors)
for successor in successors:
if successor in closeSet:
continue
successor_node=Node(successor,current)
successor_node.g= current.g + cost_to_move(current.state, successor)
successor_node.h = heuristic(successor, start)
successor_node.f = successor_node.g + successor_node.h
print("successor.g we have:",successor.g)
if successor_node in open_list and successor_node.f >= open_list[open_list.index(successor_node)].f:
continue
open_list.append(successor_node)
#In this i still face some issue like Error Like:
successor_node.g= current.g + cost_to_move(current.state, successor)
AttributeError: 'tuple' object has no attribute 'g'