一个简单的人工智能题：用问题归约法求解野人与修道士的
编辑： admin 2017-01-03
-
4
问题归约法从目标(要解决的问题)出发,逆向推理,通过一系列变换把初始问题变换为子问题集合和子子问题集合,直至最后归约为一个平凡的本原问题集合.
已知条件1：最后一次乘船的一定是两人.
已知条件2：往与返的组合不能重复,否则没有意义.
已知条件3：左岸人数除最末次外,不为零.
目标0：
右岸有3个野人3个修道士,船在右.
逆向推理：
最后一次乘船到右岸的组合有以下几种：
1个野人1个修道士；2个野人.
目标-1：
a、左岸1野1修,右岸2野2修,船在左；
b、左岸2野,右岸1野3修,船在左.
逆向推理：
a、左岸1野,1修驶向左岸,右岸2野2修；
b、左岸1野,1野驶向左岸,右岸1野3修.
目标-2：
左岸1野,右岸2野3修,船在右.
逆向推理：
c、左岸1野,1修驶向右岸,右岸2野2修；
d、左岸1野,1野驶向右岸,右岸1野3修；
e、左岸1野,2野驶向右岸,右岸3修.
目标-3：
左岸3野,右岸3修,船在左.
逆向推理：
f、左岸1野,2野驶向左岸,右岸3修；
g、左岸2野,1野驶向左岸,右岸3修.
目标-4：
左岸2野,右岸1野3修,船在右.
逆向推理：
h、左岸2野,1野驶向右岸,右岸3修；
i、左岸2野,2修驶向右岸,右岸1野1修.
目标-5：
左岸2野2修,右岸1野1修,船在左.
逆向推理：
j、左岸2野,2修驶向左岸,右岸1野1修；
k、左岸1野1修,1野1修驶向左岸,右岸1野1修.
目标-6：
左岸1野1修,右岸2野2修,船在右.（与目标-5对称）
逆向推理：
l、左岸1野1修,2修驶向右岸,右岸2野.
目标-7：
左岸1野3修,右岸2野,船在左.（与目标-4对称）
逆向推理：
m、左岸3修,1野驶向左岸,右岸2野.
目标-8：
左岸3修,右岸3野,船在右.（与目标-3对称）
逆向推理：
n、左岸3修,2野驶向右岸,右岸1野.
目标-9：
左岸3修2野,右岸1野,船在左.（与目标-2对称）
逆向推理：
左岸3修1野,1野驶向左岸,右岸1野.
目标-10：
左岸3修1野,右岸2野,船在右.
逆向推理：
左岸3修1野,2野驶向右岸,右岸无人.
达到期望的初始状态^^
结论：
1、2野向右：结果左3修1野,右2野,船在右.（目标-10）
2、1野向左：结果左3修2野,右1野,船在左.（目标-9）
3、2野向右：结果左3修,右3野,船在右.（目标-8）
4、1野向左：结果左3修1野,右2野,船在左.（目标-7）
5、2修向右：结果左1修1野,有2修2野,船在右.（目标-6）
6、1修1野向左：结果左2修2野,右1修1野,船在左.（目标-5）
7、2修向右：结果左2野,右3修1野,船在右.（目标-4）
8、1野向左：结果左3野,右3修,船在左.（目标-3）
9、2野向右：结果左1野,右2野3修,船在右.（目标-2）
10、1野向左：结果左2野,右1野3修,船在左.
或1修向左：结果左1野1修,右2野2修,船在左.（目标-1）
11、2野向右,或1修1野向右,达到目的.
类似问题
类似问题1：在河的左岸有三个修道士,三个野人和一条船,修道士想用这条船把所有的人都运到河对岸,但要受到以下条件限制：修道士都会划船,但船一次只能装运两个人.在任何岸边,野人数不能超过修道[数学科目]
1.修道士A划船,运野人甲过河
修道士A划船回.
2.修道士A划船,运修道士B过河
修道士A划船回.同时将野人甲带回.
3.修道士A划船,运修道士C过河
修道士A划船回.
4.修道士A划船,运野人甲过河
修道士A划船回.
5.修道士A划船,运野人乙过河
修道士A划船回.
6.修道士A划船,运野人丙过河
类似问题2：怎样制作AI人工智能不用太麻烦的需要高级配置的那种TuT就比如制作一个普通的聊天机器人之类的.
一个普通聊天机器人需要大量语言训练.有两种做法,（对于中文）传统的是对一段文字进行分词,然后进行主谓宾分析,接着通过数据库中有的句型模式进行匹配,取得匹配高的几个,查找对应回答句型并根据原有文本联想填词.现代一般通过大规模语料训练,现成一个大的概率表,再得到回答映射概率表,最后自动完成聊天.对于小黄鸡之类的程序,是根据传统ALICE程序对句式学习的产物.
流程：
语料－－－分词（中科院ICTCLAS库）－－－语法分析／概率分析（聚类,N－gram）－－－句型模式匹配（模板匹配）／隐马可夫链,神经网络－－－概率分析（N－gram）／句型选用－－－句子生成
例子：
今天去哪吃饭啊?－－－今天／去／哪／吃饭／啊／?－－－去：去,到,在；吃饭：吃,用餐；今天：（时间）；啊：（语气助词）；哪：（疑问）－－－匹配语料：到哪里吃?外婆家／去什么地方吃饭?就在楼下小饭店吧／在哪吃饭呢?我们去学校食堂吧／中午去哪里用餐?不知道啊.－－－哪里》外婆家；什么地方》楼下／小饭店；哪》学校／食堂；哪》不／知道；聚类后：外婆家,小饭店,食堂是吃饭的地方,不知道是另一种回答－－－系统需要根据上下文语境变量识别,比如上文出现了某地方A－－－去A－－－加工美化：我们去A吃饭吧.