【人工智能大作业】A和IDA搜索算法解决十五数码（15-puzzle）问题（Python实现）（启发式搜索）

2023年7月27日下午5:41 • 人工智能 • 阅读 163

Astar和IDAstar搜索算法解决十五数码（15-puzzle）问题

(文末附实现代码，此前为理论与具体问题分析)

文章目录

Astar和IDAstar搜索算法解决十五数码（15-puzzle）问题
*
–
- (文末附实现代码，此前为理论与具体问题分析)
一、实验题目：
二、实验内容
*
–
- 启发式函数设计：
- 算法原理:
  +
  *
三、实验结果及分析
*
1.启发式函数
–
+
2.环检测优化
3.A与IDA算法性能的比较
4.实验结果
四、算法优化和创新点
*
1.IDA*搜索算法优化：
–
- 关键代码：
2. A*搜索算法优化：
–
- 关键代码：
3.实验结果：
–
+
- 总结:
- 补充：50步以上的测例
  *
  - 50步以上的测例
五、实现代码：
*
–

一、实验题目：

利用A搜索算法和IDA搜索算法解决15-puzzle问题

实验测例包括(以列表表示):

Example1：[[1, 15, 7, 10],[9, 14, 4, 11], [8, 5,0 , 6],[13, 3, 2, 12]]

Example2: [[1, 7, 8, 10],[6, 9, 15, 14], [13, 3, 0, 4], [11, 5, 12, 2]]

Example3: [[5, 6, 4, 12], [11, 14, 9, 1], [0, 3, 8, 15], [10, 7, 2, 13]]

Example4: [[14, 2, 8, 1], [7, 10, 4, 0], [6, 15, 11, 5], [9, 3, 13, 12]]

额外50步以上测例：

测例1: [[11, 3, 1, 7], [4, 6 ,8 ,2], [15 ,9 ,10, 13], [14, 12, 5 ,0]]

测例2: [[14, 10, 6, 0], [4, 9 ,1 ,8], [2, 3, 5 ,11], [12, 13, 7 ,15]]

测例3: [[14, 10, 6, 0],[4, 9 ,1 ,8],[2, 3, 5 ,11],[12, 13, 7 ,15]]

测例4: [[6 ,10, 3, 15],[14, 8, 7, 11],[5, 1, 0, 2],[13, 12, 9 ,4]]

二、实验内容

本次实验主要针对两种启发式搜索进行实现 A搜索算法和IDA搜索算法。

启发式搜索与盲目搜索或者无信息搜索最大的区别就在于启发式搜索采用了启发信息来引导整个搜索的过程，能够减少搜索的范围，降低求解问题的复杂度。这里的启发信息主要由估价函数组成，估价函数f(x)由两部分组成，从初始结点到当前结点n所付出的实际代价g(n)和从当前结点n到目标结点的最优路径的代价估计值h(n)，即 f ( n ) = g ( n ) + h ( n ) f(n) = g(n) + h(n)f (n )=g (n )+h (n )

启发式函数设计：

启发式函数需要满足以下两种性质：

1.可采纳的（admissible）
定义 h ( n ) 为到终点代价的预估值， h ∗ ( n ) 为真实的代价定义h(n)为到终点代价的预估值，h^{*}(n)为真实的代价定义h (n )为到终点代价的预估值，h ∗(n )为真实的代价

若 h ( n ) < = h ∗ ( n ) 成立，即预估值小于真实值的时候，算法必然可以找到一条最短路径若h(n)

2.单调的（consistent）
h ( n ) < = h ( n ′ ) + c o s t ( n , n ′ ) h(n)

算法原理:

I. A*算法

A*搜索算法与BFS类似，但它需要加入估价函数作为启发信息。

算法步骤

开始

1.从起点A开始，将其当作待处理的结点加入open表中

2.将其子结点也加入open表中，计算f(x), g(x),h(x)，其中f(x)=g(x)+h(x)，g(x)表示当前结点的代价，h(x)为当前结点到达目标的代价的估计

3.从open表中取出结点A，并将其加入close表中，表示已经扩展过

循环

4.从open表中弹出f(x)最小的结点C，并加入close表中

5.将C的子结点加入到open表中

6.如果待加入open表中的结点已经在open表中，则更新它们的g(x)，保持open表中该结点的g(x)最小

II. IDA*算法

算法步骤：

算法基于深度优先搜索的思想，加入启发信息，对于给定的阈值bound，定义递归过程

从开始结点C，计算所有子结点的f(x)，选取最小的结点作为下一个访问结点
对于某个节点，如果其f(x)大于bound，则返回当前结点的f(x)，取当中最小的f(x)对bound进行更新
进行目标检测

三、实验结果及分析

【注：实验结果文件均保存于result文件夹中，其中包含搜索的路径，探索的结点个数，运行时间以及IDAstar的搜索限制值】

1.启发式函数

选取不同的启发式函数会对算法的效率造成一定程度的影响，现针对两种启发式函数进行分析。

启发式函数1: 错置的数码块个数之和

在这个启发式函数中，需要统计当前状态下被错置的数码块之和，其值作为当前状态的H(x)。

启发式函数2: 曼哈顿距离

在这个启发式函数中，利用曼哈顿距离公式 M = a b s ( n o d e . x − g o a l . x ) + a b s ( n o d e . y − g o a l . y ) M = abs(node.x – goal.x) + abs(node.y – goal.y)M =a b s (n o d e .x −g o a l .x )+a b s (n o d e .y −g o a l .y )

对除了数码块0以外的所有数码块计算其曼哈顿距离，并将其累加作为当前状态的总曼哈顿距离，

注：计算曼哈顿距离时之所以排除数码块0，是因为若考虑数码块0，则不满足可采纳性(Admittable) h ( n ) < = h ∗ ( n ) h(n)，这个启发式函数就不满足算法的最优性。

举个简单的例子来证明这个结论，若现在的状态为如下：那么下一步肯定是将数码块0向右移动一格，也就是代价为1，而当前状态的h ( n ) = 2 h(n) = 2 h (n )=2，也就是说h ( n ) > h ∗ ( n ) h(n)>h^{*}(n)h (n )>h ∗(n )，这就与可采纳性矛盾。

1 2 3 4
5 6 7 8
9 10 11 12
13 14 0 15

启发式函数1和启发式函数2的效率比较：

为了比较这两种启发式函数的效率，并且获得具体的数值，现采用25步的测例进行实验。

【人工智能大作业】A*和IDA*搜索算法解决十五数码（15-puzzle）问题（Python实现）（启发式搜索）

; 关键代码：

（1）启发式函数1：

（2）启发式函数2：

运行结果：

在A*搜索算法上：

启发式函数1:

启发式函数2:

从结果可以看出，采用启发式函数1需要扩展更多的结点，且运行时间更慢。

因此，在之后的实验中，均采用曼哈顿距离作为启发式函数。

; 2.环检测优化

* IDA*搜索算法 IDA搜索算法本质上为深度优先搜索算法，它在空间上有比广度优先算法更优的性能，即 O ( b m ) O(bm)O (b m ) （其中b是后继结点的个数，m是搜索树的深度），因为它不需要使用队列来保存已经拓展过的结点，如果IDA 采用了环检测则会破坏它在空间上的最优性。因此，对于IDA*的优化并没有采用环检测，而是采用路径检测（这将会在之后讨论到）

3.A 与IDA 算法性能的比较

启发式函数：曼哈顿距离

数码状态存储数据结构：List

环检测数据结构：Set

4.实验结果

（运行结果路径可在Github仓库中的Results文件下载）
测例1 [[1, 15, 7, 10],[9, 14, 4, 11], [8, 5,0 , 6],[13, 3, 2, 12]]

A* 搜索算法运行结果：

Test 1, Total Step 40
Used Time 0.303069 sec
Expanded 2765 nodes

IDA* 搜索算法运行结果：

Test 1, Total Step 40
Used Time 1.194115 sec
Expanded 25590 nodes
Bound: 40

测例2 [[1, 7, 8, 10],[6, 9, 15, 14], [13, 3, 0, 4], [11, 5, 12, 2]]

A* 搜索算法运行结果：

Test 2, Total Step 40
Used Time 0.130206 sec
Expanded 4009 nodes

IDA* 搜索算法运行结果：

Test 2, Total Step 40
Used Time 0.526660 sec
Expanded 6348 nodes
Bound: 40

测例3 [[5, 6, 4, 12], [11, 14, 9, 1], [0, 3, 8, 15], [10, 7, 2, 13]]

A* 搜索算法运行结果：

Test 3, Total Step 40
Used Time 0.089238 sec
Expanded 575 nodes

IDA* 搜索算法运行结果：

Test 3, Total Step 40
Used Time 0.241839 sec
Expanded 2602 nodes
Bound: 40

测例4 [[14, 2, 8, 1], [7, 10, 4, 0], [6, 15, 11, 5], [9, 3, 13, 12]]

A* 搜索算法运行结果：

Test 4, Total Step 40
Used Time 0.985068 sec
Expanded 15017 nodes

IDA* 搜索算法运行结果：

Test 4, Total Step 40
Used Time 18.741641 sec
Expanded 252281 nodes
Bound: 40

总结:

测例Example1Example2Example3Example4Used Time [A| IDA]0.30|1.190.13|0.520.06|0.240.98|18.74Expanded Nodes [A | IDA] (nodes)2765 | 255904009 |6348575|260215017|252281Better [A | IDA]AAAA

从以上A 与IDA在深度为40的搜索树的表现情况来看，A的搜索效率大于IDA，此外，从扩展的结点个数来看，IDA 扩展的结点数更多，这跟IDA本身搜索的方式有关。由于A 需要保存扩展过的结点，因此内存消耗远大于IDA ，至此，可以猜测IDA在深度更大的搜索问题上表现会比A更优，A*需要使用复杂度logn优先队列进行排序，可想而知当待扩展的结点数目剧增的时候，就需要对大量的结点进行排序，存储开销会非常大。

为了验证这个猜想，现采用需要移动49步的15 puzzle进行实验：

测例 [[14, 10, 6, 0],[4, 9 ,1 ,8],[2, 3, 5 ,11],[12, 13, 7 ,15]]

A* 搜索算法运行结果：

Test 2, Total Step 53
Used Time 511.812972 sec
Expanded 22587975 nodes

IDA* 搜索算法运行结果：

Test 2, Total Step 49
Used Time 493.416811 sec
Expanded 9890739 nodes
Bound: 49

从实验结果可以看出，在搜索深度更大的情况下，IDA的表现比A更优。可以猜测到，深度加大以后 A*需要在优先队列中对更多的进行排序，这大大降低了搜索的效率，

四、算法优化和创新点

在以上算法的实现中，存储数码状态的数据结构均为List，Tuple相对与list来说，在存储空间上显得更加轻量级一些。对于元组这样的静态变量，如果它不被使用并且占用空间不大时，Python 会暂时缓存这部分内存。这样，下次我们再创建同样大小的元组时，Python 就可以不用再向操作系统发出请求，去寻找内存，而是可以直接分配之前缓存的内存空间，这样就能大大加快程序的运行速度。

因此，考虑到Tuple在性能上更优，现用Tuple作为存储数码状态的数据结构，对A和IDA分别采用此优化方式。

在子结点的生成中，采用了预生成数码可移动方向（使用时直接查表）和Python内嵌函数的功能进行实现。

启发式函数：曼哈顿距离

数码状态存储数据结构：Tuple

环检测数据结构：Set

1.IDA*搜索算法优化：

关键代码：

generateChild()

预生成数码可移动方向、Python内嵌函数

这部分主要用于生成状态的子结点，由于将二维矩阵转换成了一维元组，所以在数码0的移动上需要作一些修改，也即是将数码0的坐标进行+1，-1，+4，-4，就可以实现上下左右移动的操作；这里提前生成4×4的数码表上16个位置可以移动的方向，并保存在列表movetable中，并采用python内置函数的功能，可直接调用generateChild()的返回值，获得某个状态的子结点。

IDAsearch(g, Hx*, bound)

剪枝优化

这部分是IDA*搜索算法的核心部分，在算法框架的基础上，加入了用set容器实现的CLOSE表，这与优化前不同的是，在优化之前，仍然是采用list进行路径检测，而之前提到过，从查找的角度来说，set的性能在大量数据的前提下是优于list的，因此在这里采用set进行判重，一方面起到了剪枝的作用，一方面能起到优化算法运行效率的作用。

; 2. A*搜索算法优化：

关键代码：

优化后：

A_star(start, Fx)

这里为A搜索算法的核心部分，环检测中以set作为状态存储的容器，这里的状态都以Tuple进行存储，因此可以直接加入set中；生成子结点的方式采用了与上方IDA同样的实现方式。

优化前：

与优化前进行对比，由于采用了列表来存储状态，因此加入set中需要将其转换成字符串的形式，同时包含了繁琐的计算坐标移动的三重for循环。

; 3.实验结果：

下面，我们来看看在 Example1-4上优化后的算法的结果如何：

Example1

A* 搜索算法运行结果：

Test 1, Total Step 40
Used Time 0.092726 sec
Expanded 3055 nodes

IDA* 搜索算法运行结果：

Test 1, Total Step 40
Used Time 0.261489 sec
Expanded 16334 nodes
Bound: 40

Example2

A* 搜索算法运行结果：

Test 2, Total Step 40
Used Time 0.039616 sec
Expanded 4240 nodes

IDA* 搜索算法运行结果：

Test 2, Total Step 40
Used Time 0.271453 sec
Expanded 30105 nodes
Bound: 40

Example3

A* 搜索算法运行结果：

Test 3, Total Step 40
Used Time 0.016239 sec
Expanded 4779 nodes

IDA* 搜索算法运行结果：

Test 3, Total Step 40
Used Time 0.098768 sec
Expanded 37683 nodes
Bound: 40

Example4

A* 搜索算法运行结果：

Test 4, Total Step 40
Used Time 0.483208 sec
Expanded 15259 nodes

IDA* 搜索算法运行结果：

Test 4, Total Step 40
Used Time 5.040609 sec
Expanded 256103 nodes
Bound: 40

总结:

测例Example1Example2Example3Example4优化前Used Time [A| IDA] (sec)0.30|1.190.13|0.520.06|0.240.98|18.74优化后Used Time[A | IDA] (sec)0.09|0.260.03|0.270.01|0.090.48|5.04Better [A | IDA]AAAA

优化前与优化后对比，IDA在运行时间上最高提高了4.5倍的性能，最少也有提升大约1.5倍，A在运行时间上最多提升6倍，最少提升了2倍。两者之中在这四个测例上仍然是A*算法占优。

补充：50步以上的测例

除了Example1-4上的测例以外，这里针对50步以上的测例四个测例，以优化前和优化后进行对比实验：

50步以上的测例

测例1 [[11, 3, 1, 7],[4, 6 ,8 ,2],[15 ,9 ,10, 13],[14, 12, 5 ,0]]

A* 搜索算法运行结果：

&#x4F18;&#x5316;&#x524D;
Test 1, Total Step 56
Used Time 2271.522129 sec
Expanded 18113640 nodes

&#x4F18;&#x5316;&#x540E;
Test 1, Total Step 56
Used Time 1077.335515 sec
Expanded 18116567 nodes

IDA* 搜索算法运行结果：

&#x4F18;&#x5316;&#x524D;&#xFF1A;
&#x65F6;&#x95F4;&#x8FC7;&#x957F;

&#x4F18;&#x5316;&#x540E;&#xFF1A;
Test 1, Total Step 56
Used Time 11228.500149 sec
Expanded 861726906 nodes
Bound: 56

测例2 [[14, 10, 6, 0],[4, 9 ,1 ,8],[2, 3, 5 ,11],[12, 13, 7 ,15]]

A* 搜索算法运行结果：

&#x4F18;&#x5316;&#x524D;&#xFF1A;
Test 2, Total Step 53
Used Time 511.812972 sec
Expanded 22587975 nodes

&#x4F18;&#x5316;&#x540E;&#xFF1A;
Test 2, Total Step 49
Used Time 54.638738 sec
Expanded 4438912 nodes
Bound: 49

IDA* 搜索算法运行结果：

&#x4F18;&#x5316;&#x524D;&#xFF1A;
Test 2, Total Step 49
Used Time 493.416811 sec
Expanded 9890739 nodes
Bound: 49

&#x4F18;&#x5316;&#x540E;&#xFF1A;
Test 2, Total Step 49
Used Time 54.638738 sec
Expanded 4438912 nodes
Bound: 49

测例3 [[0, 5, 15, 14],[7, 9, 6 ,13],[1, 2 ,12, 10],[8, 11, 4, 3]]

A* 搜索算法运行结果：

&#x4F18;&#x5316;&#x524D;&#xFF1A;
Test 3, Total Step 64
Used Time 13271.092952 sec
Expanded 124070829 nodes

&#x4F18;&#x5316;&#x540E;&#xFF1A;
Test 3, Total Step 64
Used Time 5099.071962 sec
Expanded 124434683 nodes

IDA* 搜索算法运行结果：

&#x4F18;&#x5316;&#x524D;&#xFF1A;
&#x65F6;&#x95F4;&#x8FC7;&#x957F;

&#x4F18;&#x5316;&#x540E;&#xFF1A;
&#x65F6;&#x95F4;&#x8FC7;&#x957F;

测例4 [[6 ,10, 3, 15],[14, 8, 7, 11],[5, 1, 0, 2],[13, 12, 9 ,4]]

A* 搜索算法运行结果：

&#x4F18;&#x5316;&#x524D;&#xFF1A;
Test 4, Total Step 48
Used Time 170.719640 sec
Expanded 125820596 nodes

&#x4F18;&#x5316;&#x540E;&#xFF1A;
Test 4, Total Step 48
Used Time 62.862862 sec
Expanded 126187137 nodes

IDA* 搜索算法运行结果：

&#x4F18;&#x5316;&#x524D;&#xFF1A;
Test 4, Total Step 48
Used Time 1111.598261 sec
Expanded 20291684 nodes
Bound: 48

&#x4F18;&#x5316;&#x540E;&#xFF1A;
Test 4, Total Step 48
Used Time 419.185472 sec
Expanded 34135093 nodes
Bound: 48

总结:

测例1234优化前Used Time [A| IDA] (sec)2271.5 |NaN511.8|493.413271.0|NaN170.7|1111.5优化后Used Time[A | IDA] (sec)1077.3|11228.554.6|54.65099.0| Nan62.8 |419.1Better [A | IDA]AIDAA*A

五、实现代码：

或者也可以Clone我的Github仓库并运行代码：Github代码链接

A*优化前：


import copy
import heapq
import numpy as np
import time

end_state = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
node_num  = 0

init_state = [
       [[1, 15, 7, 10],[9, 14, 4, 11], [8, 5,0 , 6],[13, 3, 2, 12]],

   ]

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

OPEN = []

CLOSE = set()

path = []

def print_path(node):
    if node.parent != None:
        print_path(node.parent)
    path.append(node.state)
    return path

class Node(object):
    def __init__(self, gn=0, hn=0, state=None, hash_value=None, parent=None):
       self.gn = gn
       self.hn = hn
       self.fn = self.gn + self.hn
       self.state = state
       self.hash_value = hash_value
       self.parent = parent

    def __lt__(self, node):
        if self.fn == node.fn:
            return self.gn > node.gn
        return self.fn < node.fn

def manhattan(state):
    M = 0
    for i in range(4):
        for j in range(4):
            if state[i][j] == end_state[i][j] or state[i][j] == 0:
                continue
            else:
                x = (state[i][j] - 1) // 4
                y = state[i][j] - 4 * x -1
                M += (abs(x - i) + abs(y - j))
    return M

def misplaced(state):
    sum = 0
    for i in range(4):
        for j in range(4):
            if state[i][j] == 0:
                continue
            if state[i][j] != end_state[i][j]:
                sum += 1
    return sum

def A_star(start, Fx):
    root = Node(0, 0, start, hash(str(start)), None)
    OPEN.append(root)
    heapq.heapify(OPEN)
    CLOSE.add(root.hash_value)
    while len(OPEN) != 0:
        top = heapq.heappop(OPEN)
        global node_num
        node_num += 1
        if top.state == end_state:
            return print_path(top)
        for i in range(4):
            for j in range(4):
                if top.state[i][j] != 0:
                    continue
                for d in range(4):
                    new_x = i + dx[d]
                    new_y = j + dy[d]
                    if 0  new_x  3 and 0  new_y  3:
                        state = copy.deepcopy(top.state)
                        state[i][j], state[new_x][new_y] = state[new_x][new_y], state[i][j]
                        h = hash(str(state))
                        if h in CLOSE:
                            continue
                        CLOSE.add(h)
                        child = Node(top.gn+1, Fx(state), state, h ,top)
                        heapq.heappush(OPEN, child)

if __name__ == '__main__':
    f = open('AStar_result.txt','w')
    for idx, test in enumerate(init_state):
        time1 = time.time()
        PATH = np.asarray(A_star(test, manhattan))
        time2 = time.time()

        test = np.asarray(test)

        for i, p in enumerate(PATH):
            if i == 0:
                 print("15-Puzzle initial state:")
                 print(p)
                 f.write("15-Puzzle initial state:\n")
                 f.write('%s\n\n' %(str(p)))
            else:
                print('Move: %d' %(i))
                print(p)
                f.write('Move: %d \n' %(i))
                f.write("%s \n" %(str(p)))

        print('Test %d, Total Step %d' %(idx+1, len(path)-1))
        print("Used Time %f" %(time2-time1), "sec")
        print("Expanded %d nodes" %(node_num))

        f.write('Test %d, Total Step %d \n' %(idx+1, len(path)-1))
        f.write("Used Time %f sec\n" %(time2-time1))
        f.write("Expanded %d nodes\n\n" %(node_num))

        OPEN.clear()
        CLOSE.clear()
        path.clear()

A*优化后：


import copy
import heapq
import numpy as np
import time

node_num  = 0
end_state = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)

init_state = [
    (1, 15, 7, 10,9, 14, 4, 11, 8, 5,0 , 6, 13, 3, 2, 12),

    ]

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

OPEN = []

CLOSE = set()

path = []

def print_path(node):
    if node.parent != None:
        print_path(node.parent)
    path.append(node.state)
    return path

class Node(object):
    def __init__(self, gn=0, hn=0, state=None, parent=None):
       self.gn = gn
       self.hn = hn
       self.fn = self.gn + self.hn
       self.state = state
       self.parent = parent

    def __lt__(self, node):
        if self.fn == node.fn:
            return self.gn > node.gn
        return self.fn < node.fn

def manhattan(state):
    M = 0
    for t in range(16):
            if state[t] == end_state[t] or state[t]== 0:
                continue
            else:
                x =  (state[t] - 1) // 4
                y =  state[t] - 4 * x - 1
                dx = t // 4
                dy = t % 4
                M += (abs(x - dx) + abs(y - dy))
    return M

def generateChild():
   movetable = []
   for i in range(16):
       x, y = i % 4, i // 4
       moves = []
       if x > 0: moves.append(-1)
       if x < 3: moves.append(+1)
       if y > 0: moves.append(-4)
       if y < 3: moves.append(+4)
       movetable.append(moves)
   def children(state):
       idxz = state.index(0)
       l = list(state)
       for m in movetable[idxz]:
           l[idxz] = l[idxz + m]
           l[idxz + m] = 0
           yield(1, tuple(l))
           l[idxz + m] = l[idxz]
           l[idxz] = 0
   return children

def A_star(start, Fx):
    root = Node(0, 0, start, None)

    OPEN.append(root)
    heapq.heapify(OPEN)

    CLOSE.add(start)

    while len(OPEN) != 0:
        top = heapq.heappop(OPEN)
        global node_num
        node_num += 1
        if top.state == end_state:
            return print_path(top)

        generator = generateChild()
        for cost, state in generator(top.state):
            if state in CLOSE:
                continue
            CLOSE.add(state)
            child = Node(top.gn+cost, Fx(state), state,top)
            heapq.heappush(OPEN, child)

if __name__ == '__main__':
    f = open('AStar_Result_M.txt','w')
    for idx, test in enumerate(init_state):
        time1 = time.time()
        PATH = np.asarray(A_star(test, manhattan))
        time2 = time.time()

        test = np.asarray(test)

        for i, p in enumerate(PATH):
            if i == 0:
                 print("15-Puzzle initial state:")
                 print(p)
                 f.write("15-Puzzle initial state:\n")
                 f.write('%s\n\n' %(str(p)))
            else:
                print('Move: %d' %(i))
                print(p)
                f.write('Move: %d \n' %(i))
                f.write("%s \n" %(str(p)))

        print('Test %d, Total Step %d' %(idx+1, len(path)-1))
        print("Used Time %f" %(time2-time1), "sec")
        print("Expanded %d nodes" %(node_num))

        f.write('Test %d, Total Step %d \n' %(idx+1, len(path)-1))
        f.write("Used Time %f sec\n" %(time2-time1))
        f.write("Expanded %d nodes\n\n" %(node_num))

        OPEN.clear()
        CLOSE.clear()
        path.clear()

IDA*优化前：

import numpy as np
import time
import copy

end_state = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
node_num = 0

init_state = [
   [[1, 15, 7, 10],[9, 14, 4, 11], [8, 5,0 , 6],[13, 3, 2, 12]],

    ]
CLOSE = {}

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
def is_goal(node):
    index = 1
    for row in node:
        for col in row:
            if(index != col):
                break
            index += 1
    return index == 16

def manhattan(state):
    M = 0
    for i in range(4):
        for j in range(4):
            if state[i][j] == end_state[i][j] or state[i][j] == 0:
                continue

            else:
                x = int((state[i][j] - 1) / 4)
                y =  state[i][j] - 4 * x - 1
                M += (abs(x - i) + abs(y - j))
    return M

def misplaced(state):
    sum = 0
    for i in range(4):
        for j in range(4):
            if state[i][j] == 0:
                continue
            if state[i][j] != end_state[i][j]:
                sum += 1
    return sum

def generateChild(state, Hx):
    child = []
    for i in range(4):
            for j in range(4):
                if state[i][j] != 0:
                    continue
                for d in range(4):
                    new_x = i + dx[d]
                    new_y = j + dy[d]
                    if 0  new_x  3 and 0  new_y  3:
                        new_state = copy.deepcopy(state)
                        new_state[i][j], new_state[new_x][new_y] = new_state[new_x][new_y], new_state[i][j]
                        child.append(new_state)

    return sorted(child, key=lambda x: Hx(x))

def IDAsearch(path, g, Hx, bound):
    global node_num
    node = path[-1]
    node_num +=1

    f = g + Hx(node)
    if f > bound:
        return f
    if node == end_state:
        return 0

    Min = 99999
    CLOSE[str(node)] = g

    for c in generateChild(node, Hx):

            path.append(c)
            t = IDAsearch(path, g+1, Hx, bound)
            if t == 0:
                return 0
            if t < Min:
                Min = t
            path.pop()

    return Min

def IDAstar(start, Hx):
    bound = Hx(start)
    path = [start]
    CLOSE[str(start)] = 0

    while(True):
        ans = IDAsearch(path, 0, Hx,bound)
        if(ans == 0):
            return (path,bound)
        if ans == -1:
            return None
        bound = ans

if __name__ == '__main__':
    f = open('IDAStar_Difresult.txt','w')
    for idx, test in enumerate(init_state):
        time1 = time.time()
        PATH,BOUND = IDAstar(test, misplaced)
        time2 = time.time()
        PATH = np.asarray(PATH)

        test = np.asarray(test)

        for i, p in enumerate(PATH):
            if i == 0:
                 print("15-Puzzle initial state:")
                 f.write("15-Puzzle initial state:\n")

                 p = np.asarray(p)
                 print(p)
                 f.write('%s\n\n' %(str(p)))
            else:
                print('Move: %d' %(i))

                f.write('Move: %d \n' %(i))
                p = np.asarray(p)
                print(p)
                f.write("%s \n" %(str(p)))

        print('Test %d, Total Step %d' %(idx+1, len(PATH)-1))
        print("Used Time %f" %(time2-time1), "sec")
        print("Expanded %d nodes" %(node_num))
        print("Bound: %d" %(BOUND))

        f.write('Test %d, Total Step %d \n' %(idx+1, len(PATH)-1))
        f.write("Used Time %f sec\n" %(time2-time1))
        f.write("Expanded %d nodes\n" %(node_num))
        f.write("Bound: %d\n\n" %(BOUND))

IDA*优化后：

import numpy as np
import time
import copy

end_state = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)
node_num = 0

init_state = [
     (1, 15, 7, 10,9, 14, 4, 11, 8, 5,0 , 6, 13, 3, 2, 12),

     (0, 5, 15, 14,7, 9, 6 ,13,1, 2 ,12, 10,8, 11, 4, 3),

    ]

CLOSE = set()
path = []

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

def manhattan(state):
    M = 0
    for t in range(16):
            if state[t] == end_state[t] or state[t]== 0:
                continue
            else:
                x =  (state[t] - 1) // 4
                y =  state[t] - 4 * x - 1
                dx = t // 4
                dy = t % 4
                M += (abs(x - dx) + abs(y - dy))
    return M

def generateChild():
   movetable = []
   for i in range(16):
       x, y = i % 4, i // 4
       moves = []
       if x > 0: moves.append(-1)
       if x < 3: moves.append(+1)
       if y > 0: moves.append(-4)
       if y < 3: moves.append(+4)
       movetable.append(moves)
   def children(state):
       idxz = state.index(0)
       l = list(state)
       for m in movetable[idxz]:
           l[idxz] = l[idxz + m]
           l[idxz + m] = 0
           yield(1, tuple(l))
           l[idxz + m] = l[idxz]
           l[idxz] = 0
   return children

def IDAsearch(g, Hx, bound):
    global node_num
    node = path[-1]
    node_num +=1
    f = g + Hx(node)
    if f > bound:
        return f
    if node == end_state:
        return 0

    Min = 99999
    generator = generateChild()
    for cost, state in generator(node):
        if state in CLOSE: continue
        path.append(state)
        CLOSE.add(state)
        t = IDAsearch(g+1,Hx,bound)

        if t == 0: return 0
        if t < Min: Min = t

        path.pop()
        CLOSE.remove(state)
    return Min

def IDAstar(start, Hx):
    global CLOSE
    global path
    bound = Hx(start)
    path = [start]
    CLOSE = {start}

    while(True):
        ans = IDAsearch(0, Hx,bound)
        if(ans == 0):
            return (path,bound)
        if ans == -1:
            return None
        bound = ans

if __name__ == '__main__':
    f = open('IDAStar_result.txt','w')
    for idx, test in enumerate(init_state):
        time1 = time.time()
        PATH,BOUND = IDAstar(test, manhattan)
        time2 = time.time()
        PATH = np.asarray(PATH)

        test = np.asarray(test)

        for i, p in enumerate(PATH):
            if i == 0:
                 print("15-Puzzle initial state:")
                 f.write("15-Puzzle initial state:\n")

                 p = np.asarray(p)
                 print(p)
                 f.write('%s\n\n' %(str(p)))
            else:
                print('Move: %d' %(i))

                f.write('Move: %d \n' %(i))
                p = np.asarray(p)
                print(p)
                f.write("%s \n" %(str(p)))

        print('Test %d, Total Step %d' %(idx+1, len(PATH)-1))
        print("Used Time %f" %(time2-time1), "sec")
        print("Expanded %d nodes" %(node_num))
        print("Bound: %d" %(BOUND))

        f.write('Test %d, Total Step %d \n' %(idx+1, len(PATH)-1))
        f.write("Used Time %f sec\n" %(time2-time1))
        f.write("Expanded %d nodes\n" %(node_num))
        f.write("Bound: %d\n\n" %(BOUND))

Original: https://blog.csdn.net/m0_52387305/article/details/123531945
Author: Maxwell-Wong
Title: 【人工智能大作业】A和IDA搜索算法解决十五数码（15-puzzle）问题（Python实现）（启发式搜索）

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/718829/

转载文章受原作者版权保护。转载请注明原作者出处！

人工智能

【自取】最近整理的，有需要可以领取学习：

Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言刷题答案下载！

手把手教你：铁路异物侵入的目标检测系统

系列文章手把手教你：图像识别的垃圾分类系统手把手教你：人脸识别考勤系统手把手教你：基于粒子群优化算法（PSO）优化卷积神经网络（CNN）的文本分类目录系列文章一、项目简…

人工智能 2023年7月11日
0054
计算机视觉基础学习-图像拼接

1、基础理解首先本文介绍的图像拼接并非对尺寸相同的图片进行简单拼接，而是基于全景图的拼接普通相机拍摄图像时，无法兼顾相机视场与视场中单个物体的分辨率问题，而全景相机普遍价格昂贵…

人工智能 2023年6月22日
0086
Python Matplotlib 折线图线条颜色和样式

Python Matplotlib 折线图线条颜色和样式折线颜色折线形状数据点（节点）形状坐标示例折线颜色 ; 折线形状 ‘-‘ ：实线&#8…

人工智能 2023年7月4日
00104
《动手学深度学习》第三章-softmax回归总结

《动手学深度学习》第三章-softmax回归总结 softmax回归总结《动手学深度学习》第三章-softmax回归总结 * 1.从fashion_mnist导入数据(d2l.l…

人工智能 2023年6月17日
00104
Matplotlib设置坐标轴日期格式

Matplotlib设置坐标轴日期格式绘制双坐标轴 ax2=ax1.twinx() 创建了一个独立的Y轴，共享了X轴。双坐标轴！类似的还有twiny() 设置坐标轴日期格式需…

人工智能 2023年7月16日
0083
CVPR2022 目标检测方向文章（附摘要）

CVPR官方下载：主会论文：https://openaccess.thecvf.com/CVPR2022 Workshop论文：https://openaccess.thecvf….

人工智能 2023年6月16日
0067
图像分割之Unet解析及实现代码

Unet解析及实现代码论文连接: https://arxiv.org/pdf/1505.04597.pdf 源码连接: https://github.com/FENGShuang…

人工智能 2023年6月17日
0077
深挖ROC曲线（截断值计算） – 基于R语言

深挖ROC曲线（截断值计算） – 基于R语言前言混淆矩阵 * 1.通过混淆矩阵计算准确度为什么需要计算截断值重点部分：AUC计算和截断值定义 * 1.何为最佳截…

人工智能 2023年7月2日
0081
FPN特征金字塔网络

改进卷积神经网络目标检测，提取多尺度的特征信息进行融合，提高目标检测的精度 R-CNN系列是在得到的最后一层特征图上进行特征提取，从而进行目标识别的，顶层特征在不断地卷积池化过程…

人工智能 2023年6月22日
0078
Iterative Entity Alignment via Knowledge Embeddings

概述：本文主要解决的问题是不同KG间的实体对齐问题。之前解决这个问题主要依靠一些额外的信息来完成，比如维基百科。但在本文中，我们依靠aligned entities也就是已经对齐…

人工智能 2023年6月10日
0085
[人脸算法]技术方向综述

01 人脸技术的应用人脸硬件产品：考勤支付，安防监控，医疗美容人脸软件产品：各类娱乐软件，如美图秀秀 02 人脸图像算法及其研究方向人脸检测核心算法目的：检测图像中是否存在人…

人工智能 2023年6月6日
0089
机器学习之分类与回归的常见评价指标

在人工智能领域，机器学习的模型及效果如何需要用各种指标来评价。本文将简单介绍几种机器学习中无监督学习的常用评价指标。无监督学习主要分为两类：分类问题与回归问题。分类问题又分为二分…

人工智能 2023年6月30日
0067
数据挖掘学习报告一

1.观看学习了学堂在线《数据科学导论》 1.1了解了一些数据科学发展史：中国已将大数据发展确定为国家战略。 1.2认识了一些基本概念：（1）”数据”指的…

人工智能 2023年7月17日
0062
【毕业设计/课程设计】基于opencv的高精度人脸识别考勤系统设计与实现

啊哦~你想找的内容离你而去了哦内容不存在，可能为如下原因导致： ① 内容还在审核中 ② 内容以前存在，但是由于不符合新的规定而被删除 ③ 内容地址错误 ④ 作者删除了内容。可…

人工智能 2023年6月18日
0095
Pytorch中RNN参数解释

其实构建rnn的代码十分简单，但是实际上看了下csdn以及官方tutorial的解释都不是很详细，说的意思也不能够让人理解，让大家可能会造成一定误解，因此这里对rnn的参数做一个详…

人工智能 2023年6月6日
00108
关于Focal loss损失函数的代码实现

Focal loss的公式：其中用到的交叉熵损失函数表达式是（3） F L （ p t ） = − ( 1 − p t ) γ log ⁡ p t (1) FL（p_{t}） = …

人工智能 2023年6月15日
0086

2024 年 5 月
一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

【人工智能大作业】A*和IDA*搜索算法解决十五数码（15-puzzle）问题 （Python实现）（启发式搜索）

(文末附实现代码，此前为理论与具体问题分析)

文章目录

启发式函数设计：

算法原理:

I. A*算法

II. IDA*算法

算法步骤：

1.启发式函数

启发式函数1: 错置的数码块个数之和

启发式函数2: 曼哈顿距离

启发式函数1和启发式函数2的效率比较：

; 关键代码：

运行结果：

; 2.环检测优化

3.A 与IDA 算法性能的比较

4.实验结果

1.IDA*搜索算法优化：

关键代码：

; 2. A*搜索算法优化：

关键代码：

; 3.实验结果：

总结:

补充：50步以上的测例

50步以上的测例

A*优化前：

A*优化后：

IDA*优化前：

IDA*优化后：

大家都在看

【人工智能大作业】A和IDA搜索算法解决十五数码（15-puzzle）问题（Python实现）（启发式搜索）