Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > задачка коммивояжера

Автор: Гость_Olga 30.11.2005, 22:51

Необходимо решить задачу коммивояжера на Lisp.
Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город.
Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим?
Выдавать программа должна кротчайший путь коммивояжера (список пройденных городов) и его длину.
Для нахождения длины пути велели задавать матрицу городов в виде списка расстояний между городами. Допустим есть три города А В С , тогда надо задать список расстояний от одного города до каждого из остальных ((0 3 9) (3 0 1) (9 1 0)).
АВС
А 039
В 301
С 910
На входе у нас есть два списка: список городов и список расстояний между городами.
Надо реализовывать эвристический алгоритм поиска, с эвристикой `идти в ближайший город`. Решать задачу надо с помощью рекурсии.
Пожалуйста помогите. Заранее спасибо.

Автор: SET P 1.12.2005, 12:03

просто, когда человек хочет решить задачу, он сначала делиться своими мыслями по реализации и рассказывает какие у него возникли трудности... в общем, активно что-то делает, а не ждёт когда за него всё сделают другие. люди, знающие LISP, здесь есть. Вам наверняка помогут.

а "на слабо" лучше брать в разделе Центр помощи

Автор: svg 2.12.2005, 01:12

По зубам, мотивации нет работать за индивида/индивидку, который сам
никаких усилий не приложил.

Напишите Деду Морозу, найдете решение в чулке под кроватью.

Автор: Гость_Olga 2.12.2005, 18:12

С чего Вы взяли, что я ничего не делаю и не приложила ни каких усилий. Просто давать какие-то рекомендации по решению я не могу, т.к не знаю как решать. А давать свои наработки (неработающие) не имеет смысла, тюкю разбираться в чужом коде зачастую весьма трудно (это я уже один раз пробовала).
То, что я прошу решить задачку еще не означает, что я "халявщица", поэтому прошу не обижать.

Автор: Andrey1 2.12.2005, 18:33

Цитата

Не хочу, конечно, подливать масло в огонь..., но хочу заметить, что действительно, люди сюда приходят не чтобы озадачеваться. А скорее, чтобы расслабиться, пообщаться и узнать что-нибудь интересное.

Автор: Guest 3.12.2005, 00:00

Какие Вы здесь все вредные

Автор: DENNN 5.12.2005, 10:06

Ага такие вот прямо вредные-вредные.

Автор: AntonSaburov 5.12.2005, 14:13

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

Автор: Гость_Olga 5.12.2005, 16:58

Ну тогда скажите пожалуйста как удалить свою тему

Автор: svg 5.12.2005, 19:42

Вот решение.

Код


(defparameter *towns*
  '(a b c d e f))

(defparameter *path-matrix*
  (make-array (list (length *towns*) (length *towns*))
              :initial-element 0))

(defun fill-path-matrix (&optional (max-distance 10))
  "Fill *path-matrix* randomly"
  (labels ((gen-dist ()
             (let ((d (random max-distance)))
               (if (> d 0) d (gen-dist))))
           (idx-permutations (current rest)
             (setf (aref *path-matrix* current current) 0)
             (when rest
               (dolist (idx rest)
                 (let ((dist (gen-dist)))
                   (setf (aref *path-matrix* current idx) dist
                         (aref *path-matrix* idx current) dist)))
               
               (idx-permutations (car rest) (cdr rest)))))
    (let (idxs)
      (dotimes (i (length *towns*))
        (push i idxs))
      (setf idxs (nreverse idxs))
      (idx-permutations (car idxs) (cdr idxs)))))

(defun salesman-problem (&rest towns)
  (assert (not (set-difference towns *towns*)) ()
          "don't know about these towns ~a" (set-difference towns *towns*))
  (labels (;; distance between two towns
           (dist (from to)
             (aref *path-matrix* from to))
           ;; nearest town according to heuristics
           (nearest-town (from candidates)
             (car (sort (copy-list candidates)
                        #'(lambda (a b) (< (dist from a) (dist from b))))))
           (find-path (town candidates)
             (if (not candidates)
                 nil ; last town
                 (let ((next (nearest-town town candidates)))
                   (cons next (find-path next (delete next candidates)))))))
    (let* (;; town indexes in *path-matrix*
           (idxs (mapcar #'(lambda (town) (position town *towns*)) towns))
           ;; starting here
           (from-idx (car idxs))
           ;; result path in indexes
           (idx-path (cons from-idx (find-path from-idx (cdr idxs))))
           ;; path length
           (path-len (apply #'+
                            (maplist
                             #'(lambda (path)
                                 (dist (car path) (or (cadr path) from-idx)))
                             idx-path)))
           ;; path in town's names
           (town-path (mapcar #'(lambda (idx) (elt *towns* idx))
                              idx-path)))
      (values town-path path-len))))

CL-USER> (fill-path-matrix 100)
CL-USER> *path-matrix*
#2A((0 55 16 98 9 24)
(55 0 76 47 12 7)
(16 76 0 52 22 26)
(98 47 52 0 98 25)
(9 12 22 98 0 19)
(24 7 26 25 19 0))
CL-USER> (salesman-problem 'a 'b 'c 'f)
(A C F B)
104

Автор: Andrey1 7.12.2005, 22:54

Цитата(AntonSaburov @ 5.12.2005, 14:13)

Видимо здесь нет людей, которые пишут на LISP (ну не популярный это язык)

Я пишу. Редко, мало, но пишу.
Насчет популярности... уверен, что популярная система Mathematica Вам тоже кажется непопулярной.

Цитата(Guest @ 3.12.2005, 00:00)

Какие Вы здесь все вредные

Да... рожа смайлика с табличкой - на самом деле улыбающаяся.
А вот если бы Вы, мадмуазель, спросили что-нибудь конкретное, а не литоргический вопрос "сделайте за меня мою работу, пожалуйста", то может даже мне тут не пришлось выставлять смайлики с табличками... smile

Да, и подскажите миссис, как удалить тему!.. smile