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

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

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

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

  • Автор
    Сообщения
  • #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).

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