第一次作业

3.5

解：

S（农夫 狼 羊 菜）初始状态由题可知S₀（0 0 0 0），目标状态S₁(1 1 1 1),

解决方案之一如下：

1)、农夫先将羊带到右岸，然后将羊放到右岸后再一个人回到左岸；

2)、农夫又将菜带到右岸，并将菜放到右岸再把羊带回到左岸放在左岸；

3)、农夫把狼带到右岸，并将狼放到右岸然后再一个人回到左岸；

4)、农夫把羊带到右岸；任务完成；

根据上述进行求解，S₀到S₁的过程为：

S₀(0 0 0 0)->(1 0 1 0)->-(0 0 1 0)->(1 0 1 1)->(0 0 0 1)->(1 1 0 1)->(0 1 0 1)->S₁(1 1 1 1)

3.8

解：

建立树形图，由深度优先搜索算法可知最短优解为：

A-C-D-E-B-A 路径为：2+3+9+6+10=30

A-B-E-D-C-A 路径为：10+6+9+3+2=30