ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg Khovayko [SPAM trap - don't re  2:5020/400     30 Jul 2003  01:46:24
 To : Grebnov Ilya
 Subject : Re: Отыскание контуров фиксированной длины
 -------------------------------------------------------------------------------- 
 

 Grebnov Ilya wrote:
 
 > 
 >   Контуp - замкнутый оpиентиpованный маpшpут, в котоpом все дуги pазличны(
 > веpшины могут повтоpяться ).
 >   Дан оpиентиpованный гpаф, найти все сабжи.Помогите с алгоpитмом.
 По-моему, вот такой паровоз полетит (предполагается, что длина всех 
 путей более нуля):
 
 1. Создаешь структуру S с полями:
   1.1. Hомер исходного узла N1
   1.2. номер текущего узла N2
   1.3. Длина пройденого пути L
   1.4. Множество использованых дуг графа M
 (можно сделать битовым массивом)
 2. Создаешь приоритетную очередь Q из структур S.
 В качестве приоритета выбираешь 1.3 (L) по возрастанию.
 То есть элементы с наименьщей длиной пути идут в голову
 очереди.
 3. В цикле "для всех узлов графа" делать:
 3.1. Создать стркутуру 1:
 (cur_node_no, cur_node_no, 0, <EMPTY_SET>);
 3.2. Положить эту структуру в очередь Q.
 
 После шага 3 в очереди будет N структур, где N - число узлов
 в графе.
 4. Собственно вычисления.
 
 while(!Q.empty()) { // пока очередь не пуста
   S cur = Q.get(); // Взять очередную структуру из очереди.
 
   if(cur.L > заданая длина пути)
     continue; // Длина меньше быть уже не может, дальше не стоит рыпаться
 
   if(cur.L == заданая длина пути){
     if(cur.N1 == cur.N2) { Вывести найденый цикл (N1, M)}
     continue; // дальше опять-таки не стоит рыпаться
   }
 
   // Тут длина пути в cur менее заданой - можно копать дальше
 
   Цикл "Для всех дуг, исходящих из узла N2" делаем: {
     if(текущая дуга отсутствует в множестве cur.M) {
       S next = cur;
       добавим текущую дугу в множество next.M;
       next.N2 = номер узла на конце текущей дуги
       next.L += длина текущей дуги
       Q.put(next); // поставили элемент в очередь на обработку
     } // if
   } // для всех дуг
 
 } // while
 Время работы алгоритма в худшем случае пропорционально
 произведению количества узлов графа на искомую длину циклов.
 То есть грубо говоря - N * M;
 
 -- 
 #include <best/regards>
 Oleg Khovayko  http://olegh.spedia.net
 PS/ATTN: Reply to reverted address net.comcast@olegh
 
 --- ifmail v.2.15dev5
  * Origin: http://www.ftc.gov/opa/2001/04/spam.htm (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Отыскание контуров фиксированной длины   Grebnov Ilya   28 Jul 2003 21:07:54   Re: Отыскание контуров фиксированной длины   Oleg Khovayko [SPAM trap - don\'t re   30 Jul 2003 01:46:24