Я пытаюсь построить решение проблемы N-Puzzle, используя поиск по ширине в Python.N Puzzle в Python
Мое решение умело находить ответ, если все номера штрихов равны нулю. например
initial_state = [1,2,3,4,0,5,6,7,8]
или
initial_state = [1,2,3,4,5,6,7,0,8]
, но не с
initial_state = [1,2,5,3,4,0,6,7,8]
Радует найти ниже моей реализации. Если кто-то может указать на недостаток в моей логике, это было бы очень ценно.
Заранее благодарен!
def right(state):
items = list(state)
i = items.index(0)
n = int(math.sqrt(len(items)))
if (i+1) % n != 0:
del items[i]
items.insert(i+1, 0)
return tuple(items)
else:
pass
def left(state):
items = list(state)
i = items.index(0)
n = int(math.sqrt(len(items)))
if i % n != 0:
del items[i]
items.insert(i-1, 0)
return tuple(items)
else:
pass
def up(state):
items = list(state)
i = items.index(0)
n = int(math.sqrt(len(items)))
if n**2 < i <= (n**2 - n):
del items[i]
items.insert(i+n, 0)
return tuple(items)
else:
pass
def down(state):
items = list(state)
i = items.index(0)
n = int(math.sqrt(len(items)))
if i > n:
del items[i]
items.insert(i-n, 0)
return tuple(items)
else:
pass
class Problem(object):
def __init__(self, initial, goal=None):
self.initial = initial
self.goal = goal
self.n = len(initial)
self.size = int(math.sqrt(self.n))
self.blank = self.initial.index(0)
self.top_row = [i for i in range(self.n) if i < self.size]
self.bottom_row = [i for i in range(self.n) if self.n - (self.size) <= i < self.n]
self.left_column = [i for i in range(self.n) if i % self.size == 0]
self.right_column = [i for i in range(self.n) if (i + 1) % self.size == 0]
def actions(self):
result_list = ["UP","DOWN","LEFT","RIGHT"]
return result_list
def result(self, state, action):
if action == "RIGHT":
return right(state)
if action == "LEFT":
return left(state)
if action == "UP":
return up(state)
if action == "DOWN":
return down(state)
def goal_test(self, state):
return state == self.goal
def path_cost(self, c):
return c + 1
class Node:
def __init__(self, state, parent=None, action=None, path_cost=0):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
self.depth = 0
if parent:
self.depth = parent.depth + 1
def __repr__(self):
return "<Node %s>" % (self.state,)
def __lt__(self, node):
return self.state < node.state
def expand(self, problem):
return [self.child_node(problem, action)
for action in problem.actions() if self.child_node(problem,action) is not None]
def child_node(self, problem, action):
next = problem.result(self.state, action)
if next:
return Node(next, self, action,
problem.path_cost(self.path_cost))
else:
pass
def solution(self):
return [node.action for node in self.path()[1:]]
def path(self):
node, path_back = self, []
while node:
path_back.append(node)
node = node.parent
return list(reversed(path_back))
def __eq__(self, other):
return isinstance(other, Node) and self.state == other.state
def __hash__(self):
return hash(self.state)
def bfs(problem):
node = Node(problem.initial)
frontier = deque([node])
explored = set()
while frontier:
node = frontier.pop()
explored.add(node.state)
if problem.goal_test(node.state):
return node
for child in node.expand(problem):
if child.state not in explored and child not in frontier:
frontier.append(child)
return [child for child in explored]
p = Problem((1,2,5,3,4,0,6,7,8), (0,1,2,3,4,5,6,7,8))
bfs(p)
#returns
"""[(1, 2, 5, 3, 4, 0, 6, 7, 8),
(1, 2, 0, 5, 3, 4, 6, 7, 8),
(0, 1, 2, 5, 3, 4, 6, 7, 8),
(1, 2, 5, 3, 0, 4, 6, 7, 8),
(1, 2, 5, 0, 3, 4, 6, 7, 8),
(1, 0, 2, 5, 3, 4, 6, 7, 8)]"""
Это не удается, потому что вы не определили 'bfs',' up', 'down',' left', 'right' и, возможно, некоторые другие вещи. –
жаль, что я пропустил часть своего кода, сейчас обновится. @ paul-hankin – johnaphun
Как вы тестировали 'up'? Я верю, что «вверх» и «вниз» неверны. –