[задача коммивояжера] есть у кого в заначке программа?

матрица из 31 городов

я в 1998 году до 50-ти узлов считал на персоналке.
Сейчас это вообще раз плюнуть должно быть - без всяких генетических алгоритмов.

http://tsp.r-forge.r-project.org/

Если всего 31 город, то может легче все варианты перебрать?

Стоимость пути 98

Ребра которые нужно пройти (неотсортированно):

10 28
4 19
2 11
23 9
0 3
17 29
29 10
7 27
27 26
9 24
22 8
3 21
20 4
21 20
5 30
18 5
19 18
6 16
16 17
30 6
1 13
13 15
26 1
14 0
12 2
15 12
11 14
28 25
8 23
24 7
25 22

Метод ветвей и границ, если надо, могу выложить код.

>Если всего 31 город, то может легче все варианты перебрать?

30! - это очень много.

>Стоимость пути 98

Спасибо! Можешь прогнать для случая, когда надо выйти из города под номером 1 и вернуться в него же?

>Метод ветвей и границ, если надо, могу выложить код.

Давай, если не жалко )

>Можешь прогнать для случая, когда надо выйти из города под номером 1

Решение задачи — цикл, выходить можно из любого города.

Посмотри, может чем поможет.

http://pastebin.kde.org/75745/

Формат входных данных: число городов, дальше матрица. Всё через пробелы.

спасибо. буду мучать )

Алгоритм Литтла если точнее. Нагуглил то описание, которое нам раздавали на практиках: http://revolution.allbest.ru/mathematics/00366455_0.html

Есть свои подводные камни у алгоритма, например если невнимательно читать описание, можно получить не один большой цикл, а несколько более маленьких.

У меня получился один из вариантов длиной 92:

Ты уверен, что 98 правильно, или я где-то напортачил?

Обход узлов:

1 15 3 13 12 4 22 5 21 20 6 19 31 7 17 18 11 30 29 26 10 9 23 25 8 28 27 2 14 16

Я в этом списке чего-то 24 города не вижу.

точно. Натупил я.

Теперь тоже 98 время от времени вылазит. Но все же еще нестабильно.

Популяция быстро вырождается. Приходится коэффициент мутации на 0.8 задирать.

А там разве не «отжиг» используется? Типа сначала мутации большие, а потом уменьшаются.

>А там разве не «отжиг» используется? Типа сначала мутации большие, а потом уменьшаются.

У меня и без отжига вырождается )

Да и тем более, что динамическое изменение коэффициента мутаций - это улучшение исходного алгоритма. Но просто так его уменьшать наобум нельзя.