Помогите решить задачу Железнодорожная стрелка

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

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

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

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

    questioner
    Участник

    Здравствуйте.
    Не могли бы вы помочь с решением логической задачи «Железнодорожная стрелка»?

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

    Она чем-то похожа на приведенную Вами задачу о супружеских парах. Я не знаю, как подступить к ее решению на swi-prolog. Очень надеюсь на Вашу помощь. Спасибо.

  • #1869

    Состояние задачи описывается тройкой (Вагоны справа, Вагоны слева, Тупик).
    Вам надо описать правила переходов между состояниями и запустить генерацию новых состояний из начального (генерироваться они будут по описанным правилам). Генерировать до тех пор, пока не выполнится конечное условие, которое тоже тривиально описывается.

    Что конкретно не получается?

    • #1870

      questioner
      Участник

      Не получается написать ограничения на правильное «использование» тупика. Да и выходит не логичным, что последний вагон одного поезда, сразу становится последним вагоном второго. Подскажите, что исправить, пожалуйста.

      lastN(X,N,Begin,End):- 
        append(Begin,End,X), 
        lenght(End,N).
       
      firstN(X, N, Begin,End):- 
        append(Begin,End,X),
        lenght(Begin,N).
       
      solve(A,B):-
        write(A), write(" "),
        write([]), write(" "), 
        write(B),nl, 
        find(A,B,0).
       
      find(A,B, K):- lenght(B,N), N=1, lastN(B,1,Begin,End),
              write(A),write(" "),write(End), write(" "), write(Begin),nl,reverse(End,REnd),
              append(REnd,A,NewA), write(NewA),write(" "),write([]), write(" "),
              write(Begin),nl, K1 is K+1,find(NewA,Begin, K1).
       
      find2(_,_,0).
      find2(B,A,K):-
        firstN(A,1,Begin,End), reverse(Begin, RBegin), 
        write(B),write(" "),write(RBegin),write(" "),write(End),nl,
        append(B,RBegin,NewB), 
        write(NewB),write(" "),write([]),write(" "),write(End),nl,
        K1 is K-1, find2(NewB,End,K1).

      • #1871

        Как-то очень сложно Вы решаете задачу. Мне кажется, Ваша задача решается примерно также как задача о волке, козе и капусте.
        Не было времени вникнуть в Ваш код, но я нашел время и попытался — не получилось.
        Предикат find2 у Вас совсем не используется.

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

        В задаче вагон отличается от паровоза. Если паровоз загнать в тупик, то связанные с ним вагоны двигаться не смогут. В Вашем коде такого разделения я вообще не заметил.

        Я не совсем понял. Могут ли оба состава одновременно быть справа от тупика, например?

        • #1872

          questioner
          Участник

          Здравствуйте. Спасибо за ответ. Пока решить задачу по-другому у меня не вышло.
          Не совсем понимаю, а каким правилом можно задать разделение вагона от паровоза ?

          Да, оба состава могут быть одновременно по одну сторону от тупика.

          • #1873

            Может быть стоит отделять не первый и последний элементы, а делить список в любом месте (ведь поезд можно разорвать в любом месте) — посмотрите правило sublist.
            Я думаю, что локомотив может оказаться в середине поезда теоретически :).

            В зависимости от того, какие варианты генерации новых состояний вы допустите, будет зависеть и формат хранения состояния.

            check(([], [T], L)):- %1
              T = лок, ([лок|_] = L; last(L, лок)), !.
            generate((L, [V], R), (LL, [], RR)):- %2
              append(L, [V], LL), RR = R; LL = L, append([V], R, RR).
            generate((L, [], R), (LL, [V], RR)):- %3
              LL = L, R = [V|RR]; append(LL, [V], L), RR = R.
            % ...

            Я привел лишь вариант, не самый лучший, наверное. Явно в конец надо дописать правил генерации состояний.

            Первое приведенное правило срабатывает когда на левой ветке пусто, в тупике стоит локомотив, а список, стоящий в правой части, содержит локомотив первым или последним элементом. Аналогично должно быть описано правило, когда пусто в правой ветке. Это правило проверки правильности размещения вагонов, если оно завершилось удачно — то решение найдено.

            Второе правило срабатывает в случае, если в тупике что-то находится. В результате генерируются новые состояния, в которых в тупике пусто, а то, что там находилось, прикреплено либо в правый конец левого поезда, либо в левый конец правого поезда.

            Третье правило срабатывает если тупик пуст — в него помещается либо первый элемент правого списка, либо последний элемент левого списка.

            В этом же духе надо описать остальные правила. А затем, запустить поиск в глубину или в ширину.

            Отделять, наверное есть смысл только тот вагон, который является ближним к тупику.
            Если это правый поезд — то просто отделяйте первый элемент.
            Если же это левый поезд — то отделять надо последний элемент. Для этого можно использовать встроенный предикат last(?List, ?Last). Завершается успешно когда Last является последним элементом списка List.

          • #1882

            Я решал бы вашу задачу с поиском в глубину, т.к. тут нет большой разницы, но поиск в глубину выглядит попроще.

            Правило генерации состояний я переписал так:

            generate((L, [V], R), (LL, [], RR)):-
              append(L, [V], LL), RR = R;
              LL = L, append([V], R, RR).
            generate((L, [], R), (LL, [V], RR)):-
              L = [лок|_], last(L, V), append(LL, [V], L), RR = R;
              last(R, лок), R = [V|RR], LL = L.

            Тут учитывается то, что вагон кто-то должен затолкнуть в тупик, поэтому с края должен быть локомотив.

            Предикат поиска в глубину я взял почти без изменений, единственное отличие в том, что вместо сравнения текущего состояния с конечным вызывается предикат is_finish_state (выше я описывал его как check).

            	
            dfs(State, _, [State]):-
              is_finish_state(State), !.
            dfs(A, VN, [A|TR]):-
              generate(A, X),
              not(member(X, VN)),
              dfs(X, [A|VN], TR).

            решение задачи Железнодорожная стрелка

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