• Еli
  • Восстановленный участник
  • На форуме с 5 ноября 2005г.
  • Сообщений: 5
  • Спасибо: 0

Тема: Мне тоже нужна помощь в решении задачи о коммивояжере

Люди добрые, поделитесь решением задачи о коммивояжоре на Lisp.
Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим?
Вообще просили использовать "жадный" алгоритм поиска, но мне хоть как-нибудь решить.
Помогите!!!!!
Заранее спасибо!

  • Еli
  • Восстановленный участник
  • На форуме с 5 ноября 2005г.
  • Сообщений: 5
  • Спасибо: 0

Re: Мне тоже нужна помощь в решении задачи о коммивояжере

Единственное, что мне удалось сделать, так это написать алгоритм нахождения гамильтонова цикла (т.е. прохождение через все города только по одному разуи возвращение в исходный город). Методом поиска в глубину с возвратом. Но я не знаю, будет ли это кратчайший путь и как вычислять пройденный путь (надо как-то добавить еще алгоритм?).

(DEFUN HAMILTCYCLE (LAMBDA (GRAPH)
; GRAPH - граф в виде структуры смежности ;
; Результат: гамильтонов цикл в виде списка вершин, ;
; NIL - если гамильтонова цикла не существует ;
(COND ( (NULL GRAPH) NIL )
( T (COND ( (NULL (CDR GRAPH))
(LIST (CAAR GRAPH)))
( T (HC GRAPH (CAAR GRAPH)
(LIST (CAAR GRAPH))
(CDAR GRAPH)
)
)
)
)
)
))
; ---------------------------------------- ;
(DEFUN HC (LAMBDA (GRAPH START VISITED SONS)
; START - первая вершина графа ;
; VISITED - список пройденных вершин ;
; SONS - соседи просматриваемой вершины ;
(COND ( (NULL SONS) NIL )
( T (COND ( (AND (MEMBER START SONS)
(EQ (LENGTH GRAPH)
(LENGTH VISITED))
)
(REVERSE VISITED)
)
( T (COND
( (MEMBER (CAR SONS) VISITED)
(HC GRAPH START VISITED
(CDR SONS)) )
( T (OR (HC GRAPH START
(CONS
(CAR SONS)
VISITED)
(NEIGHBOUR3
(CAR SONS)
GRAPH)
)
(HC
GRAPH START VISITED
(CDR SONS))) )) )
)
)
)
))
; ------------------------------- ;
(DEFUN NEIGHBOUR3 (LAMBDA (X GRAPH)
(COND ( (NULL (ASSOC X GRAPH)) NIL )
( T (CDR (ASSOC X GRAPH)) )
)
))

Пример:

$ (HAMILTCYCLE '((1 . (2 6)) (2 . (1 3 4)) (3 . (2 4))
(4 . (2 3 5)) (5 . (4 6)) (6 . (1 5))))
(1 2 3 4 5 6)

Помогите находить наименьший путь (и его длину)!!!!

  • DMS
  • Восстановленный участник
  • На форуме с 6 октября 2004г.
  • Сообщений: 162
  • Спасибо: 0

Re: Мне тоже нужна помощь в решении задачи о коммивояжере

Вариант решения:
1. сделать список всех возможных перестановок координат городов, добавив в начало и в конец каждого исходную точку.
2. определить длину "линии" для каждого списка.
3. найти min значение и уже затем получить набор точек, т.е. min путь.
функции перестановок лежат в посте VH (2003-11-10 16:42:47)
https://www.caduser.ru/forum/topic6705.html

  • Еli
  • Восстановленный участник
  • На форуме с 5 ноября 2005г.
  • Сообщений: 5
  • Спасибо: 0

Re: Мне тоже нужна помощь в решении задачи о коммивояжере

Предложенное решение конечно правильное, но как его реализовать на Lisp  я незнаю!! Не хочу наглеть, но не могли бы Вы написать код (пожалуйста)?

  • DMS
  • Восстановленный участник
  • На форуме с 6 октября 2004г.
  • Сообщений: 162
  • Спасибо: 0

Re: Мне тоже нужна помощь в решении задачи о коммивояжере

Сразу оговорюсь, что 10 точек уже ждать в лом...
и всё же:
;вспомогательные функции

(defun VHSHIFT (L N)
  (if (> N 0)
    (apply '(lambda (X) (cons X (VHSHIFT X (1- N)))) (list (append (cdr L) (list (car L)))))
    ) ;_ end of if
  ) ;_ end of defun
(defun VHLIST (L) (VHSHIFT L (length L)))
(defun VHSORT (L)
  (if (cdr L)
    (apply 'append
       (mapcar '(lambda (X) (mapcar '(lambda (Y) (cons (car X) Y)) (VHSORT (cdr X)))) (VHLIST L))
       ) ;_ end of apply
    (list L)
    ) ;_ end of if
  ) ;_ end of defun
(defun _LINELENGTH (LST ISCLOSED / )
  (if (cdr LST)
    (+ (distance (car LST) (cadr LST)) (_LINELENGTH (cdr LST) ISCLOSED))
    (if ISCLOSED (distance (car LST) ISCLOSED) 0)
    ) ;_ end of if
  ) ;_ end of defun

;основная

(setq POINTLIST (list (list 0 100) (list 100 0) (list 100 100)))
;|или
(setq POINTLIST nil)
(while (setq PT (getpoint))
  (setq POINTLIST (cons PT POINTLIST))
  (command "_point" PT)
  ) ;_ end of while
|;
;(mapcar '(lambda (X) (command "point" X)) PTLIST)
(defun VOYGER (PTLIST STPT / PATHLEN PATHLIST VARIANTS)
  (setq VARIANTS (VHSORT PTLIST))
  (setq PATHLIST (mapcar '(lambda (X) (cons STPT X)) VARIANTS))
  (setq PATHLEN (mapcar '(lambda (X) (_LINELENGTH X STPT)) PATHLIST))
  (cdr (nth (vl-position (apply 'min PATHLEN) PATHLEN) PATHLIST))
  ) ;_ end of defun
;вызов
(setq RESULT (VOYGER POINTLIST (list 0 0)))
;рисование
(command "_pline")
(foreach N RESULT (command N))
(command "")

дальше куроч сам
P.S. перед рисованием не забудь привязки отключить!!!

  • Еli
  • Восстановленный участник
  • На форуме с 5 ноября 2005г.
  • Сообщений: 5
  • Спасибо: 0

Re: Мне тоже нужна помощь в решении задачи о коммивояжере

Огромное спасибо, ну просто зачет спас!!!!!