Задача на переливания (сосуды). Оптимизация поиска

Главная Форумы Программирование Помощь с решением задач на Prolog Решение головоломок на Prolog Задача на переливания (сосуды). Оптимизация поиска

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 1 неделя, 3 дн. назад.

  • Автор
    Сообщения
  • #4258

    В этой заметке разберем решение классической логической задачи на переливания (может даваться с разными формулировками, но одной сутью). Задача решается с помощью деревьев поиска решений, при этом у нас возникнет проблема с производительностью, поэтому рассмотрим как можно оптимизировать поиск.

    Задача: даны 2 сосуда, имеющие целочисленные объемы V1 и V2.
    При этом V1 и V2 не имеют общих делителей, отличных от 1.
    Имеется также “безразмерный” пруд, из которого можно черпать воду сосудами,
    и в который можно выливать воду из сосудов. Определить последовательность переливаний,
    необходимую для получения заданного (целочисленного) количества воды в одном из сосудов.

    Подход к решению

    Математически эта задача давно разобрана и доказано, что если V1 и V2 — взаимно-простые числа, то задача имеет решение.

    Общий подход к решению такого рода задач на языке Prolog сводится к обходу пространства состояний задачи в ширину, либо в глубину. Под состоянием в данном случае имеется ввиду пара (Jar1, Jar2), содержащая текущее количество воды в сосудах. При этом, пространство состояний имеет древовидную структуру (можно назвать его деревом поиска решений).

    Итак, у нас есть состояние, по правилам, описанным в условии задачи (правила переливания в данном случае) мы можем получить новые состояния, для каждого из которых процесс может повторяться. Все это выполняется до тех пор, пока очередное состояние не будет соответствовать условию решения задачи. В зависимости от стратегии обхода этого графа мы получим либо первое попавшееся решение (обход в глубину), либо оптимальное по числу шагов (поиск в ширину).

    На языке Prolog (я использую SWI Prolog) это может быть записано следующим образом:

    solve(jar(VolumeA, A), jar(VolumeB, B), target(Target), Actions):-
      bfs(volumes(VolumeA, VolumeB), target(Target), [state(jars(A, B), actions([init]))], Actions).
      
    bfs(_Volumes, target(Target), [state(jars(A, B), Actions)|_Other], Actions):-
      (A = Target; B = Target).
    bfs(Volumes, target(Target), [state(Jars, HeadActions)|Buffer], Actions):-
      generate_states(Volumes, Jars, HeadActions, NextStates),
      append(Buffer, NextStates, NextBuffer),
      bfs(Volumes, target(Target), NextBuffer, Actions).

    Тут solve — функция, которую вызывает пользователь, передавая ей данные задачи (объемы кувшинов, их начальное содержимое и цель, которую надо достичь) для получения результата — набора действий (Actions). Эта функция вызывает функцию поиска в ширину (bsf), передавая ей данные в более для обработки удобном формате, а также начальное состояние. Состояние описывается содержимым кувшинов и набором действий, которые привели к этому: state(jars(A, B), actions([init])). В поиске в ширину состояния выстраиваются в очередь (добавление происходит в один конец, а выбор для обработки — с другого конца), для этого мы используем список, изначально содержащий единственный элемент.

    Функция bfs проверяет не достигнуто ли конечное состояние (не оказалось ли в одном из кувшинов искомое количество литров). Если не достигнуто — выбирается первое состояние очереди и функцией genegate_states (показанной ниже) формируется новый набор состояний, которые добавляются в конец с помощью встроенной функции append. Новая очередь состояний передается на вход bfs рекурсивно.

    Осталось разобрать генерацию состояний, код объемный, но очень простой, поэтому пояснения дам частично. Варианты перехода из текущего состояния опишем недетерминированным предикатом next_state. Недетерминированный — значит возвращает несколько решений, чтобы собрать их всех используем встроенный предикат findall:

    generate_states(Volumes, Jars, actions(PrevActions), NextStates):-
      findall(NextState, 
              next_state(Volumes, Jars, actions(PrevActions), NextState),
              NextStates).

    Собственно next_state описывает все условия переходов, заданные в задаче, приведу его часть:

    next_state(volumes(VolumeA, VolumeB), jars(A, B), actions(PrevActions), NextState):-
      \+ A = 0, % из A можно вылить
      NextState = state(jars(0, B), actions([a_to_pond|PrevActions]));
      
      \+ B = VolumeB, % в B можно зачерпнуть
      NextState = state(jars(A, VolumeB), actions([pond_to_b|PrevActions]));

    Т.е. если A не равно нулю (в первом кувшине что-от есть) — то следующим состоянием может быть такое, где A равно нулю (его содержимое можно вылить). Если B не полный — то его можно долить из пруда (зачерпнуть) и следующим состоянием будет такое, где он полный.

    Оптимизация поиска решения

    Приведенный выше код будет замечательно работать, но … долго (в некоторых случаях решения можно ждать вечно — оно зацикливается). Проблема в том, что хоть мы и частично оптимизировали решений (описав более сложные правила, не позволяющие вылить из пустого кувшина), но все равно будут рассматриваться многократно повторяющиеся действия:

    вылить-налить-вылить-вылить …

    приводящие к уже рассмотренным состояниям, например:

    (0,7) → (0,0) → (0,7) → …

    На самом деле, возвращаться в состояние, которое было рассмотрено выше нет смысла. Если мы посмотрим на функцию поиска кратчайшего пути в графе (поиск в ширину) — то заметим, что все посещенные вершины могут помещаться в список и при переходе в следующее состояние (по дуге графа, edge) необходимо выполнить поиск нового узла (конца дуги) в списке посещенных:

    step(X,T,[Y,X|T]):-
      edge(X,Y), not(member(Y,T)).

    Мы же в нашей задаче посещенные вершины будем хранить во встроенной базе данных, для этого добавим вспомогательный предикат, выполняющий получение следующего состояния и проверку его наличия в базе. Если в базе такой записи нет — то состояние является новым и в базу добавляется:

    next_unique_state(Volumes, Jars, PrevActions, NextState):-
      next_state(Volumes, Jars, PrevActions, NextState),
      NextState = state(jars(A, B), _Actions),
      \+ jars(A, B),
      assert(jars(A, B)).

    Оператор \+ соответствует логическому НЕ, в Turbo/Visual Prolog соответствующая строка должна быть записана как NOT(jars(A, B)). Предикат jars должен быть объявлен динамическим, а generate_states должен использовать next_unique_state вместо next_state. Перед началом работы базу данных необходимо очистить вызовом retractall (ведь запись в нее — это побочный эффект) и в этом она «хуже» чем список посещенных узлов. С другой стороны записи базы данных доступны в любой точке программы (к ней имеется глобальная точка доступа) и нам это удобно.

    После такой «оптимизации» наше решение начинает работать мгновенно. В нашем случае до оптимизации в решении могли происходить зацикливания, в ряде других задач это не столь критично, но переход в уже пройденное состояние означает повторное вычисление уже обработанной цели. Грубо говоря, рационально сохранить вычисленный для этой цели результат вместо его повторного вычисления. В общем случае такой подход называется мемоизацией или табулированием.

    Итак, исходный код задачи целиком:

    :- dynamic jars/2.
    solve(jar(VolumeA, A), jar(VolumeB, B), target(Target), Actions):-
      retractall(jars(_, _)),
      bfs(volumes(VolumeA, VolumeB), target(Target), [state(jars(A, B), actions([init]))], Actions).
      
    bfs(_Volumes, target(Target), [state(jars(A, B), Actions)|_Other], Actions):-
      (A = Target; B = Target).
    bfs(Volumes, target(Target), [state(Jars, HeadActions)|Buffer], Actions):-
      generate_states(Volumes, Jars, HeadActions, NextStates),
      append(Buffer, NextStates, NextBuffer),
      bfs(Volumes, target(Target), NextBuffer, Actions).
      
    generate_states(Volumes, Jars, actions(PrevActions), NextStates):-
      findall(NextState, 
              next_unique_state(Volumes, Jars, actions(PrevActions), NextState),
              NextStates).
              
    next_unique_state(Volumes, Jars, PrevActions, NextState):-
      next_state(Volumes, Jars, PrevActions, NextState),
      NextState = state(jars(A, B), _Actions),
      \+ jars(A, B),
      assert(jars(A, B)).
      
    next_state(volumes(VolumeA, VolumeB), jars(A, B), actions(PrevActions), NextState):-
      \+ B = 0, % из B можно перелить в A 
      APlusB is min((A + B), VolumeA), % A = A + B
      Delta is APlusB - A, % сколько смогли перелить
      BMinusDelta is B - Delta, % B = B - Delta
      NextState = state(jars(APlusB, BMinusDelta), actions([b_to_a|PrevActions]));
      
      \+ B = 0, % из B можно вылить
      NextState = state(jars(A, 0), actions([b_to_pond|PrevActions]));
      
      \+ A = 0, % из A можно перелить в B
      BPlusA is min((A + B), VolumeB), % A = A + B
      Delta is BPlusA - B, % сколько смогли перелить
      AMinusDelta is A - Delta, 
      NextState = state(jars(AMinusDelta, BPlusA), actions([a_to_b|PrevActions]));
      
      \+ A = 0, % из A можно вылить
      NextState = state(jars(0, B), actions([a_to_pond|PrevActions]));
      
      \+ B = VolumeB, % в B можно зачерпнуть
      NextState = state(jars(A, VolumeB), actions([pond_to_b|PrevActions]));
      
      \+ A = VolumeA, % в A можно зачерпнуть
      NextState = state(jars(VolumeA, B), actions([pond_to_a|PrevActions])). 

    Другие оптимизации

    В ряде случаев (в других задачах) мемоизации будет не достаточно — пространство состояний будет расти невероятно быстро. Тогда применяют эвристики, т. е. некоторые решения необходимо «отбросить». Часто это называют поиском с заглублением — сначала выполняется поиск в ширину на такую глубину, на которую возможно это сделать за приемлемое время (подбирается для каждого случая индивидуально), при этом формируется пространство состояний. Каждому состоянию присваивается некоторая оценка решения — например, оценить можно позицию в шашках и шахматах или в качестве критерия может использоваться длина при поиске кратчайшего пути. Часть позиций с низкой оценкой отбрасывается, а для остальных может выполняться или повторный поиск в ширину или поиск в глубину (иногда сочетание разных видов поиска дает результат быстрее). Естественно, в таких случаях нельзя говорить об уникальности найденного решения, т. к. часть вариантов мы отбросили по субъективному принципу.

    На приведенном рисунке показано как с помощью этой программы можно получить все решения и их количество действий в них. Видно, что решения выводятся в порядке увеличения длины решения, т.е. первое решение – оптимальное, т.к. используется алгоритм поиска в ширину.

Для ответа в этой теме необходимо авторизоваться.