Re: Урощение формул

From

Ivan Boldyrev (2:5080/1003)

To

Vitaly Lugovsky ()

Date

2003-01-28T17:58:29Z

Area

RU.ALGORITHMS

From: Ivan Boldyrev <boldyrev@dataeast.ru>

"VL" == Vitaly Lugovsky writes:
 VL> Vladislav Terehov wrote:
>> VL>  Зачем тут нейросети - я так с ходу вряд ли соображу.
>> 
>> VL>  Задача эта - эмпирическая. И NP-полная.
>> Расскажи несчатному пеpвокуpснику, что значат эти
>> опpеделения... Или хотя бы где почитать можно.

 VL>  NP-полная - решение расположено где-то на БЕСКОНЕЧНОМ дереве, и
 VL> требуется полный обход его. Однако, имея некоторые эмпирические
 VL> правила, мы можем найти более-менее хорошее решение, обходя лишь
 VL> часть дерева.

Скажи, а в задаче коммивояжёра -- "найти кратчайший цикл, проходящий
через все вершины полносвязного взвешенного графа" -- тоже бесконечное
дерево решений? С учётом того, что количество вообще всех циклов в
любом конкретном конечном графе конечно?

А для школьника/первокурсника я бы объяснил так: для некоторых задач
есть алгоритмы решения, временная сложность (количество шагов) которых
можно сверху оценить полиномом от размера задачи (количество вершин в
графе, например). Есть задачи, сложность которых больше, чем любой
полином, например, сложность выражается через экспоненту, или через
какую-нибудь более бысторастущую функцию, и доказано, что
полиномиальных алгоритмов решения нет.

А есть задачи, для которых существуют неполиномиальные алгоритмы
(которые при не очень удачных входных данных сводятся к перебору всех
вариантов, которых может быть как раз экспоненциальное количество), но
никто не знает, есть ли для них полиномиальные алгоритмы. Из множества
таких задач выделяют некоторое множество задач по чисто формальным
признакам (их можно решать за полиномиальное время на
"недетерминированной машине Тьюринга"; что это такое -- не так уж
важно). Такие задачи называются NP-проблемами (nondeterministic
polynomial). В этом классе NP-проблем есть некоторое хитрое
подмножество, которое называется классом NP-полных задач (NPC). Оно
характеризуется тем, что любую задачу из NP можно свести к любой
задаче из NPC (в том числе они сводятся друг к другу). Таким образом,
научившись за полиномиальное время решать любую задачу из NPC, мы
сможем решить любую задачу из NP также за полиномиальное время (но,
конечно, большее, но по сравнению с экспонентой это мелочи...)

На практике NP-сложные задачи (а их на удивление много) решают
приближенными методами, которые дают не самое оптимальное решение, но
зато всегда за полиномиальное время.

-- 
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)