我正在使用Python编写A *实现。我正在为我的优先级队列使用heapdict（https://pypi.org/project/HeapDict/）。问题是我的算法一直在将子节点放到打开列表中，而没有检查是否有更好的路径。换句话说，我似乎无法使elif条件调用。
我有一个State类，主要功能，输入了8个拼图块和一个a_star实现功能。
我已经尽我所能实现了一颗星级。之前在heapdict中访问f和g成本已经带来了问题，但是据我所知，这已经得到了照顾。我将展开的子项放到公开清单上，并尝试测试与公开表中相同子项的g成本相当的g成本，但无济于事。
8个拼图文件包含：
0 1 2 3 4 5 6 7 8
6 4 0 8 1 3 5 7 2
星星：
import puzzle
from collections import deque
from heapdict import heapdict
# Specify the search algorithm for solving the sliding tile puzzle
SEARCH_ALGORITHM = "a_star"
# File containing 8 puzzle instances
INSTANCE_FILE = "8_puzzle_instances"
def a_star(initial_state, goal):
expansion_count = generation_count = 0
open_list = heapdict()
open_list[initial_state] = initial_state.f
while len(open_list) > 0:
current = open_list.popitem()
if current[0] == goal:
print("Initial state is goal state")
return None, expansion_count, generation_count
current[0].closed = True
children = current[0].successors()
expansion_count += 1
for child in children:
generation_count += 1
if child not in open_list or child.closed == False:
# Insert child in open list.
# For loop keeps adding children to open_list.
open_list[child] = child.f
else:
open_list[child] = child.g
if child.g < open_list[child]:
# Reset priority of child.
open_list[child] = child.f
return None, expansion_count, generation_count
州立大学：
import math
import random
import sys
WIDTH = 3
SIZE = 9
HEURISTIC = "manhattan"
def settings_init(width=WIDTH, size=SIZE, heuristic=HEURISTIC):
global WIDTH, SIZE, HEURISTIC
WIDTH = width
SIZE = size
HEURISTIC = heuristic
class State:
def __init__(self, board, parent):
self.board = board
self.parent = parent
self.closed = None
self.goal_board = [x for x in range(0, SIZE)]
if parent is not None:
self.g = parent.g + 1
if HEURISTIC == 'manhattan':
self.h = 0
initial_board = self.board
goal_board = self.goal_board
for i in range(SIZE):
for j in range(i+1, SIZE):
self.h = abs(initial_board[i] - goal_board[i]) + abs(initial_board[j] - goal_board[j])
self.f = self.g + self.h
else:
self.g = self.h = 0
# Lower bound on optimal cost of path is equal
# to the heuristic on optimal path cost.
self.f = self.g + self.h
# Stores the hash key based on the list representing the puzzle
# state, not the object representing the state. This allows lookup in
# the hash table to find better paths
# Set equal to `None` to indicate this State hasn't been hashed yet.
self.hash = None
def __eq__(self, other):
# Compare two states for equality. This is the goal test
return self.board == other.board
def __hash__(self):
# Store the result of the hash function to speed up lookup
if self.hash is None:
self.hash = hash(tuple(self.board))
return self.hash
def __str__(self):
# String representation of a State as seen when printing the solution
# path
return " ".join(["_" if x == 0 else str(x) for x in self.board])
def successors(self):
# Compute the successor states generated by taking an action in the
# state
children = []
# For each action in the set of actions
for move in ("move_up", "move_down", "move_left", "move_right"):
try:
children.append(getattr(self, move)())
# If the action can't be taken, e.g. moving a blank off of the
# board, then skip that action and don't append it to the list of
# successors
except ValueError:
continue
return children
# Generate new state from current state
def move_right(state):
tmp = state.board[:]
i = tmp.index(0)
if i % WIDTH != WIDTH - 1:
tmp[i], tmp[i + 1] = tmp[i + 1], tmp[i]
return State(tmp, state)
raise ValueError('invalid move right of state', tmp)
def move_left(state):
tmp = state.board[:]
i = tmp.index(0)
if i % WIDTH != 0:
tmp[i], tmp[i - 1] = tmp[i - 1], tmp[i]
return State(tmp, state)
raise ValueError('invalid move left of state', tmp)
def move_up(state):
tmp = state.board[:]
i = tmp.index(0)
if i > WIDTH - 1:
tmp[i], tmp[i - WIDTH] = tmp[i - WIDTH], tmp[i]
return State(tmp, state)
raise ValueError('invalid move up of state', tmp)
def move_down(state):
tmp = state.board[:]
i = tmp.index(0)
if i < SIZE - WIDTH:
tmp[i], tmp[i + WIDTH] = tmp[i + WIDTH], tmp[i]
return State(tmp, state)
raise ValueError('invalid move down of state', tmp)
主要功能：
def main():
puzzle.settings_init()
# Check to see if we can open the instances file.
try:
instances_fh = open(INSTANCE_FILE)
except FileNotFoundError:
raise(INSTANCE_FILE, "not found.")
sys.exit(-1)
# Define puzzle goal state
gboard = [x for x in range(0, puzzle.SIZE)]
goal = puzzle.State(gboard, None)
# Run search.
# Load a puzzle state from the instance file.
initial_state = load_instance_from_file(instances_fh)
# Indices of counts returned by search algorithms
EXPANDED = 0
GENERATED = 1
# While there are instances left to solve:
while initial_state:
solution = None
try:
print("Solving", initial_state.board)
if 'a_star' == SEARCH_ALGORITHM:
solution, *counts = a_star(initial_state, goal)
# Display solution
if solution is None:
print ("Solution is not found")
else:
# Build path from initial state to goal state
ptr = solution
path = []
while ptr is not None:
path.append(str(ptr))
ptr = ptr.parent
path.reverse()
print(
"Goal state reached in {len(path) - 1} moves by",
f"{SEARCH_ALGORITHM} after {counts[EXPANDED]} node",
f"expansions and {counts[GENERATED]} node generations.",
)
print(*path, sep='\n')
print()
except ValueError:
sys.exit(1)
initial_state = load_instance_from_file(instances_fh)
return
if __name__ == "__main__":
main()
我希望该算法能在比BFS算法更短的时间内找到无序8个拼图的解决方案，但是，我的实现从未找到解决方案。我没有得到任何错误，一个star函数只是完成了将子级放到打开列表中，直到返回None，generation_count，expansion_count行。
[我怀疑当我需要访问一条最佳路径时，我实际上也没有指向儿童父母。 State类应该是每个节点的生成父指针，但是在我的实现中，优先级队列似乎无权访问f以外的任何东西。
您为什么问我们？你有谷歌。点击->Some Images.Random Image