Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Интересная задача о КОНВЕРТЕ
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Адиль Адиль вне форума
Новичок
 
Сообщений: 10
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.01.2005
По умолчанию Интересная задача о КОНВЕРТЕ - 11.01.2005, 13:46

Люди помогите написать на Прологе задачу о конверте:
Суть: Всем извесная логическая задача.Нарисовать конверт, не отрывая карандаша от бумаги, и не проводя по одной и той же линии. Введем обозначения ребра графа буквами (литерные константы), вершины цифрами.
[][][]а /1
[][][]]/__ в
[][]]2| б /|3
[][][г|д/е|ж
[]][]4| /_ |5
[][][][]] з

[]-специальновставлены для поддержки правильного отоброженияграфика

predicates
ребро (а,1,2) т.е. от вершины 1 до 2 идет ребро а. Т.к. граф не ориентированный то используется предикат вида ребро (а,1,2) т.е. знания о структуре графа будет содержать 16 фактов:
ребро (а,1,2)
ребро (а,2,1)
Решением задачи должен являться список пройденных ребер графа, причем длина должна быть 8, и не должно быть повторяющихся ребер.
Правила:
1.Путь (Т,П):-длина (П,, write _list(Пройденных ребер),!.
2.Путь (Т,П):-ребро (Р,Т,H), не принадлежит (Р,П),пройденному пути (H,[Р|П]).
Т- текущая вершина графа, а Р список пройденных ребер.
[b]1-ое правило означает:
Если длина списка Р становится=8, список Р выводится на печать.
[b]2-ое правило явл-яс генератором перебора. Оно перебирает предикаты ребро и находит такое что оно не принадлежит к списку Р и поиск дальнейшего пути производится из новой вершины Р.
Дополнения:
Фрагмент 1-ый
Определение длины списка от правила:
длина([],0).
длина([A|B],N):-длина (B,M),N is M+1
Фрагмент 2-ой
Вывод списка из правила 2.
write_list([]).
write_list([H|T]):-write(H),write_list(T).
А теперь вопрос:
goal
путь(4,[])-должен выводить с любой вершины полный список рисования конверта

Если у кого-то имеется совершенно другое решение, то помогите. Заранее благодарен.
Ответить с цитированием
  (#2 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,955
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 11.01.2005, 21:27

Это называется эйлеров путь. Ищется он ЭЛЕМЕНТАРНО:
Код:
domains il=integer*
facts дуга(integer,integer)
predicates
nondeterm ребро(integer,integer)
nondeterm путь(integer,il,il,integer)
принад(integer,integer,il)
goal 
путь(4,[],Путь,0).
clauses 
дуга(1,2).  дуга(1,3).  дуга(2,3).  дуга(2,4).
дуга(2,5).  дуга(3,4).  дуга(3,5).  дуга(4,5).

ребро(А,Б):-дуга(А,Б);дуга(Б,А).

путь(_,Путь,Путь,8):-!.
путь(А,Стек,Путь,К):-ребро(А,Б),not(принад(А,Б,Стек)),
   К1=К+1,путь(Б,[А,Б|Стек],Путь,К1).

принад(А,Б,[А,Б|_]):-!.
принад(А,Б,[Б,А|_]):-!.
принад(А,Б,[_,_|Стек]):-принад(А,Б,Стек).
Из вершины №4 прога нашла 44 возможных эйлеровых пути. Заметьте, что прога выводит путь в виде обратного списка, в котором каждое ребро задаётся парой своих смежных вершин. Например, первое решение:
Код:
Путь=[3,5,1,3,2,1,4,2,3,4,2,3,5,2,4,5]
надо понимать как последовательность рёбер:
(4,5)(5,2)(2,3)(3,4)(4,2)(2,1)(1,3)(3,5).
Если Вам надо, то добавьте реверс списка пути самостоятельно.
Ответить с цитированием
  (#3 (permalink)) Старый
Адиль Адиль вне форума
Новичок
 
Сообщений: 10
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.01.2005
По умолчанию 11.01.2005, 22:40

Зачем нужно слово facts и честно говоря у меня пролог останавливается на дуга(integer,integer) и дальше отказывается работать. Может что-то не так?
Ответить с цитированием
  (#4 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 11.01.2005, 23:55

Цитата:
Originally posted by Адиль
[b]Может что-то не так?
Конечно не так. Зачем слово facts убрали?
facts - это раздел БД.
Если сильно не нравится, уберите полностью этот раздел и перенесите объявление дуга в раздел predicates, не забудьте написать перед ним nondeterm, в facts он по умолчанию такой.
А лучше всего - не портите прогу.
И зачем было весь пост цитировать?
Ответить с цитированием
  (#5 (permalink)) Старый
Адиль Адиль вне форума
Новичок
 
Сообщений: 10
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.01.2005
По умолчанию 12.01.2005, 12:08

С б.д. я еще не разу не работал. В domains мы ее публикуем и описываем. Значит нужно создавать файл facts типа *.dat и описывать там данные.
дуга(1,2). дуга(1,3). дуга(2,3). дуга(2,4).
дуга(2,5). дуга(3,4). дуга(3,5). дуга(4,5).
А как подключить б.д. к проге? Или надо действовать как-то по другому?
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,955
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 12.01.2005, 18:46

Никакой файл БД создавать не надо, т.к. я эту БД УЖЕ ВКЛЮЧИЛ в исходник:
Код:
дуга(1,2). дуга(1,3). дуга(2,3). дуга(2,4). 
дуга(2,5). дуга(3,4). дуга(3,5). дуга(4,5).
Адиль пишет:
Цитата:
Зачем нужно слово facts и честно говоря у меня пролог останавливается на дуга(integer,integer) и дальше отказывается работать. Может что-то не так?
Причина проста - Вы работаете в Турбо-Прологе, а этот дедуля не понимает ключевое слово facts. Поставьте вместо него database и всё будет чики-пики.

Alison, я это сделал специально, из вредности, предвидя, что Адиль работает на Турбе. А в VIP можно писать и facts и database.
Ответить с цитированием
  (#7 (permalink)) Старый
Адиль Адиль вне форума
Новичок
 
Сообщений: 10
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.01.2005
По умолчанию 15.01.2005, 21:35

Большое спасибо за задачу. Наконец-то я нашел VIP 5.2 и протестировал задачу
Ответить с цитированием
  (#8 (permalink)) Старый
Адиль Адиль вне форума
Новичок
 
Сообщений: 10
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.01.2005
По умолчанию 17.01.2005, 21:50

Но как быть, если нужно искать с других вершин. Эта программа работает только с 4-ой и 5-ой вершинами. Как ее можно модифицировать, чтобы она могла искать такие пути:
путь(1,[],Путь,0).
путь(2,[],Путь,0).
путь(3,[],Путь,0).
Ответить с цитированием
  (#9 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,955
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 18.01.2005, 12:34

Цитата:
Как ее можно модифицировать, чтобы она могла искать такие пути:
Код:
путь(1,[],Путь,0). 
путь(2,[],Путь,0). 
путь(3,[],Путь,0).
Вы абсолютно правильно изменили цель. И Пролог Вам абсолютно правильно и честно ответил, что из данных точек РЕШЕНИЙ НЕТ. Поверьте мне, что он (Пролог) очень старался и перебрал все возможные пути, но, к сожалению, решения не нашёл.
Адиль, попробуйте сами карандашом по бумаге. Может у Вас получится лучше, чем у Пролога.
Ответить с цитированием
  (#10 (permalink)) Старый
Адиль Адиль вне форума
Новичок
 
Сообщений: 10
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.01.2005
По умолчанию 19.01.2005, 14:31

Цитата:
Адиль, попробуйте сами карандашом по бумаге. Может у Вас получится лучше, чем у Пролога.
Большое спасибо за сарказм. Попробовал на бумаге. Признаю свою ошибку
Ответить с цитированием
  (#11 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 19.01.2005, 15:06

Цитата:
Originally posted by Адиль
[b]Большое спасибо за сарказм.
Адиль, это не сарказм, это мягкий юмор ...
Цитата:
Попробовал на бумаге.
... а также намек на то, что если слегка углубиться в теорию графов, то сразу станет ясно, что у Вашего связного графа ровно 2 нечетные вершины, поэтому эйлеров путь, во-первых, существует, а, во-вторых, начинаться он может только в одной из этих вершин и заканчиваться в другой. Вот если бы у Вашего графа все вершины были четными (если б конверт, например, был бы полностью развернут, т.е. еще пририсованы ребра (4,6) и (5,6) снизу), то из любой вершины можно было бы построить эйлеров цикл (много циклов ), т.е. нарисовать развернутый конверт, не отнимая карандаша от бумаги и не проводя одну линию дважды.
Ответить с цитированием
  (#12 (permalink)) Старый
Адиль Адиль вне форума
Новичок
 
Сообщений: 10
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.01.2005
По умолчанию 25.01.2005, 11:09

Большое спасибо
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Stom Stom вне форума
Новичок
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2007
По умолчанию 27.11.2007, 00:13

Всем доброго времени суток

Задали мне написать программу об обходе всех вершин графа из заданной точки и вывода пути (конверт) , вот она:

Код:
domains
текущая = integer
ребро = ребро(string,integer,integer)

пройденые = string*
predicates
является_элементом(string,пройденые)
не_является_элементом(string,пройденые)
длина(пройденые, integer)
nondeterm найти_путь(integer,пройденые)
nondeterm ребро(string,integer,integer)
clauses
ребро("а",1,2).
ребро("а",2,1).

ребро("б",2,3).
ребро("б",3,2).

ребро("в",1,3).
ребро("в",3,1).

ребро("г",2,4).
ребро("г",4,2).

ребро("д",2,5).
ребро("д",5,2).

ребро("е",4,3).
ребро("е",3,4).

ребро("ж",3,5).
ребро("ж",5,3).

ребро("з",4,5).
ребро("з",5,4).

является_элементом(Ребро,[Ребро|_]):- !.
является_элементом(Ребро,[_|Пройденые]):- является_элементом(Ребро,Пройденые).
не_является_элементом(Ребро,Пройденые):- not(является_элементом(Ребро,Пройденые)).
длина([],0).
длина([_|А],Л):- длина(А,Длинахвоста), Л=Длинахвоста+1.

найти_путь(_,Пройденые):-длина(Пройденые,8),write(Пройденые).

найти_путь(Текущая,Пройденые):-ребро(Ребро,Текущая,Новая),не_является_элементом(Ребро,Пройденые),найти_путь(Новая,[Ребро|Пройденые]).    

goal
найти_путь(4,[]).
Но работает немножко не совсем правильно, т.к. вывод начинается в обратном порядке и не с нужного ребра... Подскажите пожалуйста что нужно добавить чтоб все было ок?
Ответить с цитированием
  (#14 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 29.11.2007, 21:36

У Вас не хватает выходного аргумента в предикате найти_путь. Примеров поиска путей на форуме - масса. Посмотрите, как делается там.
Ответить с цитированием
  (#15 (permalink)) Старый
Stom Stom вне форума
Новичок
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2007
По умолчанию 30.11.2007, 10:30

Цитата:
У Вас не хватает выходного аргумента в предикате найти_путь. Примеров поиска путей на форуме - масса. Посмотрите, как делается там.
Спасибо, Alison я смотрел. и провел несколько часов пытаясь найти решение. Конечно для вас это смешно, однако мои познания в Прологе более чем скромны
Ответить с цитированием
Ответ

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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Интересная проблема kostyanisha Любые вопросы от новичков 1 16.02.2012 21:06
Интересная проблема Kirill Mashtaler Процессоры 10 12.01.2012 18:10
интересная программа evgen1 Pascal 15 15.12.2010 20:49
интересная задача n-andriy Pascal 3 24.06.2010 12:04
Интересная программа.... jkwe45 Софт и программы 2 15.02.2010 14:25
Интересная задачка hasper Prolog 35 21.12.2009 21:12
Интересная задачка DYX_56 Pascal 7 10.09.2008 21:04
Интересная проблема с ХР vitem Софт и программы 13 14.07.2008 10:55
Интересная задачка =) Gateway Prolog 5 25.01.2008 03:07
Интересная задача!!!!! С ++ eugene С/С++ 0 23.06.2007 18:24
Интересная задачка Black Monarh Pascal 6 28.12.2006 21:55
Интересная задача как создать алгоритм данных на вычисление ЕкатеринаАК Алгоритмы 8 06.12.2005 12:07



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