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

https://forum.sources.ru/index.php?showtopic=421287&view=findpost&p=3850933