|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ivan Boldyrev 2:5080/1003 29 Jan 2003 02:12:15
To : Vitaly Lugovsky
Subject : Re: Урощение формул
--------------------------------------------------------------------------------
"VL" == Vitaly Lugovsky writes:
VL> Ivan Boldyrev <boldyrev@dataeast.ru> wrote:
>> VL> NP-полная - решение расположено где-то на БЕСКОHЕЧHОМ дереве, и
>> VL> требуется полный обход его. Однако, имея некоторые эмпирические
>> VL> правила, мы можем найти более-менее хорошее решение, обходя лишь
>> VL> часть дерева.
>>
>> Скажи, а в задаче коммивояжёра -- "найти кратчайший цикл, проходящий
>> через все вершины полносвязного взвешенного графа" -- тоже бесконечное
>> дерево решений? С учётом того, что количество вообще всех циклов в
>> любом конкретном конечном графе конечно?
VL> Число путей от вершины к вершине - конечно. А вот число форм,
VL> тождественных заданной - бесконечно. 1 = 2-1 = 3-2 = 10^2/100 =
VL> ..., и всё такое.
Вопрос был у Vladislavа Terehovа -- что такое NP-полнота. Ты
определил понятие NP-полноты через бесконечное дерево. Я опроверг.
Hечего первокурсникам мозги пудрить :)
--
Ivan Boldyrev
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673
Силикон -- это волшебное вещество, которое делает
компьютеры умными, а женщин -- пышногрудыми.
--- ifmail v.2.15dev5
* Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
