|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 09 Oct 2001 10:10:06
To : Andrew Simontsev
Subject : Распределение файлов по CD
--------------------------------------------------------------------------------
Mon Oct 08 2001 18:58, Andrew Simontsev wrote to Rick Hustle:
RH>>>> Интересем алгоритм решения этой задачки отличный от "тупого" перебора
RH>>>> комбинаций. Т.к. уже при кол-ве файлов полядка > 12 задача становится
RH>>>> ОЧЕHЬ долгорешаемой.
IK>>> Припоминается, что лет 7-8 назад при обсуждении алгоритма для
IK>>> размещения файлов по дискетам утверждалось, что сия задача NP-полная.
RH>> Поясни, пожалуйста, что такое "NP-полная задача"?
AS> Это значит, что трудоемкость - экспоненциальная (не
AS> полиномиальная). Решается только перебором. Так что надо читать про
AS> всякие выкрутасы, типа "жадных" алгоритмах, метода ветвей и границ и
AS> проч. приемы сокращения перебора... Hу и соответсвенно точного решения
AS> можно и не получить, т. е. скорее всего оно будет не самым хорошим (но
AS> гарантированно не плохим :) )...
Hе совсем так. NP-полная - значит, принадлежит к семейству задач, за
полиномиальное время сводимых друг к другу, так что если одна из них решалась
бы за полиномиальное время - то решались бы все... Hо ни для одной пока такое
не найдено...
(Более строго - они "недетерминировано полиномиальны")
С уважением
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
