#python #algorithm #typeerror #a-star #puzzle
Вопрос:
Это код на python, который использует алгоритм* для поиска решения для 8 задач-головоломок, я получил несколько сообщений об ошибках, как я могу это исправить?(Сообщение об ошибке находится под кодом)
Существует несколько концепций объектно-ориентированного программирования для
Problemsкласса,Nodeкласса, которые реализованы для выражения поиска решения проблемы, которое вам необходимо понять, чтобы завершить программу на Python. Приоритетная очередь состоит в том, чтобы отсортировать узлы, подлежащие исследованию, в соответствии с их оценкой функции f-оценки, и вернуть минимальный в качестве первого узла, подлежащего следующему поиску.Существует также
memorizeфункция для запоминания эвристического значения состояния в виде таблицы поиска, чтобы вам не нужно было вычислять избыточное вычисление значения эвристической оценки, поэтому вы можете игнорировать его на данном этапе, если вы не понимаете.Компоненты, которые вам нужно реализовать,- это сделать абстрактную часть программы реализуемой для 8-головоломки с последующими методами, прикрепленными к классу задач, который состоит из начального состояния и состояния цели. Убедитесь, что программа может работать правильно, чтобы сгенерировать последовательность решений, которая перемещает пустую плитку, чтобы 8-головоломка могла перемещаться «Вверх», «Вниз», «Влево», «Вправо» из начального состояния в целевое состояние.
import math
infinity = math.inf
from itertools import chain
import numpy as np
import bisect
class memoize:
def __init__(self, f, memo={}):
self.f = f
self.memo = {}
def __call__(self, *args):
if not str(args) in self.memo:
self.memo[str(args)] = self.f(*args)
return self.memo[str(args)]
def coordinate(state):
index_state = {}
index = [[0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]]
for i in range(len(state)):
index_state[state[i]] = index[i]
return index_state
def getInvCount(arr):
inv_count = 0
empty_value = -1
for i in range(0, 9):
for j in range(i 1, 9):
if arr[j] != empty_value and arr[i] != empty_value and arr[i] > arr[j]:
inv_count = 1
return inv_count
def isSolvable(puzzle) :
inv_count = getInvCount([j for sub in puzzle for j in sub])
return (inv_count % 2 == 0)
def linear(state):
return sum([1 if state[i] != goal[i] else 0 for i in range(9)])
@memoize
def manhattan(state):
index_goal = coordinate(goal)
index_state = coordinate(state)
mhd = 0
for i in range(9):
for j in range(2):
mhd = abs(index_goal[i][j] - index_state[i][j]) mhd
return mhd
@memoize
def sqrt_manhattan(state):
index_goal = coordinate(goal)
index_state = coordinate(state)
mhd = 0
for i in range(9):
for j in range(2):
mhd = (index_goal[i][j] - index_state[i][j])**2 mhd
return math.sqrt(mhd)
@memoize
def max_heuristic(state):
score1 = manhattan(state)
score2 = linear(state)
return max(score1, score2)
class PriorityQueueElmt:
def __init__(self,val,e):
self.val = val
self.e = e
def __lt__(self,other):
return self.val < other.val
def value(self):
return self.val
def elem(self):
return self.e
class Queue:
def __init__(self):
pass
def extend(self, items):
for item in items: self.append(item)
class PriorityQueue(Queue):
def __init__(self, order=min, f=None):
self.A=[]
self.order=order
self.f=f
def append(self, item):
queueElmt = PriorityQueueElmt(self.f(item),item)
bisect.insort(self.A, queueElmt)
def __len__(self):
return len(self.A)
def pop(self):
if self.order == min:
return self.A.pop(0).elem()
else:
return self.A.pop().elem()
# Heuristics for 8 Puzzle Problem
class Problem:
def __init__(self, initial, goal=None):
self.initial = initial; self.goal = goal
def successor(self, state):
reachable = []
def get_key(val):
for key, value in index_state.items():
if val == value:
return key
return -1
def candidate(state, Position):
state = state.copy()
zero_index = state.index(0)
swap_index = state.index(get_key(Position))
state[zero_index], state[swap_index] = state[swap_index], state[zero_index]
return state
index_state = coordinate(state)
zero_position = index_state[0]
move_pair = {"left":[zero_position[0], zero_position[1] - 1],
"right":[zero_position[0], zero_position[1] 1],
"up":[zero_position[0] - 1, zero_position[1]],
"down":[zero_position[0] 1, zero_position[1]]
}
for action, position in move_pair.items():
#print(action, position)
if get_key(position) != -1:
reachable.append((action, candidate(state, position)))
#print(reachable)
return reachable
def goal_test(self, state):
return state == self.goal
def path_cost(self, c, state1, action, state2):
return c 1
def value(self):
abstract
class Node:
def __init__(self, state, parent=None, action=None, path_cost=0, depth =0):
self.parent = parent
if parent:
self.depth = parent.depth 1
else:
self.depth = 0
self.path_cost = path_cost
self.state = state
if action:
self.action = action
else: self.action = "init"
def __repr__(self):
return "Node state:n " str(np.array(self.state).reshape(3,3)) "n -> action: " self.action "n -> depth: " str(self.depth)
def path(self):
x, result = self, [self]
while x.parent:
result.append(x.parent)
x = x.parent
return result
def expand(self, problem):
for (act,n) in problem.successor(self.state):
if n not in [node.state for node in self.path()]:
yield Node(n, self, act,
problem.path_cost(self.path_cost, self.state, act, n))
def graph_search(problem, fringe):
closed = {}
fringe.append(Node(problem.initial,depth=0))
while fringe:
node = fringe.pop()
if problem.goal_test(node.state):
return node
if str(node.state) not in closed:
closed[str(node.state)] = True
fringe.extend(node.expand(problem))
return None
def best_first_graph_search(problem, f):
return graph_search(problem, PriorityQueue(min, f))
def astar_search(problem, h = None):
h = h or problem.h
def f(n):
return max(getattr(n, 'f', -infinity), n.path_cost h(n.state))
return best_first_graph_search(problem, f)
def print_path(path, method):
print("*" * 30)
print("nPath: (%s distance)" % method)
for i in range(len(path)-1, -1, -1):
print("-" * 15)
print(path[i])
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
# Solving the puzzle
puzzle = [7, 2, 4, 5, 0, 6, 8, 3, 1]
if(isSolvable(np.array(puzzle).reshape(3,3))): # even true
# checks whether the initialized configuration is solvable or not
print("Solvable!")
problem = Problem(puzzle,goal)
path = astar_search(problem, manhattan).path()
print_path(path, "manhattan")
path = astar_search(problem, linear).path()
print_path(path, "linear")
path = astar_search(problem, sqrt_manhattan).path()
print_path(path, "sqrt_manhattan")
path = astar_search(problem, max_heuristic).path()
print_path(path, "max_heuristic")
else :
print("Not Solvable!") # non-even false
TypeError Traceback (most recent call last)
<ipython-input-124-2a60ddc8c009> in <module>
9 problem = Problem(puzzle,goal)
10
---> 11 path = astar_search(problem, manhattan).path()
12 print_path(path, "manhattan")
13
<ipython-input-123-caa97275712e> in astar_search(problem, h)
18 def f(n):
19 return max(getattr(n, 'f', -infinity), n.path_cost h(n.state))
---> 20 return best_first_graph_search(problem, f)
21
22 def print_path(path, method):
<ipython-input-123-caa97275712e> in best_first_graph_search(problem, f)
12
13 def best_first_graph_search(problem, f):
---> 14 return graph_search(problem, PriorityQueue(min, f))
15
16 def astar_search(problem, h = None):
<ipython-input-123-caa97275712e> in graph_search(problem, fringe)
8 if str(node.state) not in closed:
9 closed[str(node.state)] = True
---> 10 fringe.extend(node.expand(problem))
11 return None
12
<ipython-input-121-e5a968bd54f0> in extend(self, items)
18
19 def extend(self, items):
---> 20 for item in items: self.append(item)
21
22 class PriorityQueue(Queue):
<ipython-input-122-db21613469b9> in expand(self, problem)
69
70 def expand(self, problem):
---> 71 for (act,n) in problem.successor(self.state):
72 if n not in [node.state for node in self.path()]:
73 yield Node(n, self, act,
TypeError: cannot unpack non-iterable int object
Ответ №1:
У меня есть несколько сообщений об ошибках, как я могу это исправить?
Существует одно сообщение об ошибке, фрагменты кодов, которые вы получаете в сообщении об ошибке, являются трассировкой стека, что может помочь вам узнать, как выполнение произошло в конечной точке, где произошла ошибка. В данном случае это не так важно. Суть ошибки заключается в следующем:
for (act,n) in problem.successor(self.state)Ошибка типа: не удается распаковать неитерабельный объект int
Таким образом, это означает, что successor метод вернул int вместо списка.
Глядя на код successor , я замечаю , что он намеревается вернуть вызванный список reachable , но прямо return в середине кода есть оператор, оставляющий большую часть этого кода неисполненной (так называемый «мертвый код»).:
return state
Это утверждение не имеет смысла там, где оно расположено. Похоже, это проблема с отступом: это return относится к функции, расположенной прямо над ней, вот так:
def candidate(state, Position):
state = state.copy()
zero_index = state.index(0)
swap_index = state.index(get_key(Position))
state[zero_index], state[swap_index] = state[swap_index], state[zero_index]
return state # <-- indentation!