人工智能入门-查找

XR

发布于：2021年4月10日
次浏览

概述

众所周知，人工智能在近些年十分火爆，在各个领域的应用也是十分广泛，其中一个领域就是导航。

也许有人会说，导航不就是电子地图嘛？和人工智能有什么关系？但其实在导航中人工智能发挥了很重要的作用。“条条大路通罗马”，为什么导航会向你推荐这条路而不推荐另一条路？这其中就涉及到了人工智能中的搜索算法。

B7S4Ln.png

在搜索中，往往有初始状态(initial states)、目标状态(goal states)，而人工智能所做的，就是在众多情形中，找到众多解决方法的最优解，其中会涉及到循环和迭代，假如我们现在有一个初始状态，我们要怎样达到目标状态呢？

概念介绍

在这之前需要先了解一些概念：

  • 动作：通常是接受状态的函数，返回在此状态中应该做出的决策
  • 迁移模型：通常是接受状态和动作的函数，返回在此状态下做出此种决策后的新状态
  • 节点：数据结构，用来记录状态，父节点，动作和路径成本
  • 边界：数据结构，用来区分已探索的部分和未探索的部分

算法讨论

在了解了相关概念之后，我们开始讨论算法：

  • 首先将初始状态放入边界，然后进入循环
    • 如果边界为空，则无解
    • 从边界中移去一个节点
    • 如果此节点包含目标状态，则追踪父节点，然后返回解决方案
    • 扩张节点并将其加入边界

下面举个例子：

B7StR6.png

假设我们现在的要求是找到从A到E的路径

  • 第一步我们将A（初始状态）放入边界，进入循环
  • 因为A不是目标状态，将A移出边界并将B加入边界
  • 因为B不是目标状态，将B移出边界并将C和D加入边界
  • 因为C不是目标状态，将C移出边界并将E加入边界
  • 因为E是目标状态，所以我们返回从A到E的路径，循环结束
至此，我们就解决了一个非常简单的路径搜索问题，当然，这个算法还存在着许多问题，比如：如何确保算法不会重新检查当前状态的父节点？如果重复检查父节点，那么程序将进入无限死循环。解决方法很简单，使用一个数据结构来储存已检查过的节点，然后在每次检查节点时遍历此数据结构，如果存在与之相同的节点则不检查。

那么在实际情况下是怎么样的呢？

实战

下面进入实战环节：

情境：你现在有一张迷宫地图，起点为A，终点为B，需要编写程序令计算机自行找出离开迷宫的路并显示在屏幕上

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

# # # # #   # # # # 

# # # # #   # # # # 

# # # # #   # # # # 

# # # # #   # # # # 

                    

# # # # #   # # # # 

# # # # #   # # # # 

# # # # #   # # # # 

A           # # # #

我们将这个待实现的程序按照之前所讨论的分为几个部分：

BITMNm.png

如图所示，我们主要将程序分为三个部分：

首先是定义相关的变量，并且将初始状态放入边界；

然后进入循环：

  • 第一步：检查边界的长度，如果等于0则说明无解
  • 第二步：从边界中移去一个节点，并将此节点添加到表示已探索的数据结构
  • 第三步：检查被移去的节点，如果此节点包含目标状态，则追踪其父节点，并返回路径

最后，我们使用一个循环来追踪完整的路径，并将其显示在屏幕上。

以下是根据思路实现的代码：

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
map1  = [['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']]

# set the route
map1[9][0]='A'
map1[0][9]='B'
for i in range(10):
    map1[5][i] = ' '

for i in range(10):
    map1[i][5] = ' '

map1[9][1] = ' '
map1[9][2] = ' '
map1[9][3] = ' '
map1[9][4] = ' '

map1[0][6] = ' '
map1[0][7] = ' '
map1[0][8] = ' '

# print out the map

for i in map1:
    for j in i:
        print(j,end=' ')
    print("\n")

class Unit:
    def __init__(self,c,p):
        x=c[0]
        y=c[1]
        self.x=x
        self.y=y
        self.up=(self.x,self.y+1)
        self.down=(self.x,self.y-1)
        self.left=(self.x-1,self.y)
        self.right=(self.x+1,self.y)
        self.directions = [self.up,self.down,self.left,self.right]
        self.parent = p

start=Unit((9,0),(0,0))
goal=Unit((0,9),(-1,-1))

def travel(map1,start):
    frontier = []
    explored = []
    current = Unit((start.x,start.y),start.parent)
    frontier.append(current)
    
    while True:
        if len(frontier) == 0:
            print("No result")
            break

        del(frontier[0])
        explored.append(Unit((current.x,current.y),current.parent))

        if current.x == goal.x and current.y == goal.y:
            print("\nGot it!\n")
            
            while current.parent != (0,0):
                for trace in explored:
                    if trace.x == current.parent[0] and trace.y == current.parent[1]:
                        if map1[current.x][current.y] == ' ':
                            map1[current.x][current.y] = '.'
                        # print(current.x,current.y)
                        current = trace
                        
            for i in map1:
                for j in i:
                    print(j,end=' ')
                print("\n")
            break
        for i in current.directions:
            j=Unit((i[0],i[1]),(current.x,current.y))
            # print((j.x,j.y),end=',')
            condition = 1
            for x in explored:
                if x.x==j.x and x.y==j.y:
                    condition = 0
            if condition and j.x>=0 and j.x<=9 and j.y>=0 and j.y<=9 and map1[j.x][j.y] != '#':
                frontier.append(Unit((i[0],i[1]),(current.x,current.y)))
        current = frontier[0]
        
travel(map1,start)

在实现的过程中，我遇到了一些问题：

  • 由于对Python中类的使用不熟练，导致代码中有关部分看起来很奇怪
  • 在遍历当前节点周围的有效节点时，没有重新初始化节点，而是直接将当前节点周围有效节点的坐标加入边界，导致循环从第二次开始就无法进行，因为坐标没有“周围的有效节点”这个属性
  • 在将以探索过的节点加入对应数据结构后，检查下一个节点是否在此数据结构时直接使用“==”，但是即使坐标相同的两个节点也可能不相等，原因是这两个节点存在于不同的地址，正确的做法是再遍历一遍存储以探索过的数据结构，直接比较此数据结构中节点的坐标值

在完成初步的实现后，处于对代码重构的要求，对代码做了相关的函数封装：

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
97
98
99
100
101
102
103
104
105
106
107
map1  = [['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
         ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']]

# set the route
map1[9][0]='A'
map1[0][9]='B'
for i in range(10):
    map1[5][i] = ' '

for i in range(10):
    map1[i][5] = ' '

map1[9][1] = ' '
map1[9][2] = ' '
map1[9][3] = ' '
map1[9][4] = ' '

map1[0][6] = ' '
map1[0][7] = ' '
map1[0][8] = ' '

# print out the map

def map_show(map1):
    for i in map1:
        for j in i:
            print(j,end=' ')
        print("\n")

map_show(map1)

class Unit:
    def __init__(self,c,p):
        x=c[0]
        y=c[1]
        self.x=x
        self.y=y
        self.up=(self.x,self.y+1)
        self.down=(self.x,self.y-1)
        self.left=(self.x-1,self.y)
        self.right=(self.x+1,self.y)
        self.directions = [self.up,self.down,self.left,self.right]
        self.parent = p

start=Unit((9,0),(0,0))
goal=Unit((0,9),(-1,-1))

def route_trace(current,explored):
    while current.parent != (0,0):
        for trace in explored:
            if trace.x == current.parent[0] and trace.y == current.parent[1]:
                if map1[current.x][current.y] == ' ':
                    map1[current.x][current.y] = '.'
                # print(current.x,current.y)
                current = trace


def action(frontier,explored,current):
    for i in current.directions:
        j=Unit((i[0],i[1]),(current.x,current.y))
        # print((j.x,j.y),end=',')
        condition = 1
        for x in explored:
            if x.x==j.x and x.y==j.y:
                condition = 0
        if condition and j.x>=0 and j.x<=9 and j.y>=0 and j.y<=9 and map1[j.x][j.y] != '#':
            frontier.append(Unit((i[0],i[1]),(current.x,current.y)))





def travel(map1,start):
    frontier = []
    explored = []
    current = Unit((start.x,start.y),start.parent)
    frontier.append(current)
    
    while True:
        if len(frontier) == 0:
            print("No result")
            break
        del(frontier[0])
        explored.append(Unit((current.x,current.y),current.parent))

        if current.x == goal.x and current.y == goal.y:
            print("\nGot it!\n")
            
            route_trace(current,explored)
            map_show(map1)
            break
        action(frontier,explored,current)
        if len(frontier) == 0:
            print("No result")
            break
        current = frontier[0]
        
travel(map1,start)

结果如下：

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
# # # # #         B 

# # # # #   # # # # 

# # # # #   # # # # 

# # # # #   # # # # 

# # # # #   # # # # 

                    

# # # # #   # # # # 

# # # # #   # # # # 

# # # # #   # # # # 

A           # # # # 


Got it!

# # # # # . . . . B 

# # # # # . # # # # 

# # # # # . # # # # 

# # # # # . # # # # 

# # # # # . # # # # 

          .         

# # # # # . # # # # 

# # # # # . # # # # 

# # # # # . # # # # 

A . . . . . # # # #

现在，这个程序已经能够找出各种迷宫地图的解法了，也就是说，如果我们对地图进行修改，程序也能够正常运行并输出相应结果，比如，我们将地图的唯一道路“封死”，那么结果就会是“No result”，如下所示：

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

# # # # #   # # # # 

# # # # #   # # # # 

# # # # #   # # # # 

# # # # #   # # # # 

                    

# # # # #   # # # # 

# # # # #   # # # # 

# # # # #   # # # # 

A     #     # # # # 

No result

至此，我们就完成了对此情境下相关代码的编写。

修改于2021.04.11

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://uniqueland.top/2021/04/10/%E4%BA%BA%E5%B7%A5%E6%99%BA%E8%83%BD%E5%85%A5%E9%97%A8-%E6%90%9C%E7%B4%A2/

更新于：2021年5月2日

知识输出

AI

评论