人工智能导论——搜索问题与技术
第1关：搜索策略
-
1、
若将搜索问题看成是走迷宫，搜索空间越大，则迷宫越大
正确
-
2、
常用的搜索策略方式为盲目搜索与启发式搜索
正确
-
3、
下列说法正确的是：B C D
A、
搜索问题只专注于能不能得到解
B、
广度优先搜索算法属于盲目搜索
C、
搜索问题的解可能有多个
D、
A*算法属于启发式搜索
第2关：盲目搜索
def PlayMazz(mazz, start, end):
'''
走迷宫，从start走到end
:param mazz: 迷宫
:param start: 迷宫的起点
:param end: 迷宫的出口
'''
# queue为队列，当队列为空或者当前地点为H时搜索结束
visited, queue = set(), [start]
while queue:
# 从队列中出队，即当前所处的地点
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
print(vertex, end='')
#********* Begin *********#
if vertex == end:
return
#********* Begin *********#
#当走到出口时结束算法
# 将当前所处地点所能走到的地点放入队列
for v in mazz[vertex]:
if v not in visited:
queue.extend(v)
第3关：启发式搜索 - 扫地机器人最短路径搜索
from a_star_utils import Node
def A_star(map, mapSize, start, end):
'''
A*算法，从start走到end
:param map:地图
:param mapSize:地图大小，例如[10,10]表示地图长10宽10
:param start:表示出发地，类型为列表，如[1,2]表示出发地为地图中的第1行第2列的方块
:param end:表示目的地，类型为列表，如[1,2]表示目的地为地图中的第1行第2列的方块
:return:从出发地到目的地的路径
'''
openedList = []
#********* Begin *********#
# 获得出发地方块的信息，并将信息保存为node变量
node = map[start[0]][start[1]]
#********* End *********#
node.distanceFromOri = 0
node.allDistance = 0
#********* Begin *********#
# 将当前方块存到开启列表中
openedList.append (node)
node.added = True
#********* End *********#
while len(openedList) != 0:
node = openedList.pop(0)
node.closed = True
if node.y == end[0] and node.x == end[1]:
finalListNeedReverse = []
while node != None:
finalListNeedReverse.append(node)
node = node.parent
finalListNeedReverse.reverse()
return finalListNeedReverse
neighboursList = []
y = node.y
x = node.x
parentDistanceFromOri = node.distanceFromOri
for needNodey in (y + 1, y, y - 1):
if needNodey < 0 or needNodey >= mapSize[0]:
continue
for needNodex in (x + 1, x, x - 1):
if needNodex < 0 or needNodex >= mapSize[1]:
continue
needNode = map[needNodey][needNodex]
if needNode.unable == True or needNode.closed == True or needNode.added == True:
continue
yOffset = needNodey - y
xOffset = needNodex - x
allOffset = yOffset + xOffset
if allOffset == 1 or allOffset == -1:
distanceFromOri = parentDistanceFromOri + 1
else:
distanceFromOri = parentDistanceFromOri + 1.4
if needNode in neighboursList:
# 若新的G值比老的G值低，则更新成老的G值
if distanceFromOri < needNode.distanceFromOri:
needNode.distanceFromOri = distanceFromOri
else:
needNode.distanceFromOri = distanceFromOri
neighboursList.append(needNode)
for needNode in neighboursList:
needNode.parent = node
# 更新F值
needNode.allDistance = needNode.distanceFromOri + needNode.distanceFromDes
needNode.added = True
openedList.append(needNode)
openedList.sort(key=lambda x: x.allDistance)
return None
第4关：搜索算法应用 - 四皇后问题
def make(mark):
'''
标记皇后的位置，例如mark[0] = 2, 表示第1行皇后放在第3列的位置
:param mark: 皇后的位置信息
:return: 拼接好的结果
'''
#初始化数组
r = [['X' for _ in range(len(mark))] for _ in range(len(mark))]
#将每一行中皇后的位置用‘Q’代替
for i in mark:
r[i][mark[i]] = 'Q'
#枚举，将原来散的元素连接成字符串
for k, v in enumerate(r):
r[k] = ''.join(v)
return r
def FourQueens(mark, cur, ret):
'''
深度优先搜索的方式求解四皇后问题
:param mark:表示皇后的位置信息，例如[0,1,3,2]表示棋盘的第1行第1列，第2行第2列，第3行第4列，第4行第3列放置了皇后。例如[1, None, None, None]表示第1行第2列放置了皇后，其他行没有放置皇后。初始值为[None,None,None,None]
:param cur:表示当前准备在第几行放置皇后，例如`cur=1`时，表示准备在第`2`行放置皇后。初始值为0
:param ret:表示存放皇后摆放结果的列表，类型为列表。初始值为[]
:return:无
'''
if cur == len(mark):
#********* Begin *********#
# 如果当前行是最后一行，记录一个解，并返回结束此次搜索
ret.append(make(mark))
return
#********* End *********#
#试探处理，将当前行的皇后应该在的位置遍历每一列，如果满足条件，递归调用处理下一行
for i in range(len(mark)):
mark[cur], down = i, True
for j in range(cur):
# 当想在当前位置放皇后会与其他皇后冲突时不放置皇后
if mark[j] == i or abs(i-mark[j]) == cur - j:
down = False
break
if down:
# 准备在下一行找能放置换后的位置
FourQueens(mark, cur+1, ret)