Форум на Исходниках.RU

Задача коммивояжера методом Монте-Карло

mkudritsky — Sun, 15 Aug 2021 03:09:21 +0000

mkudritsky: Эх, жалко, что я эту тему так поздно обнаружил (надо почаще на форум заходить).
Наверное, тема уже не актуальна, но я отвечу тем не менее.

1. Написать программу решения задачи коммивояжера (ЗК) методом Монте-Карло очень просто.
Задаем для разомкнутой ЗК массив из N элементов по числу городов:
short Gor[N], PromG, indG;
В ячейки массива заносим номера городов:
for (int i = 0; i < N; i++)
Gor[i] = i;

2. Генерируем индекс первого города:
indG = rand() mod N;
Меняем местами города с индексами 0 и indG:
PromG = Gor[0]; Gor[0] = Gor[indG]; Gor[indG] = PromG;

3. Работаем со i-м городом (по аналогии с первым):
indG = (rand() mod (N - i)) + i;
Меняем местами города с индексами i и indG:
PromG = Gor[i]; Gor[i] = Gor[indG]; Gor[indG] = PromG;

4. Ну и так далее. По пунктам 1 и 2 уже цикл просматривается.
Таких маршрутов генерируется столько, сколько нужно и сколько не жалко - чем больше, тем лучше.
Запоминается маршрут с минимальной суммарной длиной пути коммивояжера.

P.S. Общие замечания по труднорешаемой комбинаторной задаче коммивояжера.
А. Если число городов N достаточно большое, то о повторении маршрутов при генерации можно не беспокоиться - вероятность такого события чудовищно низка.
Например, при N=100 общее число маршрутов примерно равно 10^158, что несравнимо больше, скажем, миллиарда генерируемых маршрутов (10^9) в методе Монте-Карло.
Б. А судьи кто? С чем сравнивать найденный "оптимум" методом Монте-Карло?
ЗК методом полного перебора (МПП) решается для числа городов N=13..14 не более.
ЗК методом динамического программирования (МДП) точно решается для числа городов порядка N=30. При этом потребуется ПК с памятью 32-64Гб и информацию надо хранить не в байтах, а в отдельных битах!
Ну и для числа городов более 30 задача коммивояжера точно может быть решена только методом ветвей и границ (МВГ). При этом вероятность нахождения точного решения меньше единицы - а иначе ЗК не была бы труднорешаемой.
В любом случае оценить среднюю точность метода Монте-Карло можно только путем сравнения его решения с решением МПП, МДП и МВГ. Разумеется, программы МПП, МДП и МВГ писать существенно сложнее, чем программу метода Монте-Карло.

Задача коммивояжера методом Монте-Карло

Akina — Mon, 29 Mar 2021 05:20:49 +0000

Akina: А где Ваши наработки-то? в чём именно проблема, в какой точке затык?

А тому, кто сам ничего не делает, можно только помочь ничего не делать, знаете ли...

Задача коммивояжера методом Монте-Карло

Forever_smile — Sat, 27 Mar 2021 15:30:45 +0000

Forever_smile: Помогите пожалуйста, написать программу на C++. Решить задачу коммивояжера методом Монте-Карло

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

N 1 2 3 4 5
1 – 6 60 48 12
2 5 – 10 80 100
3 140 150 – 12 70
4 96 120 70 – 6
5 18 9 24 90 –