Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.216.32.116] |
|
Сообщ.
#1
,
|
|
|
Помогите пожалуйста, написать программу на 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 – |
Сообщ.
#2
,
|
|
|
А где Ваши наработки-то? в чём именно проблема, в какой точке затык?
А тому, кто сам ничего не делает, можно только помочь ничего не делать, знаете ли... |
Сообщ.
#3
,
|
|
|
Эх, жалко, что я эту тему так поздно обнаружил (надо почаще на форум заходить).
Наверное, тема уже не актуальна, но я отвечу тем не менее. 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 задача коммивояжера точно может быть решена только методом ветвей и границ (МВГ). При этом вероятность нахождения точного решения меньше единицы - а иначе ЗК не была бы труднорешаемой. В любом случае оценить среднюю точность метода Монте-Карло можно только путем сравнения его решения с решением МПП, МДП и МВГ. Разумеется, программы МПП, МДП и МВГ писать существенно сложнее, чем программу метода Монте-Карло. |