На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
  
> Задача коммивояжера методом Монте-Карло, написать программу на C++
    Помогите пожалуйста, написать программу на 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 –
      А где Ваши наработки-то? в чём именно проблема, в какой точке затык?

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

        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 задача коммивояжера точно может быть решена только методом ветвей и границ (МВГ). При этом вероятность нахождения точного решения меньше единицы - а иначе ЗК не была бы труднорешаемой.
        В любом случае оценить среднюю точность метода Монте-Карло можно только путем сравнения его решения с решением МПП, МДП и МВГ. Разумеется, программы МПП, МДП и МВГ писать существенно сложнее, чем программу метода Монте-Карло.
        Сообщение отредактировано: mkudritsky -
        1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
        0 пользователей:


        Рейтинг@Mail.ru
        [ Script execution time: 0,0180 ]   [ 17 queries used ]   [ Generated: 28.09.21, 18:01 GMT ]