第一次作业

3.5解：

按照提示一：S（农夫，狼，羊，菜），0表示在左岸，1表示在右岸。所以初始状态可以表示为S₀（0,0,0,0），目标状态为S₁（1,1,1,1）。

     从S₀到S₁过程为:

方法一： S₀（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)->S₁(1,1,1,1)

方法二： 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

解：所有路径有：

(1)A-B-C-D-E-A，费用=10+8+3+9+11=41.             (13)A-B-C-E-D-A，费用=10+8+8+9+9=44.

(2)A-B-D-C-E-A，费用=10+12+3+8+11=44.           (14)A-B-D-E-C-A，费用=10+12+9+8+2=41.

(3)A-B-E-C-D-A，费用=10+6+8+3+9=36. (15)A-B-E-D-C-A，费用=10+6+9+3+2=30.

(4)A-C-B-D-E-A，费用=2+8+12+9+11=42.              (16)A-C-B-E-D-A，费用=2+8+6+9+9=34.

(5)A-C-D-B-E-A，费用=2+3+12+6+11=34.              (17)A-C-D-E-B-A，费用=2+3+9+6+10=30.

(6)A-C-E-B-D-A，费用=2+8+6+12+9=37.                (18)A-C-E-D-B-A，费用=2+8+9+12+10=41.

(7)A-D-B-C-E-A，费用=9+12+8+8+11=48.              (19)A-D-B-E-C-A，费用=9+12+6+8+2=37.

(8)A-D-C-B-E-A，费用=9+3+8+6+11=37.                (20)A-D-C-E-B-A，费用=9+3+8+6+10=36.

(9)A-D-E-C-B-A，费用=9+9+8+8+10=44.                (21)A-D-E-B-C-A，费用=9+9+6+8+2=34.

(10)A-E-B-C-D-A，费用=11+6+8+3+9=37.              (22)A-E-B-D-C-A，费用=11+6+12+3+2=34.

(11)A-E-C-B-D-A，费用=11+8+8+12+9=48.            (23)A-E-C-D-B-A，费用=11+8+3+12+10=44.

(12)A-E-D-B-C-A，费用=11+9+12+8+2=42.            (24)A-E-D-C-B-A，费用=11+9+3+8+10=41.

可以看出，花费最短的是(15)A-B-E-D-C-A，(17)A-C-D-E-B-A，它们费用相同=30.

第一次作业

原文：http://www.cnblogs.com/wangtao1/p/4358126.html