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

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

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

Просмотр 7 сообщений - с 1 по 7 (из 7 всего)
  • Автор
    Сообщения
  • #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).

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

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

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