Здравствуйте!

Будьте добры, помогите решить такой вопрос:

Значит в разделе FAQ на сайте размещен текст программы для решения задачи коммивояжера методом простого перебора.
Программу я запускал - на текстовом примере размерностью матрицы 10*10 всё работает отлично.
На меньших размерностях вопросов тоже не возникает.
Но как только потребовалось решить матрицу 20*20 (30*30) программа зацикливается.

Текст программы находиться здесь, я в неё не вносил никаких изменений.

FAQ. Раздел Метод перебора.

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

Заранее благодарен за советы

Можешь прикрепить текстовый файл с матрицей, при обработке которой у тебя зависает программа?

конечно

Вот сразу же тебе и ошибка: нули убирай с диагонали матрицы, либо читай их тоже из файла, и только потом в элемент A[i, j] заноси MaxInt... Обрати внимание, в FAQ-е в файле данных нет нулей на главной диагонали, потому что там данные читаются вот так:

   for i:=1 to n do
      for j:=1 to n do
         if i=j then a[i,j]:=maxint { <-- Значение из файла НЕ читалось !!! } else read(a[i,j]);

.

Так ведь нули я пробовал удалить - результата это всё равно не дало.
И, кстати, из программы эту строчку я исправил чтобы из файла нолики читало.

up

Хм... Очень интересно. Вариант Гари Дарби для решения методом ветвей и границ на приведенной матрице выдает:

Running "f:\programs\pascal\__komm.exe"
1->2->9->12->4->5->14->7->8->18->10->3->6->20->13->19->15->11->17->16->1 = 221

Это правильный вариант? Потому что на примере из нашего FAQ-а задача им же решается неправильно:

Running "f:\programs\pascal\__komm.exe"
1->3->4->7->10->6->5->2->9->8->1 = 168

, в то время как программа virt-а выдает ответ = 158...

Попробую еще прогнать пару других программ, посмотрим, что они выдадут...

Спасибо Вам что помогаете докопаться до истины. Решить эту задачу методом ветвей и границ не пробовал.
Буду очень благодарен за наводку для решения задачи методом перебора, как задача Virt'а.

Спасибо ещё раз

Так... Программа работает, но ОЧЕНЬ долго. Учти, что при решении несимметричной задачи коммивояжера для N узлов (методом полного перебора) потребуется (n-1)! проходов. В твоем случае n = 20, значит число проходов будет равно 121645100408832000 (для матрица 10*10 из примера: 9! = 362880 проходов. Чувствуешь разницу?)

Так что решай задачу другим методом. Результата полного перебора на таких размерностях дождаться затруднительно.

Переход - в смысле "итерация"?



Да уж..Получается такой себе Brutal Force)..для мэйнфрейма.



Понятно..Я думал что это в программе ошибка какая-то, что она зацикливается, час ждал 20*20 - а она всё работает и работает.

Спасибо Вам большое за помощь, затраченное время и качественный ответ.