我对野人过河的问题思考

论文题目

野人过河问题的探索

课程（论文）题目：野人过河问题的探索 本文通过对野人过河问题的探索，运用人工智能知识的表示方法对这个问题进行描述、表示和推理，并且期望找到较为优化的算法。以下共分三个部分对此问题进行探索。 一 问题描述 在河的左岸有3个传教士、1条船和3个野人，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的约束限制：（1）传教士和野人都会划船，但船一次最多只能装运两个；（2）在任何岸边野人数目都不得超过传教士数目，否则传教士就会遭遇危险，被野人攻击甚至被吃掉；（3）此外，假定野人会服从任何一种过河安排，请规划出一个确保全部成员安全过河的计划。 此问题严格的约束是船只能载两人和岸上野人不多于传教士。 二 野人过河问题的知识表示及规则定义 知识表示是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。野人过河问题是一种过程性知识，有多种方法可以表示这个问题，此外野人过河问题推理所用知识和推出的结论都是可以精确表示的，因此它是属于确定性推理范畴的。 下面我用了两种方法对问题进行表示和推理： 1. 谓词逻辑表示 1） 定义谓词及个体域 谓词：AT(nM,mY,L)：n个传教士和m个野人在左岸； AT(nM,mY,R)：n个传教士和m个野人在右岸； Boat(x,y,LR)：将x个传教士和y个野人从左岸运到右岸； Boat(x,y,LR)：将x个传教士和y个野人从右岸运到左岸； 个体域：0≤n≤3，0≤m≤3，0≤x≤2，0≤y≤2，x+y≤2； 初始状态：AT(3M,3Y,L)； 目标状态：AT(3M,3Y,R)； 2） 操作条件和动作： LR(1) 条件：AT(nM,mY,L)，n=m n=m=3 动作：添加表：Boat(1,1,LR)，Boat(0,2,LR); n=m=1 动作：添加表：Boat(1,1,LR); (2) 条件：AT(nM,mY,L)，n>m n=3,m=1 动作：添加表：Boat(2,0,LR); (3) 条件：AT(nM,mY,L)，nm n=3,m=1 动作：添加表：Boat(2,0, RL) ,Boat(0,1, RL); n=3,m=2 动作：添加表：Boat(1,0, RL), Boat(0,1, RL) (3) 条件：AT(nM,mY,R)，n> AT(2M,2Y,L) AT(1M,1Y,R) Boat(1,0,RL) 状态3 =============>> AT(3M,2Y,L) AT(0M,1Y,R) Boat(0,2,LR) 状态4 =============>> AT(3M,0Y,L) AT(0M,3Y,R) Boat(0,1,RL) 状态5 =============>> AT(3M,1Y,L) AT(0M,2Y,R) Boat(2,0,LR) 状态6 =============>> AT(1M,1Y,L) AT(2M,2Y,R) Boat(1,1,RL) 状态7 =============>> AT(2M,2Y,L) AT(1M,1Y,R) Boat(2,0,LR) 状态8 =============>> AT(0M,1Y,L) AT(3M,2Y,R) Boat(0,1,RL) 状态9 =============>> AT(0M,2Y,L) AT(3M,1Y,R) Boat(0,2,LR) 状态10 =============>> AT(0M,0Y,L) AT(3M,3Y,R) 总结：知识表示能力差：只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识，系统效率低。由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，容易发生组合爆炸。 2. 状态空间法 1. 设置状态变量并确定值域 M为传教士人数，Y为野人人数，B为船数，L表示左岸，R表示右岸，要求M>=Y且 (M+Y)B <= 2。 2. 确定状态组，初始状态集和目标状态集 用三元组来表示Sf：（ML , YL , BL）（均为左岸状态）；