Задача коммивояжера (Страница 1 из 2)

Конечно спасибо. Но к сожалению в теории я знаю как решить. Как сделать эту задачку на практике, да еще и на  Lisp, вот в чем вопрос. Поэтому очень прошу тех кто разбирается в этом написать решение. Очень очень надо!!!!

Я рада, что хоть кто-то решил эту задачу на Лисп. Но совершенно не понимаю, что значит "совместно с мап". Очень хотелось бы посмотреть на решение, можно (что от меня требуется)?

> Стас

> Eli
Скачал ,не помню где,эту програму. Может Вам подойдёт.
Readme
Демо-версия программы GMC (задача коммивояжёра) для числа пунктов
не более 40 определяет минимальный путь обхода и выводит последо-
вательность номеров и координат пунктов, начиная с 1 в командную
строку. Запуск командой KOML40.
Более подробное описание по адресу www.kmtn.ru/~regul.
Набиуллин Р.Р.
regul@kmtn.ru

Игорь рекламирует деревообрабатывающие станки...

> Eli
Я смогу не раньше понедельника(28 ноября) с Вами разобраться. :)

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

--- d12 d13 d14 d15
d21 --- d23 d24 d25
d31 d32 --- d34 d35
d41 d42 d43 --- d45
d51 d52 d53 d54 ---

где d12 - расстояние от города 1 до города 2, соответственно d12=d21 (или нет?).
Для LISPа естественным было бы представить матрицу расстояний в виде:

((nil d12 d13 d14 d15)
 (d21 nil d23 d24 d25)
 (d31 d32 nil d34 d35)
 (d41 d42 d43 nil d45)
 (d51 d52 d53 d54 nil))

nil обозначает, что расстояние до текущего города не определено.
Теперь предположим, что коммивояжер находится в городе 1. Для движения в следующий город ему следует найти минимум из чисел в "хвосте" (cdr) первой строки матрицы расстояний. Допустим, что таковым оказалось расстояние до города номер 4 - d14:

nil d12 d13{d14}d15
d21 nil d23 d24 d25
d31 d32 nil d34 d35
d41 d42 d43 nil d45
d51 d52 d53 d54 nil

Идея заключается в том, чтобы перенумеровать оставшиеся города (за исключением текущего и уже пройденных) так, чтобы ближайший город оказался по номеру вслед за текущим.
Для матрицы расстояний эта операция представляет собой перестановку строк (при этом "первая" (то есть следующая за номером текущего города) строка становится последней, и так необходимое количество раз):

nil d12 d13{d14}d15
d41 d42 d43 nil d45
d51 d52 d53 d54 nil
d21 nil d23 d24 d25
d31 d32 nil d34 d35

Так как города перенумерованы, следует переставить и столбцы столько же раз и таким же образом, как до того строки:

nil d12 d13 d14 d15
d41 [b]nil{d45}d42 d43[/b]
d51 [b]d54 nil d52 d53[/b]
d21 [b]d24 d25 nil d23[/b]
d31 [b]d34 d35 d32 nil[/b]

Так как в 1-ый город возвращаться из бывшего 4-го, а ныне 2-го пока нельзя, на следующем этапе действия повторяются для меньшей матрицы (выделена жирным шрифтом) и так далее, пока матрица не кончится.
Функция COMMI_ROUTE принимает матрицу расстояний, например

(setq M5 '((nil 10 8 13 30)
           (10 nil 14 20 12)
           (8 14 nil 5 15)
           (13 20 5 nil 6)
           (30 12 15 6 nil)))

и перечень городов, например

(setq P '(1 2 3 4 5))

либо

(setq P '("1" "2" "3" "4" "5"))

и возвращает маршрут движения (но только без повторения в конце наименования первого города):

(defun COMMI_ROUTE (_dist_matrix _path)
 (if _dist_matrix
  (cons
   (car _path)
   (apply 'COMMI_ROUTE
    (apply
    '(lambda (_count)
      (list
       (COL_SWAP (mapcar 'cdr (ROW_SWAP (cdr _dist_matrix) _count)) _count)
       (ROW_SWAP (cdr _path) _count)))
     (list
      (apply
      '(lambda (_dist_list)
        (-
         (length _dist_list)
         (length (member (apply 'min _dist_list) _dist_list))))
       (list (cdr (car _dist_matrix))))))))))

Функция ROW_SWAP принимает список (например, строк матрицы расстояний) и счетчик и переставляет элементы списка указанным выше способом:

(defun ROW_SWAP (_list _count)
 (if (> _count 0)
  (ROW_SWAP (append (cdr _list) (list (car _list))) (1- _count))
  _list))

Функция COL_SWAP принимает список списков (например, строк матрицы расстояний) и счетчик и переставляет первые элементы каждого списка в конец соответствующего списка указанным выше способом:

(defun COL_SWAP (_list _count)
 (if (> _count 0)
  (COL_SWAP (mapcar 'append (mapcar 'cdr _list) (mapcar 'list (mapcar 'car _list))) (1- _count))
  _list))

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

(apply 'min '(1 2 nil 4 5))

невыполнимо.
Но если создать и применить функцию, способную "сократить" в списке nil-элементы, например:

(apply 'min ([i]f[/i] '(1 2 nil 4 5)))

то программу можно будет применять и для случаев "бездорожья".
К сожалению, рассказать,

проблематично, ибо в отличие от BASICа операторов и "строк" в LISP-программе нет, а есть только вызовы функций, необходимость которых и была вкратце разъяснена выше. Разумеется, ответы на дальнейшие вопросы последуют незамедлительно.

Потерял две строчки в последней функции

;; кратчайший путь
; num - номер пункта в списке карты
; num - номер пункта в списке сети
(defun mini-way (num lst)
 (apply 'min
    (apply '+
(mapcar (function (lambda (x)
(mapcar (function (lambda (q p)
            (distance q p)))
    x (cdr x))))
(vl-remove-if (function (lambda (z)
    (eq (car (nth (1- num) lst)) (car z))))        
(combo-list lst))))))

~'J'~

Согласно > Eli (2005-11-21 23:49:47)

Согласно http://www.erudition.ru/referat/ref/id.45585_1.html

(п.1.2.1).
Однако

Итак, достаточен ли работающий эвристический "жадный" алгоритм? Дождемся ответа от автора задания. По указанному выше адресу есть описания нескольких алгоритмов, над реализацией которых тоже можно поковыряться.
Пока - "блок-схема" реализации жадного алгоритма:

(defun COMMI_ROUTE (_dist_matrix _path)
 (if _dist_matrix ; пока матрица не сократилась до (nil)
  (cons ; присоединить
   (car _path) ; первый элемент из оставшегося списка городов
   (apply 'COMMI_ROUTE ; к результату выполнения той же функции над
    (apply
    '(lambda (_count)
      (list
       (COL_SWAP (mapcar 'cdr (ROW_SWAP (cdr _dist_matrix) _count)) _count) ; сокращенной матрицей с переставленными строками и элементами
       (ROW_SWAP (cdr _path) _count) ; и укороченным списком городов с переставленными названиями
      )
     )
     (list ; а это вычисление
      (apply
      '(lambda (_dist_list)
        (-
         (length _dist_list)
         (length (member (apply 'min _dist_list) _dist_list))))
       (list (cdr (car _dist_matrix)))
      )
     ) ; количества перестановок
    )
   )
  )
 )
)

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

Извиняюсь конечно, мы с lambda не работали, поэтому вопрос: при проверке работы программы я ввожу   (print (COMMI_ROUTE '((0 3 9 8 7)
(3 0 8 5 4) (9 8 0 3 7) (8 5 3 0 4) (7 4 7 4 0) ) '(1 2 3 4 5)))
и выдается ошибка ***- APPLY: argument
(lambda (_dist_list)
  (-(length _dist_list)
  (length (member (apply 'min _dist_list) _dist_list))))  is not a function.
To get a function in the current environment, write (function ...).
To get a function in the current environment, write (function ...).
To get a function in the global environment, write (coerce '...' function).
Что это такое и как работать с lambda.

Кстати, как называется реализация языка в вашем учреждении? А то приглядевшись выяснилось, что в конструкции функции (defun) есть некий "сюрприз". Снова процитируем Хювёнена-Сеппянена (раздел 2.5 стр.109):

Оказывается, что в данной реализации никакого исключения и сокращения нету.
Придется модифицировать текст:

(defun COMMI_ROUTE (lambda (_dist_matrix _path)
 (if _dist_matrix
  (cons
   (car _path)
   (apply 'COMMI_ROUTE
    (apply
     (function
      (lambda (_count)
       (list
        (COL_SWAP (mapcar 'cdr (ROW_SWAP (cdr _dist_matrix) _count)) _count)
        (ROW_SWAP (cdr _path) _count))))
     (list
      (apply
       (function
        (lambda (_dist_list)
         (-
          (length _dist_list)
          (length (member (apply 'min _dist_list) _dist_list)))))
       (list (cdr (car _dist_matrix)))))))))))
(defun ROW_SWAP (lambda (_list _count)
 (if (> _count 0)
  (ROW_SWAP (append (cdr _list) (list (car _list))) (1- _count))
  _list)))
(defun COL_SWAP (lambda (_list _count)
 (if (> _count 0)
  (COL_SWAP (mapcar 'append (mapcar 'cdr _list) (mapcar 'list (mapcar 'car _list))) (1- _count))
  _list)))

Попробовала запустить программу от
(2005-12-05 00:56:43). Но выдается ошибка APPLY: too few arguments given to MIN.

У нас выражение

(apply 'min '())

вычисляется в 0. Ежели у вас это выражение не вычисляется, то попробуем обходной вариант:

(defun COMMI_ROUTE (lambda (_dist_matrix _path)
 (if _dist_matrix
  (cons
   (car _path)
   (apply 'COMMI_ROUTE
    (apply
     (function
      (lambda (_count)
       (list
        (COL_SWAP (mapcar 'cdr (ROW_SWAP (cdr _dist_matrix) _count)) _count)
        (ROW_SWAP (cdr _path) _count))))
     (list
      (SWAP_COUNT (cdr (car _dist_matrix))))))))))
(defun ROW_SWAP (lambda (_list _count)
 (if (> _count 0)
  (ROW_SWAP (append (cdr _list) (list (car _list))) (1- _count))
  _list)))
(defun COL_SWAP (lambda (_list _count)
 (if (> _count 0)
  (COL_SWAP (mapcar 'append (mapcar 'cdr _list) (mapcar 'list (mapcar 'car _list))) (1- _count))
  _list)))
(defun SWAP_COUNT
 (lambda (_dist_list)
  (if _dist_list
   (-
    (length _dist_list)
    (length (member (apply 'min _dist_list) _dist_list)))
   0)))

Функция SWAP_COUNT вычисляет количество перестановок строк и столбцов.