|
前言一、问题引入二、状态空间法1. 知识及其表示2. 状态空间法定义3. 问题求解
三、基于状态空间搜索法解决八数码问题1. 八数码问题的知识表示2. 状态空间图搜索1. 无信息搜索广度优先搜索(Breadth-First Search)深度优先搜索(Depth-First Search)
2. 启发式搜索Dijkstra（UCS）算法A*算法八数码问题构造启发函数$h(n)$实例欧式距离法曼哈顿距离法
总结
前言
搜索是人工智能里面研究的一个核心问题，个人认为机器学习本质也可以理解为一种搜索。类似强化学习,对抗学习等，都是用了一些值函数近似的方法，其本质都是在搜索参数，也可以理解为一种状态搜索。近些年来也有非常多学术研究者慢慢开始将两者融汇贯通，比如像Goog的planet，Muzero以及将熵用于蒙特卡洛树搜索中平衡探索和利用的关系等。
当然笔者也是初学者，这里给出两篇文章探讨： 机器学习的过程可以理解为一种问题空间搜索的过程吗？ 将应用机器学习转化为求解搜索问题
一、问题引入
我们以《八数码难题》为例,题本身不是很难,但我们可以借助它来理解AI中的搜索策略,尝试从状态空间搜索的角度去理解它的解决方法。
问题描述 ：在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
二、状态空间法
1. 知识及其表示
知识：知识是人们在长期的生活和社会实践中，在科学研究及实验中累积起来的对客观世界的认识与经验。
注意：知识具有相对正确性、不确定性和不完整性，它在一定的条件和环境下正确。知识一定是可表示的，类似于艺术家的手感绘画方式、诗人的即兴作词方式，它大概率是不能用机器语言表示的，也就不能称之为知识。 （e.g. 刮台风大概率会下雨 、今天是火烧云明天是大概率是晴天…诸如此类“经验”我们都认为它是“知识”）
知识表示:知识表示是将人类知识形式化或者模型化,是对各种知识的机器形式语言描述,更通俗易懂的讲也可以理解为一种让计算机可以“接受”的用于描述知识的数据结构(表示方式)。
2. 状态空间法定义
状态空间方法 可形式化为四元组表示： (S,O,S0,G) 其中： S是状态空间，即问题所有可能状态的集合，O是操作算子的集合， S0是初始状态， G是目标状态。
以八数码问题为例,可以基于状态空间法形式化表示为:  状态空间的解：从初始状态 S0 到目标状态 G 的操作算子序列
3. 问题求解
问题求解(problem solving)是人工智能主要应用领域之一，它涉及表示、归约、推断、决策、规划、定理证明和相关过程等核心概念。
问题求解主要包括两个主要的方面 问题的表示：将问题以计算机可理解接受的方式进行描述，即知识表示。例如:利用我们在数据结构学习的图进行机器语言描述，将地图表示为图结构。 
求解的方法：解决问题的办法，如搜索法，归约法，推理法。
问题的类型 • 单状态问题：确定的且可全部观察（八数码） 知道问题的所有状态，从而可以计算出最佳动作序列达到目标状态。 • 多状态问题：确定的且不可全部观察（军棋） 必须通过假定的动作序列和状态来推理以达到目标状态。 • 偶然性问题：不确定的且不可全部观察（股市分析） 必需通过实时反馈来决定执行下一步行动 • 探索性问题：状态空间未知（游戏,王者荣耀,英雄联盟） 通过实时环境感知和探索学习来决定实时执行行动
三、基于状态空间搜索法解决八数码问题
1. 八数码问题的知识表示
状态空间 一个八数码的局面就是一个状态，根据八数码问题定义给出所有可能的局面组成的集合即为状态空间。本问题实际上求解初始状态到目标状态的操作算子序列。
单状态的知识表示 八数码九宫格可以看作一个隐式节点图，只有九个存储数据的格子(节点),没有边的概念。针对本题而言，我们可以采用可以采用1*9的一维数组来存储这个隐式图的数据。在网上有不少利用9位整型数字存储的做法，但这里笔者采用Python列表来存储每一个状态（八个格子）的数据，使用这种存储结构的好处是我们可以很方便的对同类问题（4阶）进行扩展，并且能够在列表中存储空格的操作算子序列。
 操作算子 显然，每一个状态可执行操作有：空格上移、空格下移、空格左移、空格右移，我们需要在我们定义的知识表示方式（数据结构）中实现状态的可执行操作，即我们需要在列表上交换对应位置的值：
 代码实现：（Python多元赋值写法,其中space_index表示空格在列表中的索引）
空格左移：
if space_index % 3 != 0: # 判断空格是否可以向左移动
state[space_index], state[space_index - 1] = state[space_index - 1], state[space_index]
空格右移：
if (space_index + 1) % 3 != 0: # 判断空格是否可以向右移动
state[space_index], state[space_index + 1] = state[space_index + 1], state[space_index]
空格上移：
if space_index - 3 >= 0: # 判断空格是否可以向上移动
state[space_index], state[space_index - 3] = state[space_index - 3], state[space_index]
空格下移：
if space_index + 3 after_cur:
reverse_number += 1
if reverse_number % 2 == 0:
return 0
else:
return 1
# @Function: 判断初始状态到目标状态是否有解
# @Parameter: initial 初始状态数据列表
# purpose 目标状态数据列表
def judge_solvable(initial,purpose):
if initial == purpose:
print("起始状态为目标状态!")
exit(0)
initial_rev_num = calculate_reverse_number(initial)
purpose_rev_num = calculate_reverse_number(purpose)
if initial_rev_num != purpose_rev_num:
print("无法到达!")
exit(0)
# enqueued 字典 用来记录已经入队过的状态
# key表示当前状态,value表示是否入队 1已经入队,0未入队
enqueued = {} # E.G {'123405678':1,'123405687':1}
# 判断当前状态是否已经被访问
def is_visited(state):
state_key = ''.join(state)
# 字典get方法: 在字典中寻找state,找到则返回字典的值,找不到则返回默认值0
if enqueued.get(state_key, 0):
# 已经访问过
return True
else:
# 如果判断为未访问过,下一步要入队,直接在这里更改,提高代码复用性
enqueued[state_key] = 1
return False
# 寻找当前状态的所有下一步所有可行状态,将其加入队列
def find_next_state(state):
global create_point,Open
#找到空格(0)的位置
space_index = state.index('0')
if space_index - 3 >= 0: # 空格向上移动
temp = state.copy()
temp[space_index], temp[space_index - 3] = temp[space_index - 3], temp[space_index]
#未被访问过则入队
if not is_visited(temp[:9]):
temp.append("up")
Open.put(temp)
create_point += 1
if space_index + 3 after_cur:
reverse_number += 1
if reverse_number % 2 == 0:
return 0
else:
return 1
# @Function: 判断初始状态到目标状态是否有解
# @Parameter: initial 初始状态数据列表
# purpose 目标状态数据列表
def judge_solvable(initial,purpose):
if initial == purpose:
print("起始状态为目标状态!")
exit(0)
initial_rev_num = calculate_reverse_number(initial)
purpose_rev_num = calculate_reverse_number(purpose)
if initial_rev_num != purpose_rev_num:
print("无法到达!")
exit(0)
# enqueued 字典 用来记录已经入队过的状态
# key表示当前状态,value表示当前状态的层数
enqueued = {} # E.G {'123405678':5,'123405687':6}
# 判断当前状态是否已经被访问
def is_visited(state):
global max_layers
state_key = ''.join(state[:9])
# 获取当前状态的层数
cur_layer = len(state) - 9
# 字典get方法: 在字典中寻找state,找到则返回字典的值,找不到则返回默认值0
if enqueued.get(state_key, 0):
# 判断当前的层数是否比已经入队的那个状态更低(浅),如果是的话则需要入队
if cur_layer = 0: # 空格向上移动
temp = state.copy()
temp[space_index], temp[space_index - 3] = temp[space_index - 3], temp[space_index]
# 未被访问过则入队,如果是倒数第二层那么就不进行去重
if not is_visited(temp):
temp.append("up")
Open.put(temp)
create_point += 1
if space_index + 3 |