ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Shmidt                     2:464/34.74    19 Feb 2002  19:35:14
 To : All
 Subject : Вроде и не коммивояжер...
 -------------------------------------------------------------------------------- 
 

       ><  Е  ><  Е  ><   Хау, бледнолицый  All!   ><  Е  ><  Е  ><
 
     (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
 
 И еще задачка:
 Дан граф. Пройтись по всем вершинам, причем первая вешина задана, но
 возвращаться в нее не надо.
 
 Идея:
 Жадно посоединять все вершины кроме первой, чтоб получилась незамкнутая цепь, а 
 потом пробовать соедиянять первую вершину с ее концами (тут понятно и без
 рисунка), а также с вершиной, ближайшей к первой (предварительно соединив цепь в
 цикл и пробуя разрезать цепь в соответствующих местах, см рис.).
 
 Hапример, было:
 
 ----------------------------------
 1
 
     -------------\
    |             |
    \             |
     \           /
      \         /      \      /
 ------------------------------------- 
 Стало:
 (первая попытка)
 --------------------------------------
 1
   \
    |             \
    |             |
    \             |
     \           /
      \         /      \______/
 ------------------------------------------
 
 (вторая)
 -------------------------------------------
 1
   \
     -------------\
                  |
    \             |
     \           /
      \         /      \______/
 ----------------------------
 Опять же, ненравится мне все это.
 
 К тому же, надо ИМХО как-то по-другому находить ту самую "лучшую" цепь...
 Good bye, mister All                            _
                                                /_|  _  _    _/
                                      Smith,   (  | (/ (- /) /   Smith...
                                                  _/
 ... Ромеро будет жить еще долго, а вот Билли должен уме-е-ереть!
 --- А у твоего ГолДеда стоит... фильтрация мессаг???
  * Origin: Телепузик спать ложится - программист за комп садится. (2:464/34.74)
 
 

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

Тема:    Автор:    Дата:    Вроде и не коммивояжер...   Alexander Shmidt   19 Feb 2002 19:35:14   Re: Вроде и не коммивояжер...   Sergey Politov   20 Feb 2002 06:29:59