AI-A*算法-8/15数码_python 人工智能a*算法求解8比特和15数码问题

简介

---

用Python编写的人工智能小程序，运用 A* 算法实现了8、15数码问题的求解，其中评价函数有曼哈顿距离以及不在位数码个数两种，用户可自行选择，用户可以随机生成或自定义初始、目标布局，另外加入了代码联动，动态地展示OPEN、CLOSE表的生成过程，用户可以清楚地看出当前运行到的步骤，同时还可以随时调节运行速度、暂停运行、继续运行，当然，如果用户不想逐步运行，可以点击“快速运行”按钮，待求解完成之后再点击“展示OPEN/CLOSE表”按钮即可查看表内容。

源代码

---

代码由以下五部分组成：

• Constant.py

class Constant():
    def __init__(self):
        self.options = [" 8 数码", "15 数码"]
        self.options1 = ["曼哈顿距离", "不在位数码个数"]
        self.list_A = [" A*算法流程", \
                "（1）把 S 放入 OPEN 表中，记 f=h，令 CLOSE 为空表", \
                "（2）若 OPEN 表为空表，则宣告失败并退出", \
                "（3）选取 OPEN 表中未设置过的具有最小 f 值的节点为最佳节点 BESTNODE，并把它放入 CLOSE 表中", \
                "（4）若 BESTNODE 为一目标节点，则成功求得一解并退出", \
                "（5）若 BESTNODE 不是目标节点，则扩展之，产生后继节点 SUCCSSOR", \
                "（6）对每个 SUCCSSOR 进行下列过程：", \
                "    （a）建立从 SUCCSSOR 返回 BESTNODE 的指针", \
                "    （b）若 SUCCSSOR 在 CLOSE 表中，则停止扩展此节点", \
                "    （c）若 SUCCSSOR 在 OPEN 表中且新 g(n) 值较小，则将旧节点更新", \
                "    （d）若 SUCCSSOR 在 OPEN 表中但新 g(n) 值较大或相等，则停止扩展此节点", \
                "    （e）若 SUCCSSOR 既不在 OPEN 表中也不在 CLOSE 表中，则将此节点加入 OPEN 表中", \
                "（7）若还有其他扩展节点，转第（6）步；若无其他扩展节点，转第（2）步"]
        self.init_8 = [[7,1,2],[8,5,3],[6,0,4]]
        self.goal_8 = [[1,2,3],[8,0,4],[7,6,5]]
        self.init_15 = [[2,3,4,8],[0,6,15,7],[1,5,10,12],[9,13,11,14]]
        self.goal_15 = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,0]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• Digital.py

class Digital():
    def __init__(self, prev, name, group, fn):
        if prev:
            self.prev = prev    # 父节点
        else:
            self.prev = self
        self.name = name        # 节点名称
        self.group = group[:]   # 数码矩阵
        self.fn = fn            # f(n)值
        if prev == '':
            self.deep = 0
        else:
            self.deep = prev.deep + 1
    
    # 设置节点在 CLOSE 表中的编号
    def set_num(self, num):
        self.num = num
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• Arithmetic.py

import math

# 曼哈顿距离
class Arith1():
    def arith(self, deep, grp1, grp2):
        num = deep
        for each1 in grp1:
            for m1 in each1:
                if m1:
                    row1 = grp1.index(each1)
                    col1 = each1.index(m1)
                    for each2 in grp2:
                        flag = False
                        for m2 in each2:
                            if m1 == m2:
                                flag = True
                                row2 = grp2.index(each2)
                                col2 = each2.index(m2)
                                break
                        if flag:
                            break
                    num += int(math.fabs(row1-row2) + math.fabs(col1-col2))

        return num

# 不在位数码个数
class Arith2():
    def arith(self, deep, grp1, grp2):
        num = deep
        n = len(grp1)
        for i in range(n):
            for j in range(n):
                if grp1[i][j]:
                    if grp1[i][j] != grp2[i][j]:
                        num += 1
        return num
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
32
33
34
35
36

• Move.py

class Move():
    
    def left(self, group):
        grp = group[:]
        for each in group:
            for i in each:
                if i == 0:
                    col = each.index(i)
                    if col == 0:
                        return False
                    row = group.index(each)
                    break
        grp[row][col] = grp[row][col-1]
        grp[row][col-1] = 0
        return grp[:]

    def right(self, group):
        grp = group[:]
        for each in group:
            for i in each:
                if i == 0:
                    col = each.index(i)
                    if col == len(each)-1:
                        return False
                    row = group.index(each)
                    break
        grp[row][col] = grp[row][col+1]
        grp[row][col+1] = 0
        return grp[:]
    
    def up(self, group):
        grp = group[:]
        for each in group:
            for i in each:
                if i == 0:
                    row = group.index(each)
                    if row == 0:
                        return False
                    col = each.index(i)                    
                    break
        grp[row][col] = grp[row-1][col]
        grp[row-1][col] = 0
        return grp[:]

    def down(self, group):
        grp = group[:]
        for each in group:
            for i in each:
                if i == 0:
                    row = group.index(each)
                    if row == len(each)-1:
                        return False
                    col = each.index(i)                    
                    break
        grp[row][col] = grp[row+1][col]
        grp[row+1][col] = 0
        return grp[:]
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

• A-Star.py

import Arithmetic
import Constant
import Digital
import Move
import time
import math
import random
import threading
from tkinter import *
from tkinter import ttk
from tkinter import messagebox


root = Tk()
root.title("A-Star 算法")

MOVE = Move.Move()
ARIT1 = Arithmetic.Arith1()
ARIT2 = Arithmetic.Arith2()
CONSTANT = Constant.Constant()

# 存放初始、目标布局矩阵
group_init = []
group_goal = []

# 存放初始布局到目标布局的移动过程
group_course = []

# 存放 OPEN、CLOSE表内容
group_open = []
group_close = []

# 使用过的所有节点数
COUNT1 = 0

# 终止运行标志
STOP = False

# 生成随机 N 数码数组
def range_create(num):
    group = []
    grp = []
    m = int(math.sqrt(num+1))
    for i in range(m):
        grp1 = []
        for i in range(m):
            n = random.randint(0, num)
            while n in grp:
                n = random.randint(0, num)
            grp.append(n)
            grp1.append(n)
        group.append(grp1)
    return group

# 数组转换成字符串
def grp_tran(group):
    st = " "
    for each in group:
        for n in each:
            if n == 0:
                st += "        "
            elif n < 10:
                st += " " + str(n) + "     "
            else:
                st += str(n) + "    "
        st = st[:len(st)-3]
        st += "\n\n "
    st = st[:len(st)-3]
    return st

# 获取数码显示字体大小
def get_bold1():
    st = variable.get()
    num = int(math.sqrt(int(st[:len(st)-3])+1))
    num = str(24 - (num - 3) * 5)
    st = 'Helvetica -' + num + ' bold'
    return st

def get_bold2():
    st = variable.get()
    num = int(math.sqrt(int(st[:len(st)-3])+1))
    num = str(16 - (num - 3) * 3)
    st = 'Helvetica -' + num + ' bold'
    return st

# 初始布局缺省生成
def default_init():
    lab2['font'] = get_bold1()
    st = variable.get()
    num = int(st[:len(st)-3])
    if num == 8:
        group_init[:] = CONSTANT.init_8
    elif num == 15:
        group_init[:] = CONSTANT.init_15
    sv_init.set(grp_tran(group_init))

# 目标布局缺省生成
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96