|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Simontsev 2:5005/115.41 08 Oct 2001 18:58:24
To : Rick Hustle
Subject : Распределение файлов по CD
--------------------------------------------------------------------------------
Sunday, October 07 2001 00:13, Rick Hustle wrote to Igor Krassikov:
RH>>> Интересем алгоритм решения этой задачки отличный от "тупого" перебора
RH>>> комбинаций. Т.к. уже при кол-ве файлов полядка > 12 задача становится
RH>>> ОЧЕHЬ долгорешаемой.
IK>> Припоминается, что лет 7-8 назад при обсуждении алгоритма для
IK>> размещения файлов по дискетам утверждалось, что сия задача NP-полная.
RH> Поясни, пожалуйста, что такое "NP-полная задача"?
Это значит, что трудоемкость - экспоненциальная (не полиномиальная).
Решается только перебором. Так что надо читать про всякие выкрутасы, типа
"жадных" алгоритмах, метода ветвей и границ и проч. приемы сокращения
перебора... Hу и соответсвенно точного решения можно и не получить, т. е. скорее
всего оно будет не самым хорошим (но гарантированно не плохим :) )...
Bye, Rick.
Sincerely yours, Andrew.
Играет симфония Глюка на клавиатуре :-)
... I'm a VooDoo Chile!
--- Добрых дел мастер 3.0.1 лет ----------------------------------
* Origin: Меняю комнатную собачку на двухкомнатную. (2:5005/115.41)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
