Недавно я наткнулся на очень интересную загадку, которая уходит корнями в глубокую древность и которую можно решить с помощью известных алгоритмов из области теории графов, таких как, например, поиск в ширину. В этом посте я описываю способ, которым я пытался решить эту проблему.
Проблема
Представьте, что в вашем распоряжении две банки A и B.
В кувшине A может храниться не более литра воды.
В банку B можно поместить максимум b литров воды.
Первоначально оба кувшина пусты.
Любая из следующих операций называется «шагом»:
- Опустошите один из кувшинов;
- Заполните один из кувшинов полностью;
- Переливайте воду из одного кувшина в другой без потерь, пока один из кувшинов не станет полным или пустым.
Исходные данные для решения задачи:
- a (целое положительное число, представляющее емкость кувшина A);
- b (целое положительное число, обозначающее вместимость банки B);
- c (любое целое положительное число).
Задача состоит в том, чтобы определить минимальное количество шагов для получения ровно c литров воды в любом из двух кувшинов, или ответить -1, если это невозможно.
Несколько бесполезных, но любопытных наблюдений
Есть некоторые факты, которые подразумеваются в проблеме, потому что они не имеют прямого отношения к решению, но я посчитал уместным хотя бы упомянуть их.
Во-первых, мы должны предположить, что существует некий бесконечный источник воды — река, бассейн, кран, водопад, струя, ручей, качимба или водопад, — из которого мы можем наполнять кувшины столько раз, сколько посчитаем нужным. Аналогично, существует также бесконечное хранилище, в которое мы можем наливать воду всякий раз, когда хотим опорожнить один из кувшинов.
Обратите внимание, что, скорее всего, мы имеем дело с кувшинами неправильной формы, на которых нет маркировки, указывающей на объем (в отличие, например, от мензурки), поэтому мы можем измерить только два объема: когда кувшин пуст — 0 литров — или когда кувшин полон — a или b литров. Обратите внимание, что любые другие показатели объема, кроме этих двух, были получены путем последовательного выполнения 3 основных разрешенных операций: опорожнения, заполнения или переливания из одной банки в другую.
Но все это не имеет значения для решения проблемы. Итак, давайте двигаться дальше.
Определение переменных
Чтобы лучше справиться с этой проблемой, удобно определить некоторые переменные:
x -> количество воды, существующее в A;
y -> количество воды в B;
w -> количество воды, оставшееся для заполнения A;
z -> количество воды, оставшейся для заполнения B;
Некоторые примеры
Рассмотрим несколько примеров с переменными x и y, обозначающими количество литров воды, хранящихся в кувшинах a и b в данный момент времени соответственно.
Пример 1
Для входов a=3, b=5 и c=4, мы имеем, что ответ равен 6 шагам, потому что, начиная с обоих пустых кувшинов (x=0, y=0), мы можем выполнить следующую последовательность операций:
- Заполните банку B (x=0, y=5);
- Передача из B в A (x=3, y=2);
- Пустой кувшин A (x=0, y=2);
- Передача из B в A (x=2, y=0);
- Заполните кувшин B (x=2, y=5);
- Передача из B в A (x=3, y=4);
Пример 2
Для входов a=8, b=56 и c=46 ответ равен -1, потому что невозможно достичь конфигурации, в которой один из стаканов вмещает 46 литров воды.
Видеть проблему в виде графика
Когда мы наблюдаем пример 2, сразу же возникает вопрос: как можно было узнать, что для этих входных значений не существует последовательности операций, которая заставит меня получить указанные c литров воды в любом из стаканов.
Очевидно, что есть случаи, когда этот ответ является немедленным. Для исходных данных a=3, b=5 и c=100 более чем достоверно известно, что ни один из кувшинов A и B не может содержать 100 литров воды в какой-то момент времени. Но для нетривиальных случаев этот ответ может быть не столь однозначным.
Ключевым моментом здесь является представление этой проблемы в виде графа, где вершины графа — это состояния проблемы, а ребра представляют собой возможности перехода из одного состояния в другое посредством операций, которые разрешено выполнять с кувшинами.
Другими словами, государство — это как фотография, показывающая количество воды, содержащейся в двух кувшинах в любой момент времени. Итак, мы можем представить состояние как упорядоченную пару (x,y) — обратите внимание, что мы говорим о направленном графе — подчиняясь принятому ранее соглашению о переменных.
Таким образом, для общего состояния (x,y) мы имеем следующие наборы соседей
Обратите внимание, что случаи переливания воды из одной банки в другую опущены, поскольку эти состояния требуют предварительной проверки, чтобы знать, приведет ли данное переливание к тому, что одна из банок окажется пустой или полной. Приведенная ниже легенда иллюстрирует, что следует делать в таких ситуациях
Решение с помощью поиска по ширине
Основная идея алгоритма поиска по ширине заключается в следующем:
- Начните с начальной вершины графа, которая в нашем случае будет состоянием (0,0), в котором обе банки пусты;
- Посетите всех соседей этой начальной вершины;
- По мере посещения соседей, сохраняйте их в структуре данных, похожей на очередь.
- Когда посещение соседа завершено, снимите элемент q с очереди;
- Повторяйте процесс посещения соседей для этой вершины q до тех пор, пока состояние не станет (c,y) или (x,c).
Гарантия того, что решение, которое будет найдено (если оно существует), будет иметь минимальное количество шагов, дается тем простым фактом, что мы используем очередь. Таким образом, мы делаем посещение, организованное по уровням, так, что ни одно состояние, находящееся на расстоянии k+1 от состояния (0,0), не будет посещено до того, как будут посещены все состояния, находящиеся на расстоянии k. Поэтому, как только мы найдем решение, оно обязательно будет тем, которое ближе к начальному состоянию, чем другие возможные решения.
Кроме того, правомерно сказать, что, если решения не существует, мы будем проходить через все пространство состояний, достижимых через (0,0), пока наша очередь не опустеет, и в конце ответим -1.
Исходный код
Моя реализация решения этой проблемы на языке C приведена ниже. Хотя переменные a,b и c в коде фиксированы, реализация была общей и адаптируемой для любых входных значений меньше 4000.
Пример вывода для значений a = 3, b = 5 и c = 4.
#include<stdio.h>
#include <stdlib.h>
int a = 3, b = 5, c = 4;
typedef struct State {
int x;
int y;
int distance;
struct State *pred;
struct State *next;
} state;
state *head, *tail;
int visited[4000][4000];
int queue_size;
void *initQueue() {
head = (state *) malloc(sizeof(state));
head->next = NULL;
queue_size = 0;
}
void insert(state *s) {
if (queue_size == 0) {
s->next = NULL;
head = s;
} else if (queue_size == 1) {
tail = s;
head->next = tail;
} else {
s->next = NULL;
tail->next = s;
tail = s;
}
queue_size++;
}
state *dequeue() {
state *removed;
if (queue_size == 0) {
return NULL;
} else if (queue_size == 1) {
removed = head;
head = NULL;
queue_size--;
return removed;
} else {
removed = head;
head = head->next;
queue_size--;
return removed;
}
}
state *getNeighbors(state s) {
state *neighbors = malloc(sizeof(state)*6);
state n;
n = s;
n.distance = s.distance + 1;
n.x = 0;
neighbors[0] = n; // Esvaziar vaso A
n = s;
n.distance = s.distance + 1;
n.y = 0;
neighbors[1] = n; // Esvaziar vaso B
n = s;
n.distance = s.distance + 1;
n.x = a;
neighbors[2] = n; // Encher vaso A
n = s;
n.distance = s.distance + 1;
n.y = b;
neighbors[3] = n; //Encher vaso B
n = s;
n.distance = s.distance + 1;
if (s.x >= (b-s.y)) {
n.x = s.x - (b-s.y);
n.y = b;
} else {
n.x = 0;
n.y = s.y + s.x;
}
neighbors[4] = n; // Transferir de A para B
n = s;
n.distance = s.distance + 1;
if (s.y >= (a-s.x)) {
n.x = a;
n.y = (s.y-(a-s.x));
} else {
n.x = s.x + s.y;
n.y = 0;
}
neighbors[5] = n; // Trasnferir de B para A
return neighbors;
}
void printSolution(state s) {
int size = s.distance;
state solution[size];
while(s.x!=0 || s.y!=0) {
solution[s.distance-1] = s;
s = *s.pred;
}
printf("(0 , 0)n");
for(int i=0; i<size; i++) {
printf("(%d , %d)n", solution[i].x, solution[i].y);
}
}
int bfs(state initial) {
state *n, *current;
initQueue();
insert(&initial);
while(queue_size != 0) {
current = dequeue();
visited[current->x][current->y] = 1;
n = getNeighbors(*current);
for(int i=0; i<6; i++) {
if (!visited[n[i].x][n[i].y]) {
visited[n[i].x][n[i].y] = 1;
n[i].pred = current;
insert(&n[i]);
if (n[i].x==c || n[i].y==c) {
printSolution(n[i]);
return n[i].distance;
}
}
}
}
return -1;
}
int main() {
state inicio = {0,0,0};
int answer = bfs(inicio);
printf("Numero minimo de passos: %dn", answer);
return 0;
}