如何在Python中实现15难题的IDA *算法? [英] How can I implement IDA* algorithm in Python for 15-Puzzle problem?

问题描述

我正在尝试使用IDA *算法和Manhattan启发式算法来解决15-Puzzle问题.我已经在此Wikipedia页面(链接)中的伪代码中实现了该算法.

I'm trying to solve the 15-Puzzle problem using IDA* algorithm and Manhattan heuristic. I already implemented the algorithm from the pseudocode in this Wikipedia page (link).

到目前为止，这是我的代码:

Here's my code so far :

def IDA(initial_state, goal_state):
    initial_node = Node(initial_state)
    goal_node = Node(goal_state)
    
    threshold = manhattan_heuristic(initial_state, goal_state)
    path = [initial_node]

    while 1:
        tmp = search(path, goal_state, 0, threshold)
        if tmp == True:
            return path, threshold
        elif tmp == float('inf'):
            return False
        else:
            threshold = tmp


def search(path, goal_state, g, threshold):
    node = path[-1]
    f = g + manhattan_heuristic(node.state, goal_state)

    if f > threshold:
        return f

    if np.array_equal(node.state, goal_state):
        return True

    minimum = float('inf')  
    for n in node.nextnodes():
        if n not in path:
            path.append(n)
            tmp = search(path, goal_state, g + 1, threshold)
            if tmp == True:
                return True
            if tmp < minimum:
                minimum = tmp
            path.pop()

    return minimum


def manhattan_heuristic(state1, state2):
    size = range(1, len(state1) ** 2)
    distances = [count_distance(num, state1, state2) for num in size]

    return sum(distances)


def count_distance(number, state1, state2):
    position1 = np.where(state1 == number)
    position2 = np.where(state2 == number)

    return manhattan_distance(position1, position2)


def manhattan_distance(a, b):
    return abs(b[0] - a[0]) + abs(b[1] - a[1])


class Node():
    def __init__(self, state):
        self.state = state

    def nextnodes(self):
        zero = np.where(self.state == 0)
        
        y,x = zero
        y = int(y)
        x = int(x)
        
        up = (y - 1, x) 
        down = (y + 1, x)
        right = (y, x + 1)
        left = (y, x - 1)

        arr = []
        for direction in (up, down, right, left):
            if len(self.state) - 1 >= direction[0] >= 0 and len(self.state) - 1 >= direction[1] >= 0:
                tmp = np.copy(self.state)
                tmp[direction[0], direction[1]], tmp[zero] = tmp[zero], tmp[direction[0], direction[1]]
                arr.append(Node(tmp))

        return arr

我正在用3x3拼图测试此代码，这是无限循环！由于递归，我在测试代码时遇到了一些麻烦...

I'm testing this code with a 3x3 Puzzle and here's the infinite loop! Due to the recursion I have some trouble testing my code...

我认为错误可能在这里: tmp = search(路径，goal_state，g + 1，阈值)(在 search 函数中).我在g成本值中仅添加了一个.不过应该是正确的，因为我只能将磁贴移动1个位置.

I think the error might be here : tmp = search(path, goal_state, g + 1, threshold) (in the search function). I'm adding only one to the g cost value. It should be correct though, because I can only move a tile 1 place away.

以下是调用 IDA()函数的方法:

Here's how to call the IDA() function:

initial_state = np.array([8 7 3],[4 1 2],[0 5 6])
goal_state = np.array([1 2 3],[8 0 4],[7 6 5])
IDA(initial_state, goal_state)

有人可以帮我吗?

推荐答案

IDA * 实现中存在几个问题.首先，变量 path 的目的是什么?我在您的代码中发现了 path 的两个目的:

There are couple of issues in your IDA* implementation. First, what is the purpose of the variable path? I found two purposes of path in your code:

1. 用作标记/地图，以保留已被访问的板状态.
2. 用作堆栈来管理递归状态.

1. Use as a flag/map to keep the board-states that is already been visited.
2. Use as a stack to manage recursion states.

但是，不可能通过使用单个数据结构来同时完成这两个操作.因此，您的代码需要进行的第一次修改:

But, it is not possible to do both of them by using a single data structure. So, the first modification that your code requires:

• Fix-1:将当前 node 作为参数传递给 search 方法.
• 修正2: flag 应该是可以有效执行 not in 查询的数据结构.

• Fix-1: Pass current node as a parameter to the search method.
• Fix-2: flag should be a data structure that can perform a not in query efficiently.

现在，修复-1 很简单，因为我们可以将当前访问节点作为搜索方法中的参数来传递.对于 fix-2 ，我们需要将 flag 的类型从 list 更改为 set ，如下:

Now, fix-1 is easy as we can just pass the current visiting node as the parameter in the search method. For fix-2, we need to change the type of flag from list to set as:

• list 中 x in s 的平均大小写复杂度为:O(n)
• set 的
  • x在s 中的平均大小写复杂度为:O(1)
  • x in s 的最坏情况复杂度是:O(n)
  • list's average case complexity for x in s is: O(n)
  • set's
    • Average case complexity for x in s is: O(1)
    • Worst case complexity for x in s is: O(n)

    您可以查看有关用于测试成员资格的性能:列表与集合以获取更多详细信息.

    You can check more details about performance for testing memberships: list vs sets for more details.

    现在，要将 Node 信息保存在 set 中，您需要在以下代码中实现 __ eq __ 和 __ hash __ 您的 Node 类.在下面，我附上了修改后的代码.

    Now, to keep the Node information into a set, you need to implement __eq__ and __hash__ in your Node class. In the following, I have attached the modified code.

    import timeit
    import numpy as np
    
    def IDA(initial_state, goal_state):
        initial_node = Node(initial_state)
        goal_node = Node(goal_state)
        
        threshold = manhattan_heuristic(initial_state, goal_state)
        
        #print("heuristic threshold: {}".format(threshold))
        
        loop_counter = 0
    
        while 1:
            path = set([initial_node])
            
            tmp = search(initial_node, goal_state, 0, threshold, path)
            
            #print("tmp: {}".format(tmp))
            if tmp == True:
                return True, threshold
            elif tmp == float('inf'):
                return False, float('inf')
            else:
                threshold = tmp
    
    
    def search(node, goal_state, g, threshold, path):
        #print("node-state: {}".format(node.state))
        f = g + manhattan_heuristic(node.state, goal_state)
    
        if f > threshold:
            return f
    
        if np.array_equal(node.state, goal_state):
            return True
    
        minimum = float('inf')  
        for n in node.nextnodes():
            if n not in path:
                path.add(n)
                tmp = search(n, goal_state, g + 1, threshold, path)
                if tmp == True:
                    return True
                if tmp < minimum:
                    minimum = tmp
    
        return minimum
    
    
    def manhattan_heuristic(state1, state2):
        size = range(1, len(state1) ** 2)
        distances = [count_distance(num, state1, state2) for num in size]
    
        return sum(distances)
    
    
    def count_distance(number, state1, state2):
        position1 = np.where(state1 == number)
        position2 = np.where(state2 == number)
    
        return manhattan_distance(position1, position2)
    
    
    def manhattan_distance(a, b):
        return abs(b[0] - a[0]) + abs(b[1] - a[1])
    
    
    class Node():
        def __init__(self, state):
            self.state = state
        
        def __repr__(self):
            return np.array_str(self.state.flatten())
    
        def __hash__(self):
            return hash(self.__repr__())
            
        def __eq__(self, other):
            return self.__hash__() == other.__hash__()
    
        def nextnodes(self):
            zero = np.where(self.state == 0)
            
            y,x = zero
            y = int(y)
            x = int(x)
            
            up = (y - 1, x) 
            down = (y + 1, x)
            right = (y, x + 1)
            left = (y, x - 1)
    
            arr = []
            for direction in (up, down, right, left):
                if len(self.state) - 1 >= direction[0] >= 0 and len(self.state) - 1 >= direction[1] >= 0:
                    tmp = np.copy(self.state)
                    tmp[direction[0], direction[1]], tmp[zero] = tmp[zero], tmp[direction[0], direction[1]]
                    arr.append(Node(tmp))
    
            return arr
    
    
    initial_state = np.array([[8, 7, 3],[4, 1, 2],[0, 5, 6]])
    goal_state = np.array([[1, 2, 3],[8, 0, 4],[7, 6, 5]])
    
    start = timeit.default_timer()
    is_found, th = IDA(initial_state, goal_state)
    stop = timeit.default_timer()
    
    print('Time: {} seconds'.format(stop - start))
    
    if is_found is True:
        print("Solution found with heuristic-upperbound: {}".format(th))
    else:
        print("Solution not found!")
    

    节点:，请仔细检查您的 Node.nextnodes()和 manhattan_heuristic()方法，因为我在这些领域没有特别注意.您可以在其他算法实现中查看 GitHub存储库(即 A * ， IDS ， DLS )来解决此问题.

    Node: Please double check your Node.nextnodes() and manhattan_heuristic() methods as I did not pay much attention in those areas. You can check this GitHub repository for other algorithmic implementations (i.e., A*, IDS, DLS) to solve this problem.

    1. Python Wiki:时间复杂度
    2. TechnoBeans:测试成员资格的性能:列表vs元组vs集
    3. GitHub:难题求解器(通过使用问题解决技术)

    这篇关于如何在Python中实现15难题的IDA *算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！