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