如何将三杯浇注拼图建模为图形
How to model the three-glass pouring puzzle as a graph
我想用图表模拟以下拼图。
The barman gives you three
glasses whose sizes are 1000ml, 700ml, and 400ml, respectively. The 700ml and 400ml glasses start
out full of beer, but the 1000ml glass is initially empty. You can get unlimited free beer if you win
the following game:
Game rule: You can keep pouring beer from one glass into another, stopping only when the source
glass is empty or the destination glass is full. You win if there is a sequence of pourings that leaves
exactly 200ml in the 700ml or 400 ml glass.
我有点不确定如何在图表中翻译这个问题。我的想法是，玻璃杯将由加权的无向图中的节点表示，其中边表示可以将玻璃杯 u 倒入玻璃杯 v 中，其他方式相同，因此步行将是导致正确解决方案的一系列倾倒。
但是，这种具有三个单节点和无向边的方法对于 Dijkstra 算法或其他贪婪算法不太适用，而我将使用这些算法来解决问题。将浇注的排列建模为图表是否更合适？
您应该将整个状态存储为顶点。我的意思是，每个玻璃杯中的值都是状态的一个组成部分，因此状态是 glassesCount 数字的数组。例如，初始状态为 (700,400,0).
之后你应该将初始状态添加到队列和运行 BFS。 BFS 适用，因为每条边的权重 =1。权重是相等的，因为权重是每个状态之间的倾倒次数，显然 = 1，因为我们只从队列中的每个状态生成可达状态。
您也可以使用 DFS，但 BFS returns 是最短的倾倒序列，因为 BFS 给出了 1 加权图的最短路径。如果您对最短浇注顺序不感兴趣，但对任何解决方案感兴趣，DFS 都可以。我将描述 BFS，因为它具有与 DFS 相同的复杂性和 returns 更好（更短）的解决方案。
在 BFS 的每个状态中，您必须通过从所有成对组合中倾倒来生成所有可能的新状态。另外，你应该检查倾倒的可能性。
对于 3 副眼镜，每个州有 3*(3-1)=6 个可能的分支，但我实现了更通用的解决方案，允许您将我的代码用于 N 副眼镜。
public class Solution{
static HashSet<State> usedStates = new HashSet<State>();
static HashMap<State,State> prev = new HashMap<State, State>();
static ArrayDeque<State> queue = new ArrayDeque<State>();
static short[] limits = new short[]{700,400,1000};
public static void main(String[] args){
State initialState = new State(new Short[]{700,400,0});
usedStates.add(initialState);
queue.add(initialState);
prev.put(initialState,null);
boolean solutionFound = false;
while(!queue.isEmpty()){
State curState = queue.poll();
if(curState.isWinning()){
printSolution(curState);
solutionFound = true;
break; //stop BFS even if queue is not empty because solution already found
}
// go to all possible states
for(int i=0;i<curState.getGlasses().length;i++)
for(int j=0;j<curState.getGlasses().length;j++) {
if (i != j) { //pouring from i-th glass to j-th glass, can't pour to itself
short glassI = curState.getGlasses()[i];
short glassJ = curState.getGlasses()[j];
short possibleToPour = (short)(limits[j]-glassJ);
short amountToPour;
if(glassI<possibleToPour) amountToPour = glassI; //pour total i-th glass
else amountToPour = possibleToPour; //pour i-th glass partially
if(glassI!=0){ //prepare new state
Short[] newGlasses = Arrays.copyOf(curState.getGlasses(), curState.getGlasses().length);
newGlasses[i] = (short)(glassI-amountToPour);
newGlasses[j] = (short)(newGlasses[j]+amountToPour);
State newState = new State(newGlasses);
if(!usedStates.contains(newState)){ // if new state not handled before mark it as used and add to queue for future handling
usedStates.add(newState);
prev.put(newState, curState);
queue.add(newState);
}
}
}
}
}
if(!solutionFound) System.out.println("Solution does not exist");
}
private static void printSolution(State curState) {
System.out.println("below is 'reversed' solution. In order to get solution from initial state read states from the end");
while(curState!=null){
System.out.println("("+curState.getGlasses()[0]+","+curState.getGlasses()[1]+","+curState.getGlasses()[2]+")");
curState = prev.get(curState);
}
}
static class State{
private Short[] glasses;
public State(Short[] glasses){
this.glasses = glasses;
}
public boolean isWinning() {
return glasses[0]==200 || glasses[1]==200;
}
public Short[] getGlasses(){
return glasses;
}
@Override
public boolean equals(Object other){
return Arrays.equals(glasses,((State)other).getGlasses());
}
@Override
public int hashCode(){
return Arrays.hashCode(glasses);
}
}
}
输出：
below is 'reversed' solution. In order to get solution from initial
state read states from the end
(700,200,200)
(500,400,200)
(500,0,600)
(100,400,600)
(100,0,1000)
(700,0,400)
(700,400,0)
有趣的事实 - 如果替换
，此问题无解
200ml in g1 OR g2
到
200ml in g1 AND g2
.
我的意思是，无法从 (700,400,0) 到达状态 (200,200,700)
如果我们想用图表来模拟这个问题，每个节点应该代表啤酒量到眼镜的可能分配。假设我们用这样的对象表示每个玻璃杯：
{ volume: <current volume>, max: <maximum volume> }
那么起始节点就是三个这样的对象的列表：
[ { volume: 0, max: 1000 }, { volume: 700, max: 700 }, { volume: 400, max: 400 } ]
边缘表示将一个玻璃杯倒入另一个玻璃杯中的动作。为了执行这样的操作，我们选择一个源玻璃和一个目标玻璃，然后计算我们可以从源向目标倒多少：
function pour(indexA, indexB, glasses) { // Pour from A to B.
var a = glasses[indexA],
b = glasses[indexB],
delta = Math.min(a.volume, b.max - b.volume);
a.volume -= delta;
b.volume += delta;
}
从起始节点开始，我们尝试从每个玻璃杯倒入其他每个玻璃杯。这些操作中的每一个都会导致新的啤酒量分配。我们检查每一个，看看我们是否达到了 200 的目标数量。如果没有，我们将任务推入队列。
为了找到从起始节点到目标节点的最短路径，我们将新发现的节点推到队列的头部，并从队列的末尾弹出节点。这确保了当我们到达目标节点时，它离起始节点的距离不会比队列中的任何其他节点更远。
为了能够重建最短路径，我们将每个节点的前导存储在字典中。我们可以使用同一个字典来确保我们不会多次探索一个节点。
以下是此方法的 JavaScript 实现。点击下方蓝色按钮运行即可。
function pour(indexA, indexB, glasses) { // Pour from A to B.
var a = glasses[indexA],
b = glasses[indexB],
delta = Math.min(a.volume, b.max - b.volume);
a.volume -= delta;
b.volume += delta;
}
function glassesToKey(glasses) {
return JSON.stringify(glasses);
}
function keyToGlasses(key) {
return JSON.parse(key);
}
function print(s) {
s = s || '';
document.write(s + '<br />');
}
function displayKey(key) {
var glasses = keyToGlasses(key);
parts = glasses.map(function (glass) {
return glass.volume + '/' + glass.max;
});
print('volumes: ' + parts.join(', '));
}
var startGlasses = [ { volume: 0, max: 1000 },
{ volume: 700, max: 700 },
{ volume: 400, max: 400 } ];
var startKey = glassesToKey(startGlasses);
function solve(targetVolume) {
var actions = {},
queue = [ startKey ],
tail = 0;
while (tail < queue.length) {
var key = queue[tail++]; // Pop from tail.
for (var i = 0; i < startGlasses.length; ++i) { // Pick source.
for (var j = 0; j < startGlasses.length; ++j) { // Pick target.
if (i != j) {
var glasses = keyToGlasses(key);
pour(i, j, glasses);
var nextKey = glassesToKey(glasses);
if (actions[nextKey] !== undefined) {
continue;
}
actions[nextKey] = { key: key, source: i, target: j };
for (var k = 1; k < glasses.length; ++k) {
if (glasses[k].volume === targetVolume) { // Are we done?
var path = [ actions[nextKey] ];
while (key != startKey) { // Backtrack.
var action = actions[key];
path.push(action);
key = action.key;
}
path.reverse();
path.forEach(function (action) { // Display path.
displayKey(action.key);
print('pour from glass ' + (action.source + 1) +
' to glass ' + (action.target + 1));
print();
});
displayKey(nextKey);
return;
}
queue.push(nextKey);
}
}
}
}
}
}
solve(200);
body {
font-family: monospace;
}
在给出了上面两个独立的暴力解决方案之后，我产生了展示约束规划的优雅的想法。它实际上并没有回答 OP 的问题，只是解决了这个难题。诚然，我预计它会更短。
par int:N = 7; % only an alcoholic would try more than 7 moves
var 1..N: n; % the sequence of states is clearly at least length 1. ie the start state
int:X = 10; % capacities
int:Y = 7;
int:Z = 4;
int:T = Y + Z;
array[0..N] of var 0..X: x; % the amount of liquid in glass X the biggest
array[0..N] of var 0..Y: y;
array[0..N] of var 0..Z: z;
constraint x[0] = 0; % initial contents
constraint y[0] = 7;
constraint z[0] = 4;
% the total amount of liquid is the same as the initial amount at all times
constraint forall(i in 0..n)(x[i] + y[i] + z[i] = T);
% we get free unlimited beer if any of these glasses contains 2dl
constraint y[n] = 2 \/ z[n] = 2;
constraint forall(i in 0..n-1)(
% d is the amount we can pour from one glass to another: 6 ways to do it
let {var int: d = min(y[i], X-x[i])} in (x[i+1] = x[i] + d /\ y[i+1] = y[i] - d) \/ % y to x
let {var int: d = min(z[i], X-x[i])} in (x[i+1] = x[i] + d /\ z[i+1] = z[i] - d) \/ % z to x
let {var int: d = min(x[i], Y-y[i])} in (y[i+1] = y[i] + d /\ x[i+1] = x[i] - d) \/ % x to y
let {var int: d = min(z[i], Y-y[i])} in (y[i+1] = y[i] + d /\ z[i+1] = z[i] - d) \/ % z to y
let {var int: d = min(y[i], Z-z[i])} in (z[i+1] = z[i] + d /\ y[i+1] = y[i] - d) \/ % y to z
let {var int: d = min(x[i], Z-z[i])} in (z[i+1] = z[i] + d /\ x[i+1] = x[i] - d) % x to z
);
solve minimize n;
output[show(n), "\n\n", show(x), "\n", show(y), "\n", show(z)];
输出为
[0, 4, 10, 6, 6, 2, 2]
[7, 7, 1, 1, 5, 5, 7]
[4, 0, 0, 4, 0, 4, 2]
幸运的是，这与其他解决方案一致。将其提供给 MiniZinc 解算器并等待......等待。没有循环，没有 BFS 和 DFS。
我想用图表模拟以下拼图。
The barman gives you three glasses whose sizes are 1000ml, 700ml, and 400ml, respectively. The 700ml and 400ml glasses start out full of beer, but the 1000ml glass is initially empty. You can get unlimited free beer if you win the following game: Game rule: You can keep pouring beer from one glass into another, stopping only when the source glass is empty or the destination glass is full. You win if there is a sequence of pourings that leaves exactly 200ml in the 700ml or 400 ml glass.
我有点不确定如何在图表中翻译这个问题。我的想法是，玻璃杯将由加权的无向图中的节点表示，其中边表示可以将玻璃杯 u 倒入玻璃杯 v 中，其他方式相同，因此步行将是导致正确解决方案的一系列倾倒。
但是，这种具有三个单节点和无向边的方法对于 Dijkstra 算法或其他贪婪算法不太适用，而我将使用这些算法来解决问题。将浇注的排列建模为图表是否更合适？
您应该将整个状态存储为顶点。我的意思是，每个玻璃杯中的值都是状态的一个组成部分，因此状态是 glassesCount 数字的数组。例如，初始状态为 (700,400,0).
之后你应该将初始状态添加到队列和运行 BFS。 BFS 适用，因为每条边的权重 =1。权重是相等的，因为权重是每个状态之间的倾倒次数，显然 = 1，因为我们只从队列中的每个状态生成可达状态。
您也可以使用 DFS，但 BFS returns 是最短的倾倒序列，因为 BFS 给出了 1 加权图的最短路径。如果您对最短浇注顺序不感兴趣，但对任何解决方案感兴趣，DFS 都可以。我将描述 BFS，因为它具有与 DFS 相同的复杂性和 returns 更好（更短）的解决方案。
在 BFS 的每个状态中，您必须通过从所有成对组合中倾倒来生成所有可能的新状态。另外，你应该检查倾倒的可能性。
对于 3 副眼镜，每个州有 3*(3-1)=6 个可能的分支，但我实现了更通用的解决方案，允许您将我的代码用于 N 副眼镜。
public class Solution{
static HashSet<State> usedStates = new HashSet<State>();
static HashMap<State,State> prev = new HashMap<State, State>();
static ArrayDeque<State> queue = new ArrayDeque<State>();
static short[] limits = new short[]{700,400,1000};
public static void main(String[] args){
State initialState = new State(new Short[]{700,400,0});
usedStates.add(initialState);
queue.add(initialState);
prev.put(initialState,null);
boolean solutionFound = false;
while(!queue.isEmpty()){
State curState = queue.poll();
if(curState.isWinning()){
printSolution(curState);
solutionFound = true;
break; //stop BFS even if queue is not empty because solution already found
}
// go to all possible states
for(int i=0;i<curState.getGlasses().length;i++)
for(int j=0;j<curState.getGlasses().length;j++) {
if (i != j) { //pouring from i-th glass to j-th glass, can't pour to itself
short glassI = curState.getGlasses()[i];
short glassJ = curState.getGlasses()[j];
short possibleToPour = (short)(limits[j]-glassJ);
short amountToPour;
if(glassI<possibleToPour) amountToPour = glassI; //pour total i-th glass
else amountToPour = possibleToPour; //pour i-th glass partially
if(glassI!=0){ //prepare new state
Short[] newGlasses = Arrays.copyOf(curState.getGlasses(), curState.getGlasses().length);
newGlasses[i] = (short)(glassI-amountToPour);
newGlasses[j] = (short)(newGlasses[j]+amountToPour);
State newState = new State(newGlasses);
if(!usedStates.contains(newState)){ // if new state not handled before mark it as used and add to queue for future handling
usedStates.add(newState);
prev.put(newState, curState);
queue.add(newState);
}
}
}
}
}
if(!solutionFound) System.out.println("Solution does not exist");
}
private static void printSolution(State curState) {
System.out.println("below is 'reversed' solution. In order to get solution from initial state read states from the end");
while(curState!=null){
System.out.println("("+curState.getGlasses()[0]+","+curState.getGlasses()[1]+","+curState.getGlasses()[2]+")");
curState = prev.get(curState);
}
}
static class State{
private Short[] glasses;
public State(Short[] glasses){
this.glasses = glasses;
}
public boolean isWinning() {
return glasses[0]==200 || glasses[1]==200;
}
public Short[] getGlasses(){
return glasses;
}
@Override
public boolean equals(Object other){
return Arrays.equals(glasses,((State)other).getGlasses());
}
@Override
public int hashCode(){
return Arrays.hashCode(glasses);
}
}
}
输出：
below is 'reversed' solution. In order to get solution from initial state read states from the end
(700,200,200)
(500,400,200)
(500,0,600)
(100,400,600)
(100,0,1000)
(700,0,400)
(700,400,0)
有趣的事实 - 如果替换
，此问题无解200ml in g1 OR g2
到
200ml in g1 AND g2
.
我的意思是，无法从 (700,400,0) 到达状态 (200,200,700)
如果我们想用图表来模拟这个问题，每个节点应该代表啤酒量到眼镜的可能分配。假设我们用这样的对象表示每个玻璃杯：
{ volume: <current volume>, max: <maximum volume> }
那么起始节点就是三个这样的对象的列表：
[ { volume: 0, max: 1000 }, { volume: 700, max: 700 }, { volume: 400, max: 400 } ]
边缘表示将一个玻璃杯倒入另一个玻璃杯中的动作。为了执行这样的操作，我们选择一个源玻璃和一个目标玻璃，然后计算我们可以从源向目标倒多少：
function pour(indexA, indexB, glasses) { // Pour from A to B.
var a = glasses[indexA],
b = glasses[indexB],
delta = Math.min(a.volume, b.max - b.volume);
a.volume -= delta;
b.volume += delta;
}
从起始节点开始，我们尝试从每个玻璃杯倒入其他每个玻璃杯。这些操作中的每一个都会导致新的啤酒量分配。我们检查每一个，看看我们是否达到了 200 的目标数量。如果没有，我们将任务推入队列。
为了找到从起始节点到目标节点的最短路径，我们将新发现的节点推到队列的头部，并从队列的末尾弹出节点。这确保了当我们到达目标节点时，它离起始节点的距离不会比队列中的任何其他节点更远。
为了能够重建最短路径，我们将每个节点的前导存储在字典中。我们可以使用同一个字典来确保我们不会多次探索一个节点。
以下是此方法的 JavaScript 实现。点击下方蓝色按钮运行即可。
function pour(indexA, indexB, glasses) { // Pour from A to B.
var a = glasses[indexA],
b = glasses[indexB],
delta = Math.min(a.volume, b.max - b.volume);
a.volume -= delta;
b.volume += delta;
}
function glassesToKey(glasses) {
return JSON.stringify(glasses);
}
function keyToGlasses(key) {
return JSON.parse(key);
}
function print(s) {
s = s || '';
document.write(s + '<br />');
}
function displayKey(key) {
var glasses = keyToGlasses(key);
parts = glasses.map(function (glass) {
return glass.volume + '/' + glass.max;
});
print('volumes: ' + parts.join(', '));
}
var startGlasses = [ { volume: 0, max: 1000 },
{ volume: 700, max: 700 },
{ volume: 400, max: 400 } ];
var startKey = glassesToKey(startGlasses);
function solve(targetVolume) {
var actions = {},
queue = [ startKey ],
tail = 0;
while (tail < queue.length) {
var key = queue[tail++]; // Pop from tail.
for (var i = 0; i < startGlasses.length; ++i) { // Pick source.
for (var j = 0; j < startGlasses.length; ++j) { // Pick target.
if (i != j) {
var glasses = keyToGlasses(key);
pour(i, j, glasses);
var nextKey = glassesToKey(glasses);
if (actions[nextKey] !== undefined) {
continue;
}
actions[nextKey] = { key: key, source: i, target: j };
for (var k = 1; k < glasses.length; ++k) {
if (glasses[k].volume === targetVolume) { // Are we done?
var path = [ actions[nextKey] ];
while (key != startKey) { // Backtrack.
var action = actions[key];
path.push(action);
key = action.key;
}
path.reverse();
path.forEach(function (action) { // Display path.
displayKey(action.key);
print('pour from glass ' + (action.source + 1) +
' to glass ' + (action.target + 1));
print();
});
displayKey(nextKey);
return;
}
queue.push(nextKey);
}
}
}
}
}
}
solve(200);
body {
font-family: monospace;
}
在给出了上面两个独立的暴力解决方案之后，我产生了展示约束规划的优雅的想法。它实际上并没有回答 OP 的问题，只是解决了这个难题。诚然，我预计它会更短。
par int:N = 7; % only an alcoholic would try more than 7 moves
var 1..N: n; % the sequence of states is clearly at least length 1. ie the start state
int:X = 10; % capacities
int:Y = 7;
int:Z = 4;
int:T = Y + Z;
array[0..N] of var 0..X: x; % the amount of liquid in glass X the biggest
array[0..N] of var 0..Y: y;
array[0..N] of var 0..Z: z;
constraint x[0] = 0; % initial contents
constraint y[0] = 7;
constraint z[0] = 4;
% the total amount of liquid is the same as the initial amount at all times
constraint forall(i in 0..n)(x[i] + y[i] + z[i] = T);
% we get free unlimited beer if any of these glasses contains 2dl
constraint y[n] = 2 \/ z[n] = 2;
constraint forall(i in 0..n-1)(
% d is the amount we can pour from one glass to another: 6 ways to do it
let {var int: d = min(y[i], X-x[i])} in (x[i+1] = x[i] + d /\ y[i+1] = y[i] - d) \/ % y to x
let {var int: d = min(z[i], X-x[i])} in (x[i+1] = x[i] + d /\ z[i+1] = z[i] - d) \/ % z to x
let {var int: d = min(x[i], Y-y[i])} in (y[i+1] = y[i] + d /\ x[i+1] = x[i] - d) \/ % x to y
let {var int: d = min(z[i], Y-y[i])} in (y[i+1] = y[i] + d /\ z[i+1] = z[i] - d) \/ % z to y
let {var int: d = min(y[i], Z-z[i])} in (z[i+1] = z[i] + d /\ y[i+1] = y[i] - d) \/ % y to z
let {var int: d = min(x[i], Z-z[i])} in (z[i+1] = z[i] + d /\ x[i+1] = x[i] - d) % x to z
);
solve minimize n;
output[show(n), "\n\n", show(x), "\n", show(y), "\n", show(z)];
输出为
[0, 4, 10, 6, 6, 2, 2]
[7, 7, 1, 1, 5, 5, 7]
[4, 0, 0, 4, 0, 4, 2]
幸运的是，这与其他解决方案一致。将其提供给 MiniZinc 解算器并等待......等待。没有循环，没有 BFS 和 DFS。