3.5 有一农夫带一条狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件的限制：
（1）船太小，农夫每次只能带一样东西过河；
（2）如果没有农夫看管，则狼要吃羊，羊要吃菜。
请设计一个过河方案，使得狼、羊、菜都能不受损失地过河，画出相应的状态空间图。
提示：（1）用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。
解：初始状态：农夫、狼、羊、菜 都在左岸（0，0，0，0）
目标状态：农夫、狼、羊、菜 都在右岸（1，1，1，1）
迁移模型：（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）（ 1 1 1 1 ）或（0 0 0 0）（1 0 1 0） （0 0 1 0）（1 1 1 0）（0 1 0 0）（1 1 0 1）（0 1 0 1）（ 1 1 1 1 ）
3.8五个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其他各城一次且仅一次，最后回到A城，请找出一条最优线路。
解：初始状态：A城
目标状态：A城
迁移模型：采用穷举法：
A—>B—>C—>D—>E—>A 路径为：41
A—>B—>C—>E—>D—>A 路径为：44
A—>B—>D—>E—>C—>A 路径为：41
A—>B—>D—>C—>E—>A 路径为：44
A—>B—>E—>D—>C—>A 路径为：30
A—>B—>E—>C—>D—>A 路径为：36
A—>C—>D—>B—>E—>A 路径为：34
A—>C—>D—>E—>B—>A 路径为：30
A—>C—>B—>D—>E—>A 路径为：42
A—>C—>B—>E—>D—>A 路径为：34
A—>C—>E—>D—>B—>A 路径为：41
A—>C—>E—>B—>D—>A 路径为：47
A—>D—>B—>E—>C—>A 路径为：48
A—>D—>B—>C—>E—>A 路径为：37
A—>D—>C—>B—>E—>A 路径为：37
A—>D—>C—>E—>B—>A 路径为：37
A—>D—>E—>C—>B—>A 路径为：44
A—>D—>E—>B—>C—>A 路径为：34
A—>E—>B—>C—>D—>A 路径为：37
A—>E—>B—>D—>C—>A 路径为：34
A—>E—>C—>B—>D—>A 路径为：48
A—>E—>C—>D—>B—>A 路径为：44
A—>E—>D—>B—>C—>A 路径为：42
A—>E—>D—>C—>B—>A 路径为：41
最优线路：A—>B—>E—>D—>C—>A 路径为：30 或 A—>C—>D—>E—>B—>A 路径为：30
原文：http://www.cnblogs.com/tangguoheli/p/4363622.html