IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

 
 Ответить  Открыть новую тему 
> Гамильтонов цикл на Prolog, Гамильтонов цикл на Prolog
kosyak
сообщение 30.10.2008 12:13
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 100
Пол: Мужской

Репутация: -  0  +


Доброго всем времени суток. Помогите разобраться с задачей: "определение цикла Гамильтона в заданном графе". Язык prolog. Какой может быть алгоритм, где можно об этом попонятней почитать? Может есть уже готовая))) На pascalе бы быстро все сделал, а вот с логическим программированием пока проблемы.

Заранее огромное спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 30.10.2008 12:25
Сообщение #2


Гость






Начать можно отсюда: http://isr.by.ru/prolog/ch9_5.htm
 К началу страницы 
+ Ответить 
kosyak
сообщение 30.10.2008 14:37
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 100
Пол: Мужской

Репутация: -  0  +


Цитата(volvo @ 30.10.2008 12:25) *

Начать можно отсюда: http://isr.by.ru/prolog/ch9_5.htm



Спасибо, отличная ссылочка. Буду разбираться
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
kosyak
сообщение 2.11.2008 13:38
Сообщение #4


Пионер
**

Группа: Пользователи
Сообщений: 100
Пол: Мужской

Репутация: -  0  +


Что-то у меня не особо получается... не могу понять как правильно задать граф. По вышеуазанной ссылке написано: "графу соответствует пара множеств - множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро - парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра - функтор р."

Вот я сделал как понял:

Код

domains
  V=integer
  VMas=V*
  R=R(V,V)
  RMas=R*
  Graf=Graf(VMas,RMas)


Правильно ли я понял?

Не получается определить следующий предикат:
Код
смеж( X, Y, граф( Верш, Реб) ) :-
                принадлежит( р( X, Y), Реб);
                принадлежит( р( Y, X), Реб).


Не знаю как разделить domain Graf на состовляющие : вершины и ребра...

Сообщение отредактировано: kosyak - 2.11.2008 13:39
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
kosyak
сообщение 2.11.2008 14:51
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 100
Пол: Мужской

Репутация: -  0  +


Вот описал часть программы:

Код

domains
  VMas=integer*
  R=Rebro(integer,integer)
  RMas=R*
predicates
  path(integer,integer,VMas,RMas,VMas)
  path1(integer,VMas,VMas,RMas,VMas)
  smezh(integer,integer,VMas,RMas)
  prinad(R,RMas)
clauses
  
  path(A,X,VM,RM,P):-
    path1(A,[Z],VM,RM,P).
    
  path1(A,[A|P1],_,_,[A|P1]).
    
  path1(A,[Y|P1],VM,RM,P):-
    smezh(X,Y,VM,RM),
    prinad(X,P1),
    path1(A,[X,Y|P1],VM,RM,P).
    
  smezh(X,Y,VM,RM):-
    prinad(Rebro(X,Y),RM);
    prinad(Rebro(Y,X),RM).
    
  prinad(X, [X|_]).
  prinad(X, [_|L]):-prinad(X,L).


Подчеркивает prinad(Rebro(X,Y),RM); пишет: "423 ',' or ')' expected"

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 2.11.2008 18:25
Сообщение #6


Гость






Хм... Что ты тут натворил?

Смотри, что ты делаешь:
1) описываешь предикат prinad(R, RMas), то есть проверка на существование ребра в графе
2) и тут же:
Код
  path1(A,[Y|P1],VM,RM,P):-
    smezh(X,Y,VM,RM),
    prinad(X,P1),
    path1(A,[X,Y|P1],VM,RM,P).
- вызываешь его как prinad(integer, integer*) ? Нельзя... Сделай отдельно проверку существования вершины в списке...

В общем, вот это:
Код
domains
  VMas=integer*
  R=rebro(integer,integer)
  RMas=R*
predicates
  inlist(integer, VMas)
  path(integer,integer,VMas,RMas,VMas)
  path1(integer,VMas,VMas,RMas,VMas)
  smezh(integer,integer,VMas,RMas)
  prinad(R, RMas)
clauses

% проверка вхождения ребра в список ребер
prinad(X, [X|_]).
prinad(X, [_|L]):-prinad(X, L).

% проверка вхождения номера вершины (integer) в список целых
inlist(X, [X|_]).
inlist(X, [_|L]):-inlist(X, L).
  
  path(A,Z,VM,RM,P):-
    path1(A,[Z],VM,RM,P).
    
  path1(A,[A|P1],_,_,[A|P1]).
    
  path1(A,[Y|P1],VM,RM,P):-
    smezh(X,Y,VM,RM),
    inlist(X,P1),
    path1(A,[X,Y|P1],VM,RM,P).
    
  smezh(X,Y,VM,RM):-
    prinad(rebro(X,Y),RM);
    prinad(rebro(Y,X),RM).
должно нормально компилироваться (Пролога у меня сейчас нет, проверить негде, но вроде бы ошибок не видно)
 К началу страницы 
+ Ответить 
kosyak
сообщение 3.11.2008 11:35
Сообщение #7


Пионер
**

Группа: Пользователи
Сообщений: 100
Пол: Мужской

Репутация: -  0  +


Спасибо большое... пойду дальше разбираться...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
kosyak
сообщение 3.11.2008 13:57
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 100
Пол: Мужской

Репутация: -  0  +


Вот написал полную программу.... но не работает (((

Код

domains
  VMas=integer*
  R=rebro(integer,integer)
  RMas=R*
predicates
  inlist(integer, VMas)
  path(integer,integer,VMas,RMas,VMas)
  path1(integer,VMas,VMas,RMas,VMas)
  smezh(integer,integer,VMas,RMas)
  prinad(R, RMas)
  gamilton(VMas,RMas,VMas)
  vseversh(VMas,VMas,RMas)
clauses

  gamilton(VM, RM, P):-
    path(_,_,VM,RM,P),
    vseversh(P,VM,RM).
    
  vseversh(P,VM,RM):-
   not(inlist(B,VM)),
   not(inlist(B,P)).

  path(A,Z,VM,RM,P):-
    path1(A,[Z],VM,RM,P).
        
  path1(A,[A|P1],_,_,[A|P1]).
    
  path1(A,[Y|P1],VM,RM,P):-
    smezh(X,Y,VM,RM),
    inlist(X,P1),
    path1(A,[X,Y|P1],VM,RM,P).
    

  smezh(X,Y,VM,RM):-
    prinad(rebro(X,Y),RM);
    prinad(rebro(Y,X),RM).
    
  prinad(X, [X|_]).
  prinad(X, [_|L]):-prinad(X, L).
  
  inlist(X, [X|_]).
  inlist(X, [_|L]):-inlist(X, L).
  
/* goal*/
/* gamilton([1,2,3,4],[rebro(1,2),rebro(2,4),rebro(2,3),rebro(3,4)],X)*/
/*    path(1,3,[1,2,3,4],[rebro(1,2),rebro(2,4),rebro(2,3),rebro(3,1)],X)*/


Она даже путь не может посчитать... никак не могу найти ошибку
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
kosyak
сообщение 3.11.2008 17:22
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 100
Пол: Мужской

Репутация: -  0  +


Все, вроде сделал:

Код

domains
  top=symbol
  Vlist=top*
  rebro=rebro(top,top)
  Rlist=rebro*
  gr=graf(Vlist,Rlist)
predicates
  path(top,top,Vlist,Vlist,gr)
  memberV(top,Vlist)
  memberR(rebro,Rlist)
  gamil(gr,Vlist)
  allV(top,Vlist)
  
clauses
  gamil(G,P):-
    G=graf(Vlist,Rlist),
    P=[A|V],
    path(A,B,[A],V,G),
    memberR(rebro(B,A),Rlist),
    allV(X,V).

  path(A,B,V,[B|V],graf(Vlist,Rlist)):-
    memberR(rebro(A,B),Rlist),
    not(memberV(B,V)).
  path(A,B,V,V2,graf(Vlist,Rlist)):-
    memberR(rebro(A,N),Rlist),
    not(memberV(N,V)),
    V1=[N|V],
    path(N,B,V1,V2,graf(Vlist,Rlist)).

  allV(X,L):-
    memberV(X,L).

  memberV(A, [A|_]).
  memberV(A, [_|L]):-memberV(A,L).
  
  memberR(A, [A|_]).
  memberR(A, [_|L]):-memberR(A,L).


только вот почему он выводить несколько раз одно и тоже решение?? непонятно
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 3.11.2008 18:16
Сообщение #10


Гость






Цитата
непонятно
Вот именно... Тебе выводит несколько раз одно и то же, мне не выводит ни одного... Какую цель ставишь?

Код
goal
  gamil(graf([a, b, c, d, e],
       [rebro(a,b), rebro(b, c), rebro(a,d), rebro(d,c), rebro(d,e), rebro(c,e)]), X), write(X).
молчит, как партизан, хотя должен был бы выводить ["a", "b", "d", "c", "e"].
 К началу страницы 
+ Ответить 
kosyak
сообщение 3.11.2008 19:00
Сообщение #11


Пионер
**

Группа: Пользователи
Сообщений: 100
Пол: Мужской

Репутация: -  0  +


Так он правильно выводит... нет никакого цикла... я просто сделал для ориентированного графа. надо rebro(1,2) и rebro(2,1) - не одно и тоже.

Вот исправленная программа, вроде все работает, как мне кажется(тоже с ориентированными):

Код

domains
  top=symbol
  Vlist=top*
  rebro=rebro(top,top)
  Rlist=rebro*
  gr=graf(Vlist,Rlist)
predicates
    /*put' ot odnoy vershini do drugoy*/
  path(top,top,Vlist,Vlist,gr)
    /*prinadlezhit li vershina spisku vershin*/
  memberV(top,Vlist)
    /*prinadlezhit li rebro spisku reber*/
  memberR(rebro,Rlist)
    /*gamiltonov cikl*/
  gamil(gr,Vlist)
    /*vse li vershini proydeni*/
  allV(Vlist,Vlist)
  
clauses
  gamil(G,P):-
    G=graf(Vlist,Rlist),
    P=[A|V],
    path(A,B,[A],V,G),
    memberR(rebro(B,A),Rlist),
    allV(Vlist,V).    

  path(A,B,V,[B|V],graf(Vlist,Rlist)):-
    memberR(rebro(A,B),Rlist),
    not(memberV(B,V)).
  path(A,B,V,V2,graf(Vlist,Rlist)):-
    memberR(rebro(A,N),Rlist),
    not(memberV(N,V)),
    V1=[N|V],
    path(N,B,V1,V2,graf(Vlist,Rlist)).

  allV([],L).
  allV([X|T],L):-
    memberV(X,L),
    allV(T,L).

  memberV(A, [A|_]).
  memberV(A, [_|L]):-memberV(A,L).
  
  memberR(A, [A|_]).
  memberR(A, [_|L]):-memberR(A,L).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
-Алексей-
сообщение 27.12.2012 16:17
Сообщение #12


Гость






Цитата(kosyak @ 3.11.2008 19:00) *

Так он правильно выводит... нет никакого цикла... я просто сделал для ориентированного графа. надо rebro(1,2) и rebro(2,1) - не одно и тоже.

Вот исправленная программа, вроде все работает, как мне кажется(тоже с ориентированными):

Код

domains
  top=symbol
  Vlist=top*
  rebro=rebro(top,top)
  Rlist=rebro*
  gr=graf(Vlist,Rlist)
predicates
    /*put' ot odnoy vershini do drugoy*/
  path(top,top,Vlist,Vlist,gr)
    /*prinadlezhit li vershina spisku vershin*/
  memberV(top,Vlist)
    /*prinadlezhit li rebro spisku reber*/
  memberR(rebro,Rlist)
    /*gamiltonov cikl*/
  gamil(gr,Vlist)
    /*vse li vershini proydeni*/
  allV(Vlist,Vlist)
  
clauses
  gamil(G,P):-
    G=graf(Vlist,Rlist),
    P=[A|V],
    path(A,B,[A],V,G),
    memberR(rebro(B,A),Rlist),
    allV(Vlist,V).    

  path(A,B,V,[B|V],graf(Vlist,Rlist)):-
    memberR(rebro(A,B),Rlist),
    not(memberV(B,V)).
  path(A,B,V,V2,graf(Vlist,Rlist)):-
    memberR(rebro(A,N),Rlist),
    not(memberV(N,V)),
    V1=[N|V],
    path(N,B,V1,V2,graf(Vlist,Rlist)).

  allV([],L).
  allV([X|T],L):-
    memberV(X,L),
    allV(T,L).

  memberV(A, [A|_]).
  memberV(A, [_|L]):-memberV(A,L).
  
  memberR(A, [A|_]).
  memberR(A, [_|L]):-memberR(A,L).


а никак нельзя код под SWI посмотреть? оч нужно
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 19.03.2024 10:10
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"