Задача Water Jug в Die Hard 3 в граф - PullRequest
3 голосов
/ 27 ноября 2009

Я не слишком уверен, как это реализовать ...

Мне нужно создать взвешенный ориентированный граф, основанный на проблеме кувшина с водой из фильма Die Hard 3 (http://www.wikihow.com/Solve-the-Water-Jug-Riddle-from-Die-Hard-3).

Мне нужно создать узлы для всех возможных ходов (заполнить, очистить, залить). После того, как мне нужно найти кратчайший путь к решению. Но у меня проблемы с созданием этого графика. Я использую свой собственный созданный связанный список / узел.

Любая помощь с алгоритмом для создания этого графа будет отличной. Спасибо.

ex) дано 3 галлона, 5 галлонов. Получите 4 галлона в кувшине на 5 галлонов. Мне нужно создать график всех возможных ходов, чтобы добраться до 4 галлонов. Каждый галлон представляет отдельный узел.

С Днем Благодарения =)

Ответы [ 2 ]

3 голосов
/ 27 ноября 2009

Предположительно, каждый узел содержит два положительных целых числа - количество галлонов в кувшине по 3 галлона, количество галлонов в кувшине по 5 галлонов. Дуги, иначе называемые ребрами (направленными), являются «ходами» (и помечены действием, которое представляет дуга) - очевидно, у вас также есть под рукой безымянное нажатие, поскольку вы всегда можете заполнить любой из кувшинов; вы также всегда можете опорожнить кувшин (так что у вас есть раковина) и так далее (все другие движения включают в себя перемещение воды из одного галлона в другой, пока либо первый не опустеет, либо второй не наполнится). Без сомнения, лучше избегать создания легальных, но бесполезных дуг («ходов»), таких как «заполнение» уже заполненного кувшина или отмена только что сделанного вами шага (например, опустошение кувшина, который вы только что наполнили из-под крана) добавление таких дуг будет означать лишь немного больше работы, а не неправильное решение.

Итак, начните с (0, 0) - оба кувшина заполнены, как у вас в начале. Очевидно, что две дуги отсюда приведут вас к (3, 0) и (0, 5) соответственно (заполняя одну или другую из крана) и так далее. Надеюсь, это поможет!

2 голосов
/ 28 ноября 2009

На каждом шаге у вас есть 6 различных вариантов

1.О = полная
2 = полный
3.A-> B
4.B-> A
5.A = 0
6 = 0

И вот, пожалуйста. Положите состояния в таблицу поиска и убедитесь, что ни одно из решений не повторится. Это также условие остановки.

размер таблицы поиска - A * B, а вычисление хеша - просто A * vol (B) + B

В таблице [A * vol (B) + B] сохранить с позиции ведьмы, с которой вы пришли. Выполните инициализацию элементов таблицы на -1 (я полагаю, что первый индекс равен 0 на вашем языке)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...