Поиск в глубину в задаче про пять супружеских пар

Программирование Помощь с решением задач на Prolog Решение головоломок на Prolog Поиск в глубину в задаче про пять супружеских пар

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

Просмотр 4 сообщений - с 1 по 4 (из 4 всего)
  • Автор
    Сообщения
  • #1878

    questioner
    Участник

    Добрый день.
    Подскажите, пожалуйста, как получить несколько решений в задаче про ревнивых пять супружеских пар?
    Мы обходим граф в ширину, наши решения ветвятся, сейчас выводится только одно решение, а как вывести все? — использовать поиск в глубину?

    #1879

    Дело в том, что поиск в ширину ищет кратчайший путь (и этим в корне отличается от поиска в глубину).
    Кратчайший путь в этом случае — это вариант переправы, содержащий наименьшее количество перемещений лодки.

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

    #1880

    questioner
    Участник

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

    #1881

    Я ошибся про поиск в ширину.
    Правило dfs менять не надо вообще.

    Изменить надо запрос:

    ?- dfs(([ma,mb,mc,md,me,fa,fb,fc,fd,fe],[],[],left),[],Path),
       printpath(Path).

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

    ?- dfs(([ma,mb,mc,md,me,fa,fb,fc,fd,fe],[],[],left),[],Path),
       printpath(Path), fail.

    Но решений тут очень много. Я не думаю, что «получить все решения» — это хорошая идея.

    В статье я использовал предикат print для вывода пути, но тогда я не знал что есть одноименный встроенный предикат. На самом деле, он просто выводит список в столбик, чтобы можно было нормально прочитать путь.
    Используйте примерно вот такой предикат для этой цели:

    printpath([]):-!.
    printpath([H|T]):-
        write(H), nl, printpath(T).

Просмотр 4 сообщений - с 1 по 4 (из 4 всего)

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