Гамильтонов цикл - Lisp

Формулировка задачи:

Здравствуйте, есть такое задание: Определить функцию, на вход которой подается граф в виде ((a b) (b c) (c d)) a - начало дуги, b - конец. Функция должна определять, является ли он гамильтоновым, и если да, то найти гамильтонов цикл. Цикл в графе называется гамильтоновым, если он содержит все вершины графа ровно по одному разу. Нужна помощь, заранее спасибо.

Код к задаче: «Гамильтонов цикл - Lisp»

textual
(defun is-bound (v1 v2 graph) 
  (cond ((null graph) nil)
        ((or (equal (list v1 v2) (car graph)) (equal (list v2 v1) (car graph))) t)
        (t (is-bound v1 v2 (cdr graph)))))
 
(defun setof (lst) 
  (if (null lst) nil (cons (car lst) (setof (remove (car lst) (cdr lst))))))      
        
(defun vlist (graph)
  (setof (apply 'append graph)))  
 
(defun backtrack (n vlst pth g)
  (cond  ((null pth) nil)
         ((and (is-bound (car pth) (car (last pth)) g) (= (length pth) n))
           (princ pth) (terpri))
         (t  (dolist (v vlst t)
               (when (and (not (member v pth)) (is-bound v (car pth) g))
                     (backtrack n vlst (cons v pth) g))))))
 
(defun hamilt (graph)
  (let* ((vlst (vlist graph))
         (n (length vlst)))
   (backtrack n vlst (list (car vlst)) graph)))
                     
(hamilt '((1 2) (1 3) (1 4) (1 5) (2 3) (3 4) (4 5)))
 
(5 4 3 2 1)
(2 3 4 5 1)
==> T
 
(hamilt '((1 2) (2 3) (3 4) (4 1)))
 
(1 4 3 2)
(3 4 1 2)
==> T

15   голосов, оценка 3.667 из 5


СОХРАНИТЬ ССЫЛКУ