二阶汉诺塔问题
问题描述
设有三根钢针,它们的编号分别是1号、2号和3号。初始情况下,1号钢针上穿有A和B两个金片。A比B小,位于B的上面。要求把这两个金片全部移到另一根钢针上,且每次只能移动一个金片,任何时刻都不能使大片位于小片的上面。
状态空间描述
$S_{1}=\{S_{1A},S_{1B}\}\to S_{3}=\{S_{2A},S_{3B}\}\to S_{4}=\{S_{3A},S_{3B}\}$
农夫过桥问题
问题描述
有一农夫带一条狼、一只羊和一筐菜欲从河的左岸乘船到右岸,但受下列条件限制:
- 船太小,农夫每次只能带一样东西过河;
- 如果没有农夫看管,则狼要吃羊,羊要吃菜。
请设计一个过河方案,使得农夫、狼、羊、菜都能不受损失地过河,画出相应的状态空间图。
状态空间描述
$S_{1}=\{农_{左},狼_{左},羊_{左},菜_{左}\}$
$S_{2}=\{农_{右},狼_{右},羊_{左},菜_{左}\}$
$S_{3}=\{农_{左},狼_{右},羊_{左},菜_{左}\}$
$S_{4}=\{农_{右},狼_{右},羊_{左},菜_{右}\}$
$S_{5}=\{农_{左},狼_{右},羊_{左},菜_{右}\}$
$S_{6}=\{农_{右},狼_{右},羊_{右},菜_{右}\}$