我不太确定如何实现这个......
我需要根据电影虎胆龙威 3 (http://www.wikihow.com/Solve-the-Water-Jug-Riddle-from-Die-Hard-3) 中的水壶问题创建一个加权有向图。
我需要为所有可能的移动(填充、清空、倾倒)创建节点。在我需要找到解决方案的最短路径之后。但是我在创建这张图时遇到了麻烦。我正在使用自己创建的链表/节点。
任何有关创建此图的算法的帮助都会很棒。谢谢。
ex) 给定 3 加仑，5 加仑。在 5 加仑的水壶中加入 4 加仑。我需要创建一个图表，包含所有可能的移动以达到 4 加仑。每个不同的加仑代表一个不同的节点。
感恩节快乐 =)
最佳答案
大概每个节点都有两个正整数——3 加仑 jar 中的加仑数，5 加仑 jar 中的加仑数。弧线，又名边缘(定向)，是“移动”(并标有弧线代表的 Action )——显然你手边还有一个未命名的水龙头，因为你总是可以装满其中一个 jar ；你也可以随时清空一个水壶(这样你就有一个水槽)；依此类推(其他 Action 都涉及将水从一加仑移到另一加仑，直到第一个加仑是空的，或者第二个加仑是满的)。毫无疑问，最好避免生成合法但无用的弧线(“移动”)，例如“填充”已经装满的水 jar ，或撤消您刚刚完成的移动(例如清空您刚刚从水龙头中填充的水 jar )，尽管添加这样的圆弧只会意味着更多的工作，而不是不正确的解决方案。
所以从 (0, 0) 开始——两个水 jar 都满了，就像开始时一样。很明显，从这里开始的两条弧分别将您带到 (3, 0) 和 (0, 5)(从水龙头填充一个或另一个)，依此类推。希望这对您有所帮助!
关于algorithm - 虎胆龙威3中的Water Jug问题成图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1806880/