Доброго времени суток! Возникла проблема с переводом программы из языка LISP в Пролог.
(текст программы из лиспа)
| Код |
; смежная вершина (первая вершина ребра, вторая вершина ребра,
; список найденных вершин, список новых вершин)
(defun smezver(x y snaid snov)
(cond
((not (member x snov)) nil) ;x не является новой вершиной
((member y snov) nil) ;y является новой вершиной
((member y snaid) nil) ;y является ранее найденной вершиной
(t t))) ;вершина является новой смежной вершиной
;поиск смежных вершин (список найденных вершин, список новых вершин, список ребер)
(defun smez(snaid snov sreb)
(cond
((null sreb) nil) ;конец поиска
((smezver (caar sreb) (cadar sreb) snaid snov) ;смежная вершина
(cons (cadar sreb) (smez snaid snov (cdr sreb)))) ;добавление в список
((smezver (cadar sreb) (caar sreb) snaid snov) ;смежная вершина
(cons (caar sreb) (smez snaid snov (cdr sreb)))) ;добавление в список
(t (smez snaid snov (cdr sreb))))) ;пропуск ребра
;поиск в ширину (список найденных вершин, список новых найденных вершин,
; вершина для поиска, список ребер)
(defun shir(snaid snov y sreb)
(cond
((null snov) nil) ;не найдено ни одной новой вершины
((member y snov) t) ;вершина найдена
(t (shir (append snaid snov) (smez snaid snov sreb) y sreb)))) ;добавление новых вершин
;поиск пути (первая вершина, вторая вершина, список ребер)
(defun path(x y sreb)
(shir nil (list x) y sreb)) ;поиск в ширину
;перебор вершин (первая вершина, список вершин, список ребер)
(defun perebor(fver sver sreb)
(cond
((null sver) t) ;конец перебора
((path fver (car sver) sreb) (perebor fver (cdr sver) sreb)) ;путь найден
(t nil))) ;нет пути
;определение связанности графа(список вершин, список ребер)
(defun svgraf(sver sreb)
(perebor (car sver) (cdr sver) sreb)) ;перебор вершин и поиск пути от первой вершины ко всем остальным
|
В общем, застрял на второй функции. Написал первый случай, когда Sreb нулевой. Дальше, я так понимаю, нужно как-то переопределить X и Y из первой функции, чтобы был вид деревьев(Что такое caar и cadar для Пролог?). Пока наработки такие, дальше не получается, 3й день бьюсь, спасайте:
| Код |
smezver(X, Y, Snaid, Snov):-
not(member(X, Snov)),
member(Y, Snaid),
member(Y, Snov).
smez(Snaid, Snov, 0):-
fail.
smez(Snaid, Snov, Sreb):-
smezver([X, Sreb], [Y, Sreb], Snaid, Snov),
append([Y, Sreb], (smez, Snaid, Snov, (nil, Sreb)));
smezver([Y, Sreb], [X, Sreb], Snaid, Snov),
append([X, Sreb], (smez, Snaid, Snov, (nil, Sreb))),
X is [tree(nil,Root,nil)|tree(nil,Root,nil)],
Y is [tree(nil,Root,tree(nil,Root,nil))|tree(tree(nil,Root,nil),Root,nil)].
|
|