8重複節點的瓷磚解決方案 - Python

Question

我試圖解決使用像BFS搜索，DFS，貪婪和A *使用曼哈頓距離作爲我的啓發式解決方案的技術八謎。

問題是，雖然我可以解決一些很多問題，但問題出在一些謎題，可能會發生的問題是，我在展開父節點時遇到的子節點可能已經存在於較舊的節點中。

我不知道我是否能夠很好地解釋我自己，但我的主要問題是我試圖查看我創建的新節點是否已經不在舊節點上。

有了這個問題，我通常會深入9，然後我的程序不會提前或給出解決方案。

我的一個ideias的是使用代碼：

if node in prev: 
    continue 
prev.append(node) 

但我想我走錯了路。

我在python上這樣做，這是我的代碼，以防有人可以幫助我。

#!/usr/bin/python 

import sys 
import copy 


class Board: 
    def __init__(self, matrix, whitepos=None): 
     self.matrix = matrix 
     self.whitepos = whitepos 
     if not whitepos: 
      for y in xrange(3): 
       for x in xrange(3): 
        if board[y][x] == 0: 
         self.whitepos = (x, y) 


def is_final_state(board): 
    final = [[1, 2, 3], [8, 0, 4], [7, 6, 5]] 
    for y in xrange(3): 
     for x in xrange(3): 
      if board.matrix[y][x] != final[y][x]: 
       return False 
    return True 


def get_whitepos(board): 
    return board.whitepos 


def move(board, x, y, dx, dy): 
    b = copy.deepcopy(board.matrix) 
    b[y][x] = b[y + dy][x + dx] 
    b[y + dy][x + dx] = 0 
    return Board(b, (x + dx, y + dy)) 


def manhattan_heur(board): 
    finalpos = [(1, 1), (0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), 
       (0, 1)] 
    cost = 0 
    for y in xrange(3): 
     for x in xrange(3): 
      t = board.matrix[y][x] 
      xf, yf = finalpos[t] 
      cost += abs(xf - x) + abs(yf - y) 
    return cost 


def wrongplace_heur(board): 
    finalpos = [(1, 1), (0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), 
       (0, 1)] 
    cost = 0 
    for y in xrange(3): 
     for x in xrange(3): 
      t = board.matrix[y][x] 
      if finalpos[t] != (x, y): 
       cost += 1 
    return cost 


def heuristic(board): 
    return manhattan_heur(board) 


class Node: 
    def __init__(self, board, parent): 
     self.state = board 
     self.parent = parent 
     if not parent: 
      self.g = 0 
     else: 
      self.g = parent.g + 1 
     self.h = heuristic(board) 

    def test_goal(self): 
     return is_final_state(self.state) 

    def expand(self): 
     children = [] 
     b = self.state 
     x, y = get_whitepos(b) 
     if x > 0: 
      children.append(Node(move(b, x, y, -1, 0), self)) 
     if x < 2: 
      children.append(Node(move(b, x, y, +1, 0), self)) 
     if y > 0: 
      children.append(Node(move(b, x, y, 0, -1), self)) 
     if y < 2: 
      children.append(Node(move(b, x, y, 0, +1), self)) 
     return children 


class Solution: 
    def __init__(self, node, mem_needed, steps): 
     self.node = node 
     self.mem_needed = mem_needed 
     self.iterations = steps 

    def inc(self, other): 
     self.node = other.node 
     self.mem_needed = max(self.mem_needed, other.mem_needed) 
     self.iterations += other.iterations 


def search(board, queue_fn, queue_arg=None): 
    max_nodes = 1 
    steps = 0 
    nodes = [Node(Board(board), None)] 
    prev = [] 
    depth = 0 
    while nodes: 
     node = nodes.pop(0) 

     if node.g > depth: 
      depth = node.g 
      print depth 

     if node in prev: 
      continue 
     prev.append(node) 

     if node.test_goal(): 
      return Solution(node, max_nodes, steps) 
     new_nodes = node.expand() 
     nodes = queue_fn(nodes, new_nodes, queue_arg) 

     max_nodes = max(max_nodes, len(nodes)) 
     steps += 1 
    return Solution(None, max_nodes, steps) 


def fifo_queue(nodes, new_nodes, _): 
    nodes.extend(new_nodes) 
    return nodes 


def bl_search(board): 
    return search(board, fifo_queue) 


def lifo_queue(nodes, new_nodes, _): 
    new_nodes.extend(nodes) 
    return new_nodes 


def dfs_search(board): 
    return search(board, lifo_queue) 


def bpl_queue(nodes, new_nodes, max_depth): 
    def f(n): 
     return n.g <= max_depth 

    new_nodes = filter(f, new_nodes) 
    new_nodes.extend(nodes) 
    return new_nodes 


def bpi_search(board): 
    solution = Solution(None, 0, 0) 
    for max_depth in xrange(0, sys.maxint): 
     sol = search(board, bpl_queue, max_depth) 
     solution.inc(sol) 
     if solution.node: 
      return solution 


def sort_queue(nodes, new_nodes, cmp): 
    nodes.extend(new_nodes) 
    nodes.sort(cmp) 
    return nodes 


def guloso2_search(board): 
    def cmp(n1, n2): 
     return n1.h - n2.h 

    return search(board, sort_queue, cmp) 


def astar_search(board): 
    def cmp(n1, n2): 
     return (n1.g + n1.h) - (n2.g + n2.h) 

    return search(board, sort_queue, cmp) 


def print_solution(search, sol): 
    print 
    print "*", search 
    node = sol.node 
    if node: 
     print "moves:", node.g 
     while node: 
      print "\t", node.state.matrix 
      node = node.parent 
    else: 
     print "no solution found" 
    print "nodes needed:", sol.mem_needed 
    print "iterations: ", sol.iterations 


board = [[6, 5, 7], [2, 0, 1], [8, 4, 3]] 

print_solution("bl", bl_search(board)) 
print_solution("dfs", dfs_search(board)) 
print_solution("bpi", bpi_search(board)) 
print_solution("guloso2", guloso2_search(board)) 
print_solution("astar", astar_search(board)) 

Answer 1

貌似你要去了解它的正確方法，但你需要定義在Node類的__eq__和__ne__方法;否則node in prev將始終返回False，因爲Python不知道如何將node與列表中的項目進行比較。查看Python data model documentation瞭解更多關於如何比較用戶定義類型的工作。

我抓住你的代碼，並添加了幾個（非常天真）的方法來做平等檢查，它不再顯示掛起。還值得注意的是，你的課程應該從基地object繼承（見下文）。這是我（在上下文中）所做的更改：

class Board(object): 
    def __init__(self, matrix, whitepos=None): 
     self.matrix = matrix 
     self.whitepos = whitepos 
     if not whitepos: 
      for y in xrange(3): 
       for x in xrange(3): 
        if board[y][x] == 0: 
         self.whitepos = (x, y) 
    def __eq__(self, o): 
     # Note that comparing whitepos is not strictly necessary; but I left 
     # it in as a safety measure in case the board state gets corrupted. 
     # If speed becomes an issue, take it out. 
     return (self.matrix, self.whitepos) == (o.matrix, o.whitepos) 

class Node(object): 
    def __init__(self, board, parent): 
     self.state = board 
     self.parent = parent 
     if not parent: 
      self.g = 0 
     else: 
      self.g = parent.g + 1 
     self.h = heuristic(board) 

    def test_goal(self): 
     return is_final_state(self.state) 

    def expand(self): 
     children = [] 
     b = self.state 
     x, y = get_whitepos(b) 
     if x > 0: 
      children.append(Node(move(b, x, y, -1, 0), self)) 
     if x < 2: 
      children.append(Node(move(b, x, y, +1, 0), self)) 
     if y > 0: 
      children.append(Node(move(b, x, y, 0, -1), self)) 
     if y < 2: 
      children.append(Node(move(b, x, y, 0, +1), self)) 
     return children 

    def __eq__(self, o): 
     # Note that you don't have to compare parents, since your goal 
     # is to eliminate ANY nodes with the same position. 
     return self.state == o.state 

class Solution(object): 
    def __init__(self, node, mem_needed, steps): 
     self.node = node 
     self.mem_needed = mem_needed 
     self.iterations = steps 

    def inc(self, other): 
     self.node = other.node 
     self.mem_needed = max(self.mem_needed, other.mem_needed) 
     self.iterations += other.iterations 

#... 

print_solution("bl", bl_search(board)) 
# I commented out all but the first search to avoid cluttering up the output. 

有了這些變化，代碼確實產生一個解決方案（我會讓你來驗證它是正確的，但這裏是我的輸出）。

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 

* bl 
moves: 20 
    [[1, 2, 3], [8, 0, 4], [7, 6, 5]] 
    [[1, 2, 3], [8, 6, 4], [7, 0, 5]] 
    [[1, 2, 3], [8, 6, 4], [0, 7, 5]] 
    [[1, 2, 3], [0, 6, 4], [8, 7, 5]] 
    [[1, 2, 3], [6, 0, 4], [8, 7, 5]] 
    [[1, 0, 3], [6, 2, 4], [8, 7, 5]] 
    [[0, 1, 3], [6, 2, 4], [8, 7, 5]] 
    [[6, 1, 3], [0, 2, 4], [8, 7, 5]] 
    [[6, 1, 3], [2, 0, 4], [8, 7, 5]] 
    [[6, 1, 3], [2, 7, 4], [8, 0, 5]] 
    [[6, 1, 3], [2, 7, 4], [8, 5, 0]] 
    [[6, 1, 3], [2, 7, 0], [8, 5, 4]] 
    [[6, 1, 0], [2, 7, 3], [8, 5, 4]] 
    [[6, 0, 1], [2, 7, 3], [8, 5, 4]] 
    [[6, 7, 1], [2, 0, 3], [8, 5, 4]] 
    [[6, 7, 1], [2, 5, 3], [8, 0, 4]] 
    [[6, 7, 1], [2, 5, 3], [8, 4, 0]] 
    [[6, 7, 1], [2, 5, 0], [8, 4, 3]] 
    [[6, 7, 0], [2, 5, 1], [8, 4, 3]] 
    [[6, 0, 7], [2, 5, 1], [8, 4, 3]] 
    [[6, 5, 7], [2, 0, 1], [8, 4, 3]] 
nodes needed: 44282 
iterations: 59930 

希望這有助於！