ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg Khovayko [SPAM trap - don't re  2:5020/400     08 Jul 2003  07:07:59
 To : Alexander Kurov
 Subject : Re: NEED:алгоpитм
 -------------------------------------------------------------------------------- 
 

 Так... Что-то никто не отвечает...
 
 Ладно, попробую высказать мои соображения на тему алгоритма.
 Сразу предупреждаю - не факт, что алгоритм точно работоспособен.
 Hе кодировал, не проверял.
 Возможно, надо что-то доделывать. Hо на первый взгляд вроде как
 выглядит нормально. Если кто опровергнет - скажу спасибо.
 
 Итак:
 
 Alexander Kurov wrote:
 
 > объясните на пальцах алгоpитм pешения данной задачи.
 
 Идея следующая:
 
 Представим граф, где узлы графа - косточки домино, а дуги вяжут
 всевозможные соединения через одинаковую цифру.
 Пример: есть набор костей:
 5:4, 3:5, 3:6, 5:2, 2:2, 1:1
 
 Вяжем из них граф:
 
 NIL--(6:3)--(3:5)+--(5:4)--NIL
                   +--(5:2)--(2:2)--NIL
 
 NIL--(1:1)--NIL
 
 теперь делаем так:
 для каждой косточки алгоритмом Дейкстры
 (обобщение волнового алгоритма для поля с переменной ценой шага)
 пускаем волну во все стороны, закрашивая пройденые клетки.
 Как только волна не может распространяться дальше
 (нарвалась на еще один NIL или же дальше все косточки - закрашеные)
 - приехали.
 
 Из всех начальных косточек выбираем ту, которая привела к минимальному
 расходу очков доминюшек.
 
 Все.
 
 -- 
 #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)
 
 

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