请教一个人工智能的题目：水罐问题

boby2000_0

原题：所谓水罐问题就是：提供给你两个水罐，—个是4公斤水的，一个是装3公斤水的。两个水罐中都没有刻度。只有一个水泵可以给水罐注水，问如何使4公斤的水罐中装有2公斤的水？请用图搜索算法解决水罐问题。
    选择你的启发式估价函数和问题。合法的规则包括；把水泼到地上；把一个水罐的水注入到另一个水罐；用泵给水罐注满水；用一个水罐的水注满另一个水罐。两个水罐的初始状态全是空的。
请画出搜索图，并指出搜索算法是否是可采纳的，及启发函数是否满足单调限制。

shengkz

3装满
3倒进4
3装满
3倒进4，至4满
4倒空
3倒进4

ok，4里面是2

算法么？完全不懂啥叫“图搜索” =0=

shengkz

楼主是问的算法吧。。。汗，偶不是学程序的。我也想知道怎么用程序完成

hdm2968

.........2楼果然厉害......
我也很想知道呀，我曾经用递归，结果还是求不出

trainqzhou

做一个cup[3][4]的数组，每一个元素表示一种状态，如：
初始状态：cup[0][0]
终止状态：cup[0][2], cup[1][2], cup[2][2], cup[3][2]

cup[a] 表示一种状态，就是第一个水罐有a升水，第二个水罐有b升水，我们要做的就是在状态空间cup[3][4]中寻找一条由初始状态到终止状态的最短路径，这个可以用广度优先搜索完成。

比如由初始态cup[0][0]可以到达的是 cup[3][0] (把第一个水罐装满水)和 cup[0][4] (把第二个水罐装满水)^_^

boby2000_0

有启发，感谢

hdm2968

trainqzhou: Re:请教一个人工智能的题目：水罐问题

做一个cup[3][4]的数组，每一个元素表示一种状态，如：
初始状态：cup[0][0]
终止状态：cup[0][2], cup[1...

您这样一说，我明白了一半，这样的搜索过程应该怎样？

shengkz

具体的算法脑子里一团糨糊了 T_T

shengkz

这样算是不是有个缺点，因为只有两种状态是可以确定的，就要么满，要么空，半满的状态是不能直接成立的（看上去却是很复杂）。

trainqzhou

不是的呀，比如cup[1][3]表示的是第一个水罐有1升水，第二个水罐有3升水的状态。搜索的时候和在迷宫中找出口是一样子的，把数组cup成一个3×4的迷宫，就可以用广度优先搜索了。

注意，这里假设水的容量都是整数，事实上根据题目的条件好像也弄不出0.5升水之类的。如果水罐的容量不是整数的话，就要修改一下算法。比如不用cup来表示状态空间，而改为建立一个状态列表，列表中记录的是已经访问过的状态，以防重复记录，从初始状态开始，访问所有可以到达的状态，把访问过的状态记录在状态列表里面，直到（1）找到终止状态（2）遍历了所有的状态但是都没有满足终止状态的，于是此种情况无解！！！