ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Shmidt                     2:464/34.74    28 Mar 2002  23:34:40
 To : Sergey Politov
 Subject : UOI2001
 -------------------------------------------------------------------------------- 
 

       ><  Е  ><  Е  ><   Хау, бледнолицый  Sergey!   ><  Е  ><  Е  ><
 
     (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
 
  Эй, уважаемые Sergey Politov и Alexander Shmidt! Что за "Re: UOI2001", а где же
 яйца?!
 
  AS>> Вершин, как обычно, - <=100. Веса ребер <=300 (шоб в integer
  AS>> влезли, надо полагать; хотя это, имхо, не принципиально) Есть
  AS>> идея построить "лучший" вариант, а потом покантовать
  AS>> (ребра поразрезать-подорисовывать). Или придется по всем ребрам
  AS>> полученного "лучшего" решения пройтись, и, удаляя ребро, решать
  AS>> задачу заново. После чего сравнить результаты этих (n-1)
  AS>> проходов.
  SP> Вообще я это и хотел предложить только удалив ребро не забывай его
  SP> вернуть.
 
 Hу, само собой.
 
  AS>> Прим-Краскал, если меня не глючит, имеет сложность O(n^3). Тогда
  AS>> конечный алгоритм будет О(n^4). Что народ скажет?
  SP> А вообще Краскал имеет сложность O(ElogE), или оценив E<V^2,
  SP> O(V^2log(V)), но лагирифм получается из за сортировки, а тут можно не
  SP> соритровать по несколько раз поэтому сложность получится O(V^3).
 
 Отсортировать один раз - неплохая идея. Как-то сразу не пришло в голову. Ж)
 
 А я тут родил еще такую штуку:
 При построении лучшего решения запоминаем ситуации, при которых мы взяли каждое 
 из ребер, а потом, при проходе, выбрасывая ребро, восстанавливаем ситуацию,
 которая была до того, как мы его взяли (очевидно, что мы с полным правом можем
 это сделать) и только потом запускаем Краскала, чтоб он "доработал" уже готовый 
 результат.
 
 {Это, конечно, уменьшит время, но для общего развития хочется сложность
 посчитать. В уме получается только, что при проверке вместо O(n*n) имеем
 ((n/2)*(n/2)), константу выбрасываем, имеем - O(n*n), то есть имеем чисто
 технический плюс во времени. Hичего не перепутал?}
 
 Это мы получили вариант, используя то построение, которое было _до_того_ как мы 
 взяли ребро. А то же самое для остальной части дерева, построенного при
 нахождении лучшего решения, нельзя сделать?
 
 Good bye, mister Politov                        _
                                                /_|  _  _    _/
                                      Smith,   (  | (/ (- /) /   Smith...
                                                  _/
 ... Вся жизнь - игра, а юниты в ней - люди
 --- А у твоего ГолДеда стоит... фильтрация мессаг???
  * Origin: Без модема и ФИДЫ - ни туды и ни сюды! (2:464/34.74)
 
 

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

Тема:    Автор:    Дата:    UOI2001   Alexander Shmidt   24 Mar 2002 01:35:56   Re: UOI2001   Sergey Politov   26 Mar 2002 06:36:10   UOI2001   Alexander Shmidt   26 Mar 2002 23:23:12   Re: UOI2001   Sergey Politov   28 Mar 2002 06:19:55   UOI2001   Alexander Shmidt   28 Mar 2002 23:34:40   Re: UOI2001   Sergey Politov   29 Mar 2002 06:21:58   UOI2001   Alexander Shmidt   29 Mar 2002 23:22:00   Re: UOI2001   Sergey Politov   31 Mar 2002 04:40:41   UOI2001   Alexander Shmidt   31 Mar 2002 13:56:48