在虎胆龙威3水壶问题转化为图 [英] Water Jug problem in Die Hard 3 into a graph

问题描述

即时通讯不太清楚如何实现这...

im not too sure how to implement this...

我需要创建一个基于从电影水罐问题的一个加权有向图虎胆龙威3（的 http://www.wikihow.com/Solve-the-Water-Jug-Riddle-from-Die-Hard-3 ）。

I need to create a weighted directed graph based on the water jug problem from the movie Die Hard 3 (http://www.wikihow.com/Solve-the-Water-Jug-Riddle-from-Die-Hard-3).

我需要创建节点的所有可能的行动（补，空，倒）。之后，我需要找到最短路径解决方案。但我必须创建此图的麻烦。我用我自己创建的链接列表/节点。

I need to create nodes for all the possible moves (fill, empty, pour). After i need to find the shortest path to the solution. But i am have trouble creating this graph. I am using my own created linked list/node.

任何帮助的算法来创建此图将是巨大的。谢谢你。

Any help with the algorithm to create this graph would be great. Thanks.

前）接受3加仑，5加仑得到4加仑5加仑的水罐。我需要创建的所有可能的移动到达4加仑的曲线图。每一个不同加仑重presents一个不同的节点。

ex) given 3 gallon, 5 gallon. Get 4 gallons in the 5 gallon jug. I need to create a graph of all the possible moves to get to 4 gallons. Each different gallon represents a different node.

感恩节快乐=）

推荐答案

presumably每个节点保存两个正整数 - 加仑的在3加仑壶号码，加仑在5加仑壶数目。弧，又名边（定向），是动作（并标有动作的弧线再presents） - 显然你也有一位不愿透露姓名自来水方便，因为你可以随时填写无论是壶的;您也可以随时空壶远（所以你也有一个接收器）;等等（其它移动所有涉及移动水从一个加仑到另一个，直到第一个是空的，或第二个是满）。这是毫无疑问，最好避免产生合法的，但没用弧（动作），如加注壶这已经满了，或者撤消你刚才的举动（如清空您刚刚从水龙头填补了壶），虽然将这种电弧只会意味着更多一点的工作，而不是一个不正确的解决方案。

Presumably each node holds two positive integers -- number of gallons in the 3-gal jug, number of gallons in the 5-gal jug. Arcs, aka edges (directed), are the "moves" (and labeled with the action the arc represents) -- apparently you also have an unnamed tap handy, since you can always fill either of the jugs; you can also always empty a jug away (so you also have a sink); and so forth (other moves all involve moving water from one gallon to the other, until either the first one is empty, or the second one is full). It's no doubt better to avoid generating legal but useless arcs ("moves"), such as "filling" a jug that's already full, or undoing a move you just made (such as emptying a jug you just filled from the tap), though adding such arcs will only mean a little more work, not an incorrect solution.

于是开始（0，0） - 这两个水罐满了，因为你已经在开始。显然从这里两个圆弧带你到（3,0）和（0,5）分别（填充的一个或另一个从水龙头），等等。希望这有助于！

So start with (0, 0) -- both jugs full, as you have at the start. Clearly the two arcs from here take you to (3, 0) and (0, 5) respectively (filling one or the other from the tap), and so on. Hope this helps!

这篇关于在虎胆龙威3水壶问题转化为图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！