Re: коммивояжёр

From

Oleg Khovayko ()

To

Ilya Rogov

Date

2003-01-12T06:03:31Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Ilya Rogov wrote:

 >    Вот про генерацию всех возможных перестановок нерекурсивным 
способом я как
 > раз и хотел спросить.

Так как я пишу на C++, я при необходимости просто зову 
next_permutation(), и все делается за меня само собою.

Вам же, если вы используете PASCAL, надо самому сгенерить перестановки.
Вот я нашел в интернете описание генерации перестановок как раз 
применительно к комми-задаче:

<<<<<

  Чтож, сегодня я хочу предолжить вам программу, которая является более 
сложной, чем обычные задания и требудет определенной подготовки. Сам 
текст программы Вы найдете на сайте http://prog.agava.ru, в разделе 
Уроки для начинающих программистов >> Домашние задания. Извиняюсь за 
публикацию текста в разделе по ДЗ, пока не было времени сформировать 
отдельный раздел для исходных текстов.

     Итак, задача:

     Есть пять городов , А , Б , С , Д и Е. Известно что человек всегда 
выходит из города А , и обязательно должен пройти все оставшиеся города 
и попасть обратно в А. К примеру , Из А -> Б -> C->Д->E->A. То есть за 
исключением А , порядок посещения оставшихся четырех городов может 
меняться. То есть существует (5-1)! комбинаций. Как мне задать чтобы 
программа сама смогла их посчитать, а потом выдать наикратчайщий путь 
??? (таблица расстояний приводится ниже)...

     A B C D E
     A 0 85 117 163 489
     B 85 0 30 50 385
     C 117 30 0 27 322
     D 163 50 27 0 302
     E 489 385 322 302 0

     Начинаем решать:

     Одна из классических задач на комбинаторику.

     Для удобства будем нумеровать города по порядку 1 2 3 4 5. Нам 
нужно получить все цепочки вида 1 N1 N2 N3 N4 1, для каждой такой 
цепочки надо сосчитать путь по ф-ле 
S:=A[1,N1]+A[N1,N2]+A[N2,N3]+A[N3,N4]+A[N4,1]. Среди этих путей надо 
найти минимальный. Таким образом задача сводится к генерации всех 
перестановок в общем случае N-элементного множества (всего таких 
перестановок N!).
     Будем генерировать перестановки в алфавитном (лексикографическом 
порядке) первая перестановка 1 2 3 4, последняя 4 3 2 1.

     Порождение всех перестановок будем производить "по индукции". 
Предположим, что мы умеем порождать все перестановки из N-1 элемента. 
Тогда сначала сгенерируем все перестановки 2,...,N, приписывая к ним 
слева единицу. Затем сгенерируем все перестановки чисел 1,3,...,N, 
приписывая к ним слева двойку и т.д. Последним шагом будет генерация 
всех перестановок из чисел 1,...,N-1 c приписыванием к ним слева числа N.
     Из описанной процедуры вытекает, что каждая следующая перестановка 
получается из предыдущей таким образом. В "предыдущей" перестановке 
X[1],...,X[N] справа ищется наибольшая убывающая подпоследовательность 
X[i]>...>X[N] ( если рассматривать позиции, начиная с i-й, то это 
последняя перестановка чисел X[i],...,X[N]). Если i=1, то все 
перестановки были сгенерированы и последовательность сортируется по 
возрастанию (получаем первую перестановку). Иначе среди чисел 
X[i],...,X[N] выбирается наименьшее X[j], большее X[i-1], и ставится на 
позицию i-1, а все оставшиеся числа (и x[i-1] в том числе) сортируются 
по возрастанию.

     Сам исходный текст программы, как я уже сказал, см. на 
http://prog.agava.ru, в разделе Уроки для начинающих программистов >> 
Домашние задания. Программа сделана для N<=100. Читает данные из файла 
road.in, который имеет следующий формат: В первой строчке содержится 
число пунктов N, далее следует матрица расстояний N строчек по N чисел 
разделенных пробелами. Вывод производится в файл road.out.

     Советую перед тем, как скачать исходник попробовать сделать ее 
самостоятельно.
 >>>>>>>>>>>

 >    Что есть "бесперспективные" ??

Допустим, где-то программа находится в середине вычислений,
и уже нашла кратчайший (из всех ранее просмотреных) путь длиной
L. Очевидно, что если при вычислении текущего пути длина
некоего начального отрезка пути префикса уже превысила L,
то далее нет смысла рассматривать пути, начинающиеся с данного
префикаса, так как при любом дальнейшем присовокуплениии остальных
точек суффикса длина только вырастет, и всегда будет больше L.
Следовательно, все такие пути будут хуже ранее найденого, и
их можно не рассматривать. Этот фокус хорошо проходит при
рекурсивном "бурении", или же при использовании более умных методов
оптимизации, типа ранее упомянутого метода ветвей и границ.

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)