Для решения новой задачи всегда хочется придумать точный эффективный алгоритм. В книге Гэри и Джонсона приведен список известных NР-полных задач и может так оказаться, что наша задача есть в этом списке Что делать в этом случае? Или нашей задачи нет в списке, но мы думаем что она могла бы там быть. Доказательство того, что наша задача NP-полна не решает проблемы. С практической точки зрения мы должны изобрести новый алгоритм или использовать старый, даже если задача NP-полна. Если алгоритм полиномиален, но степень полинома больше 3, то этот алгоритм скорее всего, не достаточно эффективен. Дадим несколько советов.
1. Придумать новый алгоритм. Один из лучших примеров такого подхода симплекс-метод линейного программирования. Хотя симплекс-метод не является полиномиальным в худшем случае, он работает. Одной из главных проблем линейного программирования является вопрос: «Почему симплекс-метод работает так хорошо?» В формулировке задачи линейного программирования значения элементов матрицы А и векторов b и с произвольны Вероятно, в реальных задачах А, b, с удовлетворяют некоторым условия делающим симплекс-метод эффективным. '
2. Рассмотреть специальные случаи задачи. Для любой нерешенной задачи полезно сначала рассмотреть специальные или крайние случаи а затем постепенно обобщать результат. Обычно новую задачу сводят к известной, пытаясь, тем не менее, не потерять специфики задачи. Великое множество комбинаторных задач можно свести к задачам целочисленного линейного программирования и решать общими методами. Однако для реальных задач эти общие методы, как правило, приводят к весьма медленным на практике алгоритмам. Общий алгоритм подобен одежд ходового размера: она подойдет всем, но не будет слишком удобна.
3. Эвристический подход. Чтобы сформулировать эвристический подход для решения конкретной задачи, обычно испытывают несколько числовых примеров, на которых тренируют интуицию. Если эвристический алгоритм приводит к успеху только в некоторых случаях, мы должны описать эти случаи.
4. Декомпозиция задачи. Если задача большая и сложная, то ее возможно удастся разложить на несколько подзадач и решать отдельно каждую. После этого необходимо как-то из частных решений составить общее решение исходной задачи. Подход декомпозиции был проиллюстрирован на задаче нахождения кратчайших путей между всеми парами вершин большой сети.
5. Использовать общие методы. Если у нас нет времени, и мы не хотим заниматься настоящими исследованиями, можно использовать общие подходы. Вот некоторые из них:
(1) поиск с возвращением,
(2) динамическое программирование,
(3) методы отсечений Гомори.
Специальные модификации даже таких методов, как поиск с возвращением, могут существенно повысить эффективность алгоритма, например, в игре на дереве. Метод отсечений Гомори предназначен для решения задач целочисленного линейного программирования. В некоторых случаях он хорошо зарекомендовал себя, но при решении многих других задач ведет себя крайне плохо.
Вообще говоря, нет систематического метода для создания новых комбинаторных алгоритмов.