安全渡河问题的图解新法

针对安全渡河这一经典问题,引入图论方法,提出了一种新的图论解法.该方法将顶点设计为由"人"、"狼"、"羊"、"白菜"组成的四元组,元组中的每个元素取值可为"此岸"、"船上"、"彼岸".然后将实际模型转换为图结构,最后通过路径搜索获得问题的解.该方法有利于分析问题域的解空间,获得一般解、随机解和最优解等多种解.该方法体现了从实际模型到理论模型的转变过程,为如何运用图论来解决实际问题提供了方法借鉴.

基于状态机研究安全渡河问题

文章基于状态机来研究两个经典的安全渡河问题。首先,对问题进行细致的分析,归纳出渡河的物质条件和安全要求;接着,根据问题的内涵,精心设计状态的描述参数;然后,基于状态参数,将问题的条件和要求,转换为状态约束表达式、变迁约束表达式,分别用来确定状态图中可能的状态点、可能的变迁边;最后,绘制状态图,将原问题建模为图论问题——求连通图中两顶点之间的最短路径。

格在安全渡河问题图解法中的应用

安全渡河问题是一个经典的逻辑推理问题,可以利用图论的方法,动态规划或整数规划来解决.给出了一种新的基于格的图解算法.相对于已有的安全渡河问题的图解法,方法更具直观性和通用性.