-1

Я пытаюсь построить решение проблемы 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)]""" 
+0

Это не удается, потому что вы не определили 'bfs',' up', 'down',' left', 'right' и, возможно, некоторые другие вещи. –

+0

жаль, что я пропустил часть своего кода, сейчас обновится. @ paul-hankin – johnaphun

+0

Как вы тестировали 'up'? Я верю, что «вверх» и «вниз» неверны. –

ответ

0

Это условие в up никогда не верно: if n**2 < i <= (n**2 - n). И это условие в down отключено одним: if i > n.

Является ли остальная часть вашего кода правильной или нет, неясно, но сначала нужно сначала отладить основы вашего представления доски и кода манипуляции.

В вашем пространстве-движущемся кода, лично я бы превратить ваш индекс в x и y координат:

x, y = i % n, i // n 

Затем вы можете проверить более естественно: x>0 для левой стороны, x<n-1 для права, y<n-1 для и y>0 для пуха.

0

Если вы обрабатываете сосед (дети) узел (состояния) путем перемещения space в UP, DOWN, LEFT, RIGHT порядке, решения в 8-puzzle с bfs, начиная с начальным состоянием 1,2,5,3,4,0,6,7,8 в будут иметь следующий вид (вы можете проверить, где это отличаясь с раствором):

path_to_goal: ['Up', 'Left', 'Left'] 
cost_of_path: 3 

enter image description here

Вы можете обратиться к этому https://sandipanweb.wordpress.com/2017/03/16/using-uninformed-informed-search-algorithms-to-solve-8-puzzle-n-puzzle/?frame-nonce=9e97a821bc для получения более подробной информации.