院

系

别

：

数

学

系

专

业

：

信

息

与

计

算

科

学

班

级

：

信

计

0

8

-

1

二

〇一二

年

5

月

人狗鸡米过河问题

一

.

摘要

本文主要对数学建模的基础模型跟“商人过河”类似简 单问题的人

狗鸡米过河问题

，在图论和数学游戏问题中，有不少渡河问题。渡河问

题是在一定的限 制条件下，要求给出最好解，反映在图论中就是求最短路线

问题。对于这类问题，有多种 解决方法，其中

Dijkstra

递推算法是最常用的

方法。

50

年代中期，

由于计算机科学技术迅猛发展，

出现了一门新兴的学科，

叫做“ 人工智能”。人工智能研究的是如何使计算机具有人类的智能，使计

算机像人类那样智能 地工作，去完成那些需要人的智能才可以完成的工作。

从另一个角度来说，人工智能研究 如何使人的智能用计算机来实现。例如，

本题中从初始状态

(1

，

1

，

1

，

1)

到目标状态

(0

，

0

，

0

，

0)

的搜索过程都可以

用人工智能的方法——由计算机来实现。利用人工智能的方法还能证明定理

(

例如，平面几何中的定理

)

。机器证明 定理就是把人证明定理的过程通过一

套符号体系，变成一系列能在计算机上实现的符号运 算过程，从而把人的推

理演绎过程机械化。这对我们所求的问题方便了很多。

关键词：最短路问题

Dijkstra

递推算法

渡河问题

-

-

-

-

-

-

-

-