如何在Python中实现IDA*算法来解决这个难题？

Question

我试图用IDA*算法和曼哈顿启发式算法来解决15个难题。 我已经在这个Wikipedia页面（link）的伪代码中实现了该算法

以下是我目前的代码：

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的谜题测试这段代码，这里是无限循环！由于递归，我在测试代码时遇到了一些问题

我认为错误可能在这里：tmp = search(path, goal_state, g + 1, threshold)（在search函数中）。我只在g成本值上加一个。这应该是正确的，因为我只能把一块瓷砖移到1个地方

下面是如何调用IDA()函数：

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)

有人能帮我吗

Answer 1

在IDA*实现中有几个问题。首先，变量path的用途是什么？我在代码中发现了path的两个用途：

1. 用作标志/map以保持已访问的板状态
2. 用作堆栈来管理递归状态

但是，使用单一的数据结构不可能同时完成这两项工作。因此，您的代码需要进行的第一次修改：

• Fix-1：将当前node作为参数传递给search方法
• Fix-2:flag应该是一个能够高效执行not in查询的数据结构

现在，fix-1很容易，因为我们可以将当前访问节点作为搜索方法中的参数传递。对于fix-2，我们需要将flag的类型从list更改为set，如下所示：

• list的{}的平均案例复杂度为：O（n）
• set
  • x in s的平均案例复杂度为：O（1）
  • x in s的最坏情况复杂性为：O（n）

您可以查看有关performance for testing memberships: list vs sets的更多详细信息以了解更多详细信息

现在，要将Node信息保存到set中，需要在Node类中实现__eq__和__hash__。在下面，我附上了修改后的代码

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 repository以获得其他算法实现（即A*、IDS、DLS）来解决此问题

参考文献：

1. Python Wiki: Time Complexity
2. TechnoBeans: Performance for testing memberships: list vs tuples vs sets
3. GitHub: Puzzle Solver (by using problem solving techniques)