VPF::Задача о миссионерах и людоедах

Alenkakiss

Дата 22.12.2009, 15:19 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 22.12.2009

Репутация: нет
Всего: нет

Помогите нововичку разобраться в логической задаче.
Условие
Миссионеры и людоеды (поиск в ширину).
Три миссионера и три людоеда находятся по одну сторону реки, через которую они хотят переправиться. В их распоряжении имеется лодка, которая может выдержать вес только двух человек. Кроме того, если в какой-то мо-мент число людоедов станет больше числа миссионеров, миссионеры будут съедены независимо от того, на каком берегу реки это случится.
Указания к решению. Различные состояния этой задачи однозначно задаются информацией, на каком берегу находятся лодка и сколько миссионеров и лю-доедов на этом же берегу.
Поэтому структура
state(ЛокализацияЛодки,
         ЧислоМиссионеровНаТомБерегуГдеЛодка,
         ЧислоЛюдоедовНаТомБерегуГдеЛодка)
полностью описывает состояние. Допустимые состояния для решения задачи - это те, когда людоеды не могут съесть миссионеров ни на том берегу, где лодка, ни на противоположном,
Возможные значение первого аргумента: атомы west (западный берег)  и east (восточный берег). Возможные значения остальных аргументов: 0, 1, 2 или 3.
Начальное состояние: state(east,3, 3). Конечное состояние: state(west,3,3).

2 людоеда или 1 людоед и 1 миссионер переправляются.
2. миссионер возвращается назад, если посылали 2 людоедов, то возвращается один из людоедов.
Итак: на 1-ом берегу 2Л и 3М, на втором 1Л.
3. Посылаем на тот берег 2Л.
4. Возвращаем 1Л.
Итак: на 1-ом берегу 1Л и 3М, на втором 2Л.
5. Пускаем 2М на тот берег.
6. Возвращаем 1Л и 1М.
Итак: На этом берегу 2Л и 2М, на втором 1Л и 1М
7. Посылаем на тот берег 2М.
8. Возвращаем на 1-ый берег 1Л.
Итак: на 1-ом берегу 3Л, на втором 3М.
9. Посылаем на тот берег 2Л.
10. Возвращаем назад 1Л.
11. Переправляем последних голодных и уставших 2Л.

Нашла решение этой задачи на VIP7 с помощью поиска в ширину. Оно содержит 11 переправ.

Код


open core, console, list

domains
сост = tuple(symbol, integer*, integer*).
путь = сост*.

class predicates
поиск_в_ширину: (сост, сост) -> путь determ.
поиск_в_ширину: (путь*, сост*, сост) -> путь determ.
переход: (сост) -> сост nondeterm.
перевезти: (integer, integer*, integer*, integer*, integer*) nondeterm (i,i,i,o,o). 

clauses
поиск_в_ширину(X, Y) = поиск_в_ширину([[X]], [X], Y).

поиск_в_ширину([[Y | П] | _], _, Y) = [Y | П]:- !.
поиск_в_ширину([[X | П] | Пути], Состояния, Y) = поиск_в_ширину(НовПути, Состояния1, Y):-
    Продолжения = [[Z, X| П] || Z = переход(X), not(isMember(Z, Состояния))],
            НовПути = append(Пути, Продолжения),
            Вершины = [V || [V | _] = getMember_nd(Продолжения)],
            Состояния1 = append(Вершины, Состояния).

переход(tuple("л", Л, П)) = tuple("п", Л1, П1):-
    N = std::fromTo(1, 2),
    перевезти(N, Л, П, Л1, П1).
переход(tuple("п", Л, П)) = tuple("л", Л1, П1):-
    N = std::fromTo(1, 2),
    перевезти(N, П, Л, П1, Л1).        

перевезти(N, [КДо, МДо], [КПосле, МПосле], [КДо-КЛ, МДо-МЛ], [КПосле+КЛ, МПосле+МЛ]):- 
    КЛ = std::fromTo(0, КДо),
    КЛ <= N, 
    МЛ = N - КЛ,
    МЛ <= МДо,  
    if МДо-МЛ > 0 then КДо-КЛ <= МДо-МЛ end if,
    if МПосле+МЛ > 0 then КПосле+КЛ <= МПосле+МЛ end if.

class facts
    счетчик : positive := 0.

clauses
    run():- 
        init(),
        Старт = tuple("л", [3, 3], [0, 0]),  
        Цель= tuple("п", [0, 0], [3, 3]), 
        Путь = поиск_в_ширину(Старт, Цель), 
        foreach tuple(Берег, Левый, Правый) = getMember_nd(reverse(Путь)),
                Левый = [КЛ, МЛ], Правый = [КП, МП]
          do 
            writef("%. На левом берегу: % кан. и % мис.; на правом берегу: % кан. и % мис. \n", 
                   счетчик, КЛ, МЛ, КП, МП),
            if Берег = "л" 
               then write("\tлодка отправляется с левого берега на правый\n\n")
               else if not(Левый = [0, 0]) then 
                      write("\tлодка отправляется с правого берега на левый\n\n") end if
             end if,
             счетчик := счетчик + 1
        end foreach,
        !, 
        _ = readLine();
        succeed().

Подскажите, как переделать для SWI-Prolog?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Prolog \| Следующая тема »