[AI]A*搜索练习题——禁止数字Forbidden Numbers

A*搜索练习题——禁止数字Forbidden Numbers

题目规则：

• 关于100到999之间的整数
• 一开始会给出两个数字表示初始状态和目标状态
• 给出一个禁止数字的集合，例如{679，666}
• 每次移动只能增加或降低一个数字
• 每次移动不能使用被禁止的数字
• 不允许连续更改数字，例如：667 → \rightarrow → 668 → \rightarrow → 669

求解问题如下：

1. 请描述其状态空间
2. 请指明operator
3. 请寻找出从 I = 567 到 G = 777 的最小序列
4. 禁止数字={666，667}
5. 找到一个好的启发式方法供A*算法使用
6. 画出 A ∗ A^{*} A∗为了解决问题而产生的搜索树
7. 对每个节点的表示：数字(状态), f, g, h和表示展开顺序的整数

答案如下：

1. 描述状态空间如下：
   S = D + × D × D × M S=D^{+} ×D×D×M S=D+×D×D×M
   D^{+} = {1, 2, …, 9}
   D = {0, 1, 2, …, 9}
   M = {no, h, t, u}

Given< N h N_{ℎ} Nh​ , N t N_{t} Nt​, N u N_{u} Nu​ , M> ∈ \in ∈ ????

• N h ∈ D + N_{ℎ} \in D^{+} Nh​∈D+
• N t N_{t} Nt​, N u ∈ D N_{u} \in D Nu​∈D
• {no = no change, h = hundreds, t = tenths, u = units}

Num(< N h N_{ℎ} Nh​ , N t N_{t} Nt​, N u , N_{u}, Nu​, _ >) = 100 × N h + 10 × N t + N u 100×N_{ℎ}+10×N_{t}+N_{u} 100×Nh​+10×Nt​+Nu​

初始状态：< I h , I t , I u , n o I_{ℎ} , I_{t}, I_{u}, no Ih​,It​,Iu​,no>
目标状态：< G h , G t , G u , G_{ℎ} , G_{t}, G_{u}, Gh​,Gt​,Gu​, _>

num(< I h , I t , I u , n o I_{ℎ} , I_{t}, I_{u}, no Ih​,It​,Iu​,no>) = I
num(< G h , G t , G u , G_{ℎ} , G_{t}, G_{u}, Gh​,Gt​,Gu​, _>) = G

2. 指明operator如下：
   
3. 最小序列如下：
   
4. 找到启发式如下：
   
5. A*搜索树如下：