Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Задача о переправе через реку (не коза-капуста-волк)
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию Задача о переправе через реку (не коза-капуста-волк) - 05.10.2005, 15:48

Добрый день. Помогите реализовать поиск решения с помощью поиска в глубину для задачи:

Четыре рыцаря, каждый в сопровождении оруженосца, собрались на берегу реки, намереваясь переправиться на другую сторону. Им удалось найти маленькую трехместную лодку, и переправа произошла бы легко. Но все оруженосцы наотрез отказались оставаться в обществе незнакомых рыцарей без своих хозяев. И все же переправа состоялась, все восемь человек благополучно перебрались на другой берег с помощью одной двухместной лодки. При этом соблюдалось условие, на котором настаивали оруженосцы. Как это было сделано?
Ответить с цитированием
  (#2 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 05.10.2005, 20:11

Я попробовал переделать эту задачу с примера решения "козы-волка-капусты"

< конечный код ниже >
Ответить с цитированием
  (#3 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 05.10.2005, 20:45

Написал все возможные варианты переправ
Ответ тот же
Ответить с цитированием
  (#4 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 05.10.2005, 21:32

Насколько я понимаю, проблема в том, что условие not(unsafe(State)) должно проверяться в таком состоянии State, когда кто-то находится в лодке. Иначе по-хорошему задача вообще не будет иметь решения. Тем более, что условия unsafe у Вас выписаны неправильно.
Ответить с цитированием
  (#5 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 05.10.2005, 21:49

Почему неправильно? Я ведь opposite'м проверяю, на разных берегах ли каждая пара "рыцарь-оруженосец". Потом при поиске пути из текущего состояния в конечное я проверяю, чтобы этот ансейф не выполнялся...
Мне кажется тут беда в другом. Ведь результат по моей базе данных возможных перевозок все же выполняется. Но лодки чудесным образом телепортируется обратно несколько раз.
В задаче о фермере возить других мог только фермер, прэтому перевозки автоматически чередовались "туда-сюда" (неправильный "оппозит" автоматически был ложный). Здесь же возить может любой человек. Но как можно отследить, чтобы направление чередовалось? Затесать в move третью переменную?

Код:
move(state(X,O1....O4), state(Y,O1....O4),Y ):- opposite(X,Y).
которая будет хранить берег лодки, а потом в

Код:
path(S,G,L,L1):-
         move(S,S1),
         not( unsafe(S1) ),
         not( member(S1,L) ),
         path( S1,G,[S1|L],L1),!.
как-то организовать проверку, что если предыдущий показатель берега лодки west, след. - east ...
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 05.10.2005, 22:19

< последний код ниже >
Ответить с цитированием
  (#7 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 05.10.2005, 22:37

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

< cut >
Ответить с цитированием
  (#8 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 06.10.2005, 12:22

Это ведь не решение.
Еще раз. С теми требованиями, что у Вас есть, решения задачи просто нет.
То есть безопасными должны быть следующие ситуации: исходная, конечная, а из промежуточных те, в которых кто-то сидит в лодке. Здесь, во-первых, в лодке не должно быть оруженосца с чужим рыцарем, а во-вторых, на каждом берегу не должно быть оруженосца в присутствии чужих рыцарей и отсутствии своего.
Опасные положения в (левых частях) перечислены все, а вот правые я бы заменила на not(X=Y), для того чтобы они подходили и для тех, кто в лодке. Я хочу сказать, что если бы я решала эту задачу путем переделывания задачи про козу с капустой, то я, пожалуй, помимо east и west ввела бы еще одно положение, например, boat - в лодке. Кроме этого, чтобы сразу находить решение покороче, имеет смысл с исходного берега отправлять только двоих, а с противоположного - либо по одному, либо двоих.
Ответить с цитированием
  (#9 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 06.10.2005, 15:21

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

left | boat | right

K1O1 K2O2 on_left | |
--- безопасно

O1 K2O2 on_lef t| K1 on_boat |
--- не знаю. О1 на берегу один, значит небезопасно. Но зачем тогда вводить это промежуточное состояние ? если "безопасность" такого случая всегда будет соответствовать состоянию, когда лодка причалит к противоположному берегу (описал ниже). А если лодка выйдет на воду и вернется обратно на берег - какой толк ...

O1 K2O2 on_left | | K1 on_right --- небезопасно

Но попробую.. А что Вы посоветуете насчет повторности направлений лодки подряд?

Добавлено:

Я добавил новое состояние

Код:
opposite(west, boat).
opposite(boat,east).
opposite(east,boat).
opposite(boat,west).
заменил opposte'ы в объявлении unsafe на not'ы (хотя по моему это одно и тоже, но наверное так быстрее).
Программа виснет :(
Ответить с цитированием
  (#10 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 06.10.2005, 17:31

Такого
Код:
opposite(west, boat). 
opposite(boat,east). 
opposite(east,boat). 
opposite(boat,west).
категорически не нужно. Только:
Код:
opposite(west,east). 
opposite(east,west).
А для той смены состояний, по-видимому, нужен другой предикат.
В чем смысл еще одного состояния. Кто-то садится в лодку, после этого проверяется, безопасно ли состояние, после этого люди высаживаются на противоположном берегу, а вот тут состояние уже вполне может быть опасным, т.е. здесь его проверять на безопасность не надо. И надо следить за берегами, т.е. одним из аргументов предиката path должен быть берег, от которого будет отплывать лодка.
Ответить с цитированием
  (#11 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 06.10.2005, 17:48

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

На первом берегу Рыц1, Ор1, Рыц2, Ор2,
на втором Рыц3, Ор3

На левом берегу в лодку садится один Ор1, ситуация безопасна, а то что он высадится на правом берегу без своего рыцаря и будет в обществе Рыц3 нас уже не волнует.

НО если бы в лодку садился не Ор1, а Рыц1, то это уже неприемлемо, так как на берегу, от которого лодка отчаливает остается Ор1 без рыцаря (с Рыц2).

Верно понял?
Ответить с цитированием
  (#12 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 06.10.2005, 17:52

В общем, да.
Только я бы с левого берега (если он исходный) не отправляла по одному, а только по двое.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 06.10.2005, 18:27

move перемещает с берега сразу на берег. Значит в правую часть каждого move надо записать не opposite, а что-то другое.
Но зачем нам тогда предикат opposite, который минует стадию лодки. Но как вы сказали, почему-то нельзя расписать этот предикат перемещения как цепочку, промежуточно включающую лодку. А куда тогда поместить возможность сесть в лодку..
Проверку на направление движения сделал, а встроить третье состояние не получается. Alison, я без вас никак :)
Ответить с цитированием
  (#14 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 06.10.2005, 18:39

Я попробовал сделать чуть по другому

Изменил предикаты ансейф

Код:
unsafe( From,state(Y,X,X,_,_,_,_,_) ):- not(X=Y), X=From.
unsafe( From,state(Y,X,_,_,X,_,_,_) ):- not(X=Y), X=From.
unsafe( From,state(Y,X,_,_,_,_,X,_) ):- not(X=Y), X=From.

unsafe( From,state(X,_,Y,X,_,_,_,_) ):- not(X=Y), X=From.
unsafe( From,state(_,_,Y,X,X,_,_,_) ):- not(X=Y), X=From.
unsafe( From,state(_,_,Y,X,_,_,X,_) ):- not(X=Y), X=From.

unsafe( From,state(X,_,_,_,Y,X,_,_) ):- not(X=Y), X=From.
unsafe( From,state(_,_,X,_,Y,X,_,_) ):- not(X=Y), X=From.
unsafe( From,state(_,_,_,_,Y,X,X,_) ):- not(X=Y), X=From.

unsafe( From,state(X,_,_,_,_,_,Y,X) ):- not(X=Y), X=From.
unsafe( From,state(_,_,X,_,_,_,Y,X) ):- not(X=Y), X=From.

unsafe( From,state(_,_,_,_,X,_,Y,X) ):- not(X=Y), X=From.
А вот предикат path

Код:
path(_,G,G,T,T).   /* The final state is reached  */

path(From,S,G,L,L1):-
         move(S,S1,From1),
         From = From1,   
         not( unsafe(From1,S1) ),
         not( member(S1,L) ),    
         path( From1, S1,G,[S1|L],L1),!.
Идея в том, что перевозка отрицательна, если оруженосец оставшийся с рыцарями без хозяина находится в месте отплытия лодки. А если же это произошло, но на месте прибытия лодки, то ситуация будет безопасна. Мне кажется то что я сделал эквивалентно введению состояния "on_boat" ?
Поправьте меня

Забыл добавить, еще удалил объявления move , где оруженосцы перемещаются не со своими рыцарями
Ответить с цитированием
  (#15 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 07.10.2005, 14:00

Цитата:
Мне кажется то что я сделал эквивалентно введению состояния "on_boat" ?
Нет, не эквивалентно.
Можно сделать примерно так:
Код:
path(GoalState,GoalState,Path,Path,_):- !.    
path(StartState,GoalState,VisitedPath,Path,X):-
move(StartState,NextState,in,X),  % переход в состояние "в лодку" с берега X
not(unsafe(NextState)),      
opposite(X,Y),
move(NextState,NextState1,out,Y),  % переход в состояние "из лодки" на берег Y
not(member(NextState1,VisitedPath)),      
path(NextState1,GoalState,[NextState1|VisitedPath],Path,Y).
Соответственно, для move:
Код:
b(east).
b(west).

move(state(west,O1,R2,O2,R3,O3,R4,O4),state(boat,O1,R2,O2,R3,O3,R4,O4),in,west).
...
move(state(X,X,R2,O2,R3,O3,R4,O4),state(boat,boat,R2,O2,R3,O3,R4,O4),in,X):- b(X).
...
(если надо переправиться с east на west).
Здесь in - направление в лодку, а последний аргумент - с какого берега люди садятся в лодку.
Аналогично для направления out - из лодки, тогда последний аргумент - это берег, на который высаживаются люди из лодки.
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача о перевозке (волк, коза, капуста) методом в ширину Vit86 Prolog 9 05.12.2012 21:21
Помогите, задача по прологу, срочно...задача с высказываниями 4ixOn Prolog 6 10.07.2011 23:29
Помогите, задача по прологу, срочно...задача о станках 4ixOn Prolog 3 09.07.2011 22:48
Волк, коза, капуста (навороты) kulikov_s Prolog 15 12.12.2010 23:09
волк, коза, капуста в стране восходящего солнца))) aag Prolog 19 08.10.2010 03:47
задача о перевозке(волк,коза,капуста) поиском в глубину yurbass Prolog 12 29.03.2009 14:29
Переправа толстых через реку Винитарх Prolog 3 17.02.2007 02:03
Волк, коза и капуста (срочно) Вастич Prolog 1 23.12.2006 18:32
Волк Коза Капуста (по просьбе Сергея) Alexei A. Morozov Prolog 3 24.10.2005 19:01
Перевозка через реку AlexMaa Prolog 3 14.06.2005 05:53
Волк, коза, капуста. Поиск в ШИРИНУ imported_Goodman Prolog 3 03.06.2005 12:30



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов