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

【Abstract】 To solve the safe crossing river problem,a new solving method based on graph theory is presented.In this solution,a vertex is designed into a tuple with 4 items,which are "man","wolf","goat",and "cabbage",and each item in the tuple can be assigned the value of "on this shore","on board",or "on other shore".Then the actual model is transformed into graph structures.Finally the solution of the problem is gained by searching out a path on the graph.The solving method is helpful to analyze the solution space of a problem domain and to acquire normal solution,random solution,optimal solution,etc.The solving method shows how to transform an actual problem into a theory model and use graph theory to solve the practical problem.更多还原