c语言吧 关注：798,792贴子：4,349,811
- 8回复贴，共1页
希腊奶
宁愿去写猪国杀
这个问题应该挺复杂的，我还搜到了一些论文：https://www.researchgate.net/publication/362382806_Analysis_of_A_Algorithm_Optimization_and_Breadth_First_Search_in_the_Water_Teapot_Game。
有个简单的思路是把问题抽象成图的最短路径问题。每个节点是四元组(a,b,c,d)表示四个杯子的状态，要求起始节点到目的节点的最短路径。
可以使用BFS，每一次遍历结果存入哈希表中,第二次遍历到相同节点时，如果步数小于第一次，则继续遍历，否则剪枝，当有一个到达终点的步数，任何大于等于这个步数的遍历可以剪枝，直到遍历结束.
有个简单的思路是把问题抽象成图的最短路径问题。每个节点是四元组(a,b,c,d)表示四个杯子的状态，要求起始节点到目的节点的最短路径。
可以使用BFS，每一次遍历结果存入哈希表中,第二次遍历到相同节点时，如果步数小于第一次，则继续遍历，否则剪枝，当有一个到达终点的步数，任何大于等于这个步数的遍历可以剪枝，直到遍历结束.
