Жадные алгоритмы на каждом шаге выбирают локально-оптимальное решение,
в расчете на то, что в итоге получится глобально-оптимальное решение.
NP-ПОЛНЫЕ ЗАДАЧИ
ЗАДАЧА О КОММИВОЯЖЕРЕ
Условие: коммивояжер хочет объехать 5 городов - и сделать это за минимально
возможное время.
Решение: перебрать все возможные комбинации порядка объезда городов.
(для 5 элементов - 120 перестановок - n!).
Если городов много, то решение будет занимать слишком много времени,
как и в задаче покрытия множества.
У задачи о коммивояжере и задаче покрытия множества есть кое-что общее:
вы вычисляете каждое возможное решение и выбираете кратчайшее/мини мальное.
Обе эти задачи являются NР-полными (non-deterministic polynomial).
NP-полные задачи не имеют известных быстрых решений.
Жадное решение для задачи о коммивояжере: выбирать каждый раз самый
ближний город из еще непосещенных.
КАК ОПРЕДЕЛИТЬ, ЧТО ЗАДАЧА ЯВЛЯЕТСЯ NР-ПОЛНОЙ̆?
Обычно различия между легко решаемыми и NP-полными задачами не очень значительны.
Например, задача поиска кратчайшего пути между точками легко решается
поиском в ширину (или алгоритмом Дейкстры для взвешенных графов). Но если нужно
найти кратчайший путь между несколькими точками - это уже NP-полная
задача о коммивояжере.
Несколько характерных признаков:
- ваш алгоритм быстро работает при малом количестве элементов,
но сильно замедляется при увеличении их числа; - формулировка все комбинации х часто указывает на NР-полноту задачи;
- вам приходится вычислять все возможные варианты Х, потому что задачу невозможно
разбить на меньшие подзадачи? Такая задача может оказаться NР-полной; - если в задаче встречается некоторая последовательность (например,
последовательность городов, как в задаче о коммивояжере) и задача не имеет
простого решения, она может оказаться NР-полной; - если в задаче встречается некоторое множество (например, множество радиостанций)
и задача не имеет простого решения, она может оказаться NР-полной; - можно ли переформулировать задачу в условиях задачи покрытия множества
или задачи о коммивояжере? В таком случае ваша задача определенно является NР-полной.
Задача на покрытие в этой папке