ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : andyc@nikom.tagil.ru                 2:5020/400     29 Jun 2001  13:31:56
 To : Aleksey Mashihin
 Subject : Re: help
 -------------------------------------------------------------------------------- 
 

 Приветствую, Aleksey!
 
 AM>   Может кто знает алгаритм нахождения пути , (рекурсия не интерисует)
 AM> для задачи типа : есть схема водопровода и есть краны у которых два
 AM> положения ОТКРЫТ или ЗАКРЫТ (т.е. вода дальше не идет) .  еобходимо найти
 AM> где есть вода , а где ее нет. 1 - отсюда течет вода |\ |  5---6---7 2-- |   
 AM> \ --3 | 4 Краны расположены в узлах (1,2,3,4,5,.. КРА Ы ) Если перекрыть 5
 AM> кран то в 6 и 7 уже не будет воды Если 1 закрыть то вообще нигде не будет
 AM> воды . Я использовал алгаритм Дейкстры, но он как-то не правильно работает  
 AM> Т.е. если есть схема типа 1--2--3--4 и перекрыть 3 кран, то он все
 AM> равно пишет что в 4 вода есть ! Если кто знает напишите плз. по работе надо,
 AM> там у меня есть карта города со схемой газопровода, и кранов будет около
 AM> 1000 так что рекурсия не покатит.
 
 попробуй по принципу ColorLines.
 используй либо двумерную карту, либо дерево.
 т.е.
 цикл от 0 до количество кранов
  цикл от 0 до количество кранов
   если в текущем кране есть вода, то если соседние не перекрыты, то
   вних тоже есть вода. (результат - в другую карту (дерево))
  конец цикла
  копируем созаднную крату в старую (меняем указатели)
 конец цикла
 
 можно еще проверить на наличие хоть одного перемещения воды по трубам
 и если таковых нету - заранее выходим из циклов.
 работало вроде-бы... хотя на больших картах достаточно долго
 Удачи
  ANDY Inc.                 
  andyc@nikom.tagil.ru
 -- 
 Отправлено через сервер Talk.Ru - http://www.talk.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.Ru (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    help   Aleksey Mashihin   28 Jun 2001 22:41:36   Re: help   andyc@nikom.tagil.ru   29 Jun 2001 13:31:56   help   Stanislav Shwartsman   29 Jun 2001 13:26:57   Re: help   andyc@nikom.tagil.ru   02 Jul 2001 07:18:02   help   Stanislav Shwartsman   29 Jun 2001 13:23:48   help   Aleksey Mashihin   01 Jul 2001 01:37:10   help   Stanislav Shwartsman   02 Jul 2001 15:31:39   help   Ivan Mak   29 Jun 2001 23:38:05   help   Aleksey Mashihin   01 Jul 2001 01:41:34   help   Ivan Mak   01 Jul 2001 16:43:31