Реализовать алгоритм решения задачи коммивояжера

@Zaruboka · Регистрация: 16.11.2012

Студворк — интернет-сервис помощи студентам

дали задание: Реализовать алгоритм решения задачи коммивояжера.
честно говоря, даже не знаю с какой стороны подойти. Гамильтонов цикл? тогда каким поиском?

@Catstail · 18.11.2012, 15:17

Серьезная задача...

@Zaruboka · 18.11.2012, 18:54 **[ТС]**

Может быть алгоритм с возвратом? рекурсивно его описать..

@Zaruboka · 03.12.2012, 22:02 **[ТС]**

Нашла код, алгоритм с возвратом. при проверке выдает следующее:
Error: Non-symbol (GRAPH) used as variable name in function HAMILTCYCLE.
как исправить??

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
(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 '((A . (F D C)) (F . (E D A B)) (E . (D F B)) (D . (E F A)) (C . (A B)) (B . (F E C))))

@Catstail · 04.12.2012, 22:48

После элементарной переделки под совр. Лисп (просто убрал LAMBDA и скобки) программа в HomeLisp сразу заработала:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
(DEFUN HAMILTCYCLE (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)
                              )
                        )
                  )
            )
      )
   )
 
==> HAMILTCYCLE
 
   (DEFUN HC (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))) )) )
                  )
            )
      )
   )
 
==> HC
   ;; ------------------------------- ;
   (DEFUN NEIGHBOUR3 (X GRAPH)
      (COND ( (NULL (ASSOC X GRAPH)) NIL )
            (  T  (CDR (ASSOC X GRAPH)) )
      )
   )
 
==> NEIGHBOUR3
 
(HAMILTCYCLE '((A . (F D C)) (F . (E D A B)) (E . (D F B)) (D . (E F A)) (C . (A B)) (B . (F E C))))
 
==> (a f d e b c)

@Zaruboka · 06.12.2012, 20:47 **[ТС]**

даа.. краснею от стыда..
спасибо!!

@Catstail · 06.12.2012, 23:19

Не стоит краснеть. Все ошибаются... Важна не ошибка сама по себе, а отношение к ней.

@Eva_19 · 09.10.2014, 10:48

Catstail, А возможна ли доработка алгоритма с целью минимизации пройденного расстояния, если дана матрица расстояний между городами (если между городами нет прямой дороги - соответствующее значение -1)?

@Catstail · 09.10.2014, 12:09

Eva_19, надо подумать...

Cheb · 10.10.2014, 15:43

Это логистика ведь? подписываюсь на тему, тоже интересно, такое тоже надо реализовать.

@Vtulhu · 16.10.2014, 18:49

Мне такие задачи нравится решать с помощью генетических/эволюционных алгоритмов. Лучшее решение они не гарантируют, но довольно быстро находят "почти лучшие" и с течением времени их улучшают. В Википедии сказано, что решение задачи коммивояжера даже для нескольких десятков городов потребует миллиарды лет расчетов на современном компьютере. Согласитесь, что получить за несколько часов решение, входящее, скажем, в 20% лучших, а за несколько дней - в 10% лучших - это очень хорошая альтернатива миллиарду лет ожидания...

@Eva_19 · 09.11.2014, 23:22

Нашла интересную программу...

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(defun commy-find-shortest-road (route roads)
  (let (next-hop (distance most-positive-double-float))
    (dotimes (road-num (length roads))
      (when (and (not (member road-num route))
                 (< (nth road-num roads) distance))
        (setq next-hop road-num
              distance (nth road-num roads))))
    next-hop))
 
(defun commy-step (route roadmap)
  (if (= (length route) (length roadmap))
      route
    (let* ((current-town (car route))
           (current-roads (nth current-town roadmap))
           (next-hop (commy-find-shortest-road route current-roads))
           )
      (push next-hop route)
      (commy-step route roadmap))))
 
(defun commy-route (roadmap)
  (reverse (commy-step '(0) roadmap)))

@Catstail · 09.11.2014, 23:28

Сообщение от Eva_19

Нашла интересную программу...

- только она, боюсь, неполная...

@Eva_19 · 11.11.2014, 10:44

А можете подсказать, что надо доделать?

@Eva_19 · 01.12.2014, 18:53

Подскажите, пожалуйста, как сюда добавить вычисление расстояния между конечным городом и городом, откуда коммивояжер вышел?

@Catstail · 01.12.2014, 19:42

Eva_19, покажите, как вы ее запускали.

@Eva_19 · 01.12.2014, 20:08

Catstail, последовательно каждую функцию запускала

Добавлено через 6 минут

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
CL-USER 1 > (DEFUN HAMILTCYCLE (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)
                              )
                        )
                  )
            )
      )
   )
HAMILTCYCLE
 
CL-USER 2 > (DEFUN HC (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))) )) )
                  )
            )
      )
   )
HC
 
CL-USER 3 > (DEFUN NEIGHBOUR3 (X GRAPH)
      (COND ( (NULL (ASSOC X GRAPH)) NIL )
            (  T  (CDR (ASSOC X GRAPH)) )
      )
   )
NEIGHBOUR3
 
CL-USER 4 > (HAMILTCYCLE '((A . (F D C)) (F . (E D A B)) (E . (D F B)) (D . (E F A)) (C . (A B)) (B . (F E C))))
(A F D E B C)

@Catstail · 01.12.2014, 20:51

Eva_19, смотрю...

Добавлено через 3 минуты
Код рабочий.

Добавлено через 5 минут

Сообщение от Eva_19

Подскажите, пожалуйста, как сюда добавить вычисление расстояния между конечным городом и городом, откуда коммивояжер вышел?

- если коммивояжер вышел из первого города, а все ребра графа имеют одинаковую длину (1), то длина пути будет равна просто длине результирующего списка вершин+1.

Lisp
1
2
3
4
5
6
7
8
(defun len-hamilt-path (graph)
  (+ 1 (length (hamiltcycle graph))))
 
==> len-hamilt-path
 
(len-hamilt-path '((A . (F D C)) (F . (E D A B)) (E . (D F B)) (D . (E F A)) (C . (A B)) (B . (F E C))))
 
==> 7

Добавлено через 4 минуты
А расстояние между начальным и конечным городом = длине списка. Другое дело, если расстояния между городами разное. Тогда нужно задать список длин путей. Например в виде:

Lisp
1
((a f 1) (a d 3) (a c 2) (f e 4) (f d 2) (f b 5) (e d 3) (e b 1) (c b 4) (b f 3))

Добавлено через 16 минут
Вот вычисление длины пути без последнего ребра:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(defun get-lenv (a b lens)
  (cond ((or (and (eq a (caar lens))
                  (eq b (cadar lens)))
             (and (eq b (caar lens))
                  (eq a (cadar lens)))) (caddar lens))
        (t (get-lenv a b (cdr lens)))))
 
(defun len-path (hc lens)
  (cond ((null (cdr hc)) 0)
        (t (+ (get-lenv (car hc) (cadr hc) lens) (len-path (cdr hc) lens)))))
 
(defun task (graph lens)
  (let ((hc (hamiltcycle graph)))
    (len-path hc lens)))
    
(task '((A . (F D C)) (F . (E D A B)) (E . (D F B)) (D . (E F A)) (C . (A B)) (B . (F E C)))
      '((a f 1) (a d 3) (a c 2) (f e 4) (f d 2) (f b 5) (e d 3) (e b 1) (c b 4) (b f 3)))
 
==> 11

@Eva_19 · 02.12.2014, 15:14

Понятно, спасибо большое)

Добавлено через 17 часов 7 минут
Пока разбиралась в коде, столкнулась с одним вопросом. Что делает эта функция? Ищет соседние вершины для заданной в графе(мое предположение)?

Lisp
1
2
3
4
5
(defun neighbor (x graph)
      (cond ((null (assoc x graph)) nil)
            (T (cdr (assoc x graph))
      )
   ))

@Catstail · 04.12.2014, 11:19

Eva_19, да, Ваше предположение верное. Функция assoc ищет в ассоциативном списке пару
(x . вершины_связанные_с_x). Если пара не найдена, возвращается nil. Иначе возвращается список вершин, связанных с x. Функцию можно реализовать рациональнее (исключив двойное вычисление одного и того же):

Lisp
1
2
3
4
(defun neighbor (x graph)
  (let ((tmp (assoc x graph)))
      (cond ((null tmp) nil)
              (T (cdr tmp)))))

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@Zaruboka 0 / 0 / 0 Регистрация: 16.11.2012 Сообщений: 16

	Реализовать алгоритм решения задачи коммивояжера 18.11.2012, 11:35. Показов 3593. Ответов 19 Метки алгоритм, коммивояжера, реализовать, решения (Все метки) дали задание: Реализовать алгоритм решения задачи коммивояжера. честно говоря, даже не знаю с какой стороны подойти. Гамильтонов цикл? тогда каким поиском? 0

@Catstail Супер-модератор 38178 / 21113 / 4307 Регистрация: 12.02.2012 Сообщений: 34,716 Записей в блоге: 14
	18.11.2012, 15:17
	Серьезная задача... 0

@Zaruboka 0 / 0 / 0 Регистрация: 16.11.2012 Сообщений: 16
	18.11.2012, 18:54 [ТС]
	Может быть алгоритм с возвратом? рекурсивно его описать.. 0

@Zaruboka 0 / 0 / 0 Регистрация: 16.11.2012 Сообщений: 16
	06.12.2012, 20:47 [ТС]
	даа.. краснею от стыда.. спасибо!! 0

@Catstail Супер-модератор 38178 / 21113 / 4307 Регистрация: 12.02.2012 Сообщений: 34,716 Записей в блоге: 14
	06.12.2012, 23:19
	Не стоит краснеть. Все ошибаются... Важна не ошибка сама по себе, а отношение к ней. 0

@Eva_19 1 / 1 / 0 Регистрация: 20.07.2013 Сообщений: 64
	09.10.2014, 10:48
	Catstail, А возможна ли доработка алгоритма с целью минимизации пройденного расстояния, если дана матрица расстояний между городами (если между городами нет прямой дороги - соответствующее значение -1)? 0

@Catstail Супер-модератор 38178 / 21113 / 4307 Регистрация: 12.02.2012 Сообщений: 34,716 Записей в блоге: 14
	09.10.2014, 12:09
	Eva_19, надо подумать... 0

Cheb 92 / 59 / 8 Регистрация: 09.11.2011 Сообщений: 443
	10.10.2014, 15:43
	Это логистика ведь? подписываюсь на тему, тоже интересно, такое тоже надо реализовать. 0

@Vtulhu 431 / 385 / 200 Регистрация: 12.08.2011 Сообщений: 1,610
	16.10.2014, 18:49
	Мне такие задачи нравится решать с помощью генетических/эволюционных алгоритмов. Лучшее решение они не гарантируют, но довольно быстро находят "почти лучшие" и с течением времени их улучшают. В Википедии сказано, что решение задачи коммивояжера даже для нескольких десятков городов потребует миллиарды лет расчетов на современном компьютере. Согласитесь, что получить за несколько часов решение, входящее, скажем, в 20% лучших, а за несколько дней - в 10% лучших - это очень хорошая альтернатива миллиарду лет ожидания... 1

@Eva_19 1 / 1 / 0 Регистрация: 20.07.2013 Сообщений: 64
	11.11.2014, 10:44
	А можете подсказать, что надо доделать? 0

@Eva_19 1 / 1 / 0 Регистрация: 20.07.2013 Сообщений: 64
	01.12.2014, 18:53
	Подскажите, пожалуйста, как сюда добавить вычисление расстояния между конечным городом и городом, откуда коммивояжер вышел? 0

@Catstail Супер-модератор 38178 / 21113 / 4307 Регистрация: 12.02.2012 Сообщений: 34,716 Записей в блоге: 14
	01.12.2014, 19:42
	Eva_19, покажите, как вы ее запускали. 0