·|15-谜问题(问题描述) 种初始排列 目标排列 13415 1234 2 512 5678 761114 9101112 891013 131415 通过一系列合法移动将初始排列转换成目标排列。 合法移动:将邻接于空格的牌移动到空格
15-谜问题（问题描述） 1 3 4 15 2 5 12 7 6 11 14 8 9 10 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 通过一系列合法移动将初始排列转换成目标排列。 合法移动：将邻接于空格的牌移动到空格。 一种初始排列 目标排列
|15谜问题(是否有解) o棋盘存在16!种不同排列 o任一初始状态,可到达的状态为这些 排列中的一半 o在求解问题前,需要判定目标状态是 否在初始状态的状态空间中
15-谜问题（是否有解） 棋盘存在16！种不同排列 任一初始状态，可到达的状态为这些 排列中的一半 在求解问题前，需要判定目标状态是 否在初始状态的状态空间中
|15谜问题(判定方法) o按目标状态给牌编号,空格为16 o用 POSITION(记录编号为的牌在初始状 态中的位置; POSITION(16)表示空格 ●图92(a)的 POSITION (15237109131415118161246) O LESS(〕是使得牌j小于牌且 POSITIoNG) > POSITION()的数目 LEsS(1)=0;LESS(4)=1;LESS(12)=6
15-谜问题（判定方法） 按目标状态给牌编号，空格为16 用POSITION(i)记录编号为i的牌在初始状 态中的位置； POSITION(16)表示空格 ⚫ 图9.2(a)的POSITION ⚫ (1 5 2 3 7 10 9 13 14 15 11 8 16 12 4 6) LESS(i)是使得牌j小于牌i且POSITION(j) > POSITION(i)的数目 ⚫ LESS(1)=0; LESS(4)=1; LESS(12)=6
。15-送间题(判定方法 o定理71当且仅当 sum(LEsS()+Ⅺ)是偶 数时,目标状态可由此 初始状态到达 Ⅹ=1:空格恰好在上 图棋盘中的蓝色格子上 X=0:空格在棋盘中 的白色格子上
15-谜问题（判定方法） 定理7.1 当且仅当 sum(LESS(i) + X)是偶 数时，目标状态可由此 初始状态到达 X＝1：空格恰好在上 图棋盘中的蓝色格子上 X＝0：空格在棋盘中 的白色格子上
15-谜问题宽度优先) 复配】】 gQ斷p 四 上 左 2】 下】【】】[ 】Ed 册 910 6复8 91079 右 左 上 右 左 上 左 【 15 68国dBda62a国目國dd已 ppos山中世[回 下下/\左 左 36 上 23 9 10 711 6□d 910010iomi2 围吗 17 20 标 的国6m[6
15-谜问题(宽度优先)