Краткая характеристика сложных задач

Во время чтения предыдущих параграфов вы могли заметить, что существует два варианта многих сложных задач. Первый вариант задачи задает вопрос: «Существует ли решение задачи, удовлетворяющее определенным условиям?». Второй, более общий случай дает ответ на вопрос: «Какое решение задачи будет наилучшим?»

Обе задачи при этом имеют одинаковое дерево решений. В первом случае дерево решений просматривается до тех пор, пока не будет найдено какое‑либо решение. Так как для этих задач не существует частичного или приближенного решения, то обычно нельзя использовать для уменьшения объема работы эвристический подход или метод ветвей и границ. Обычно всего лишь несколько путей в дереве ведут к решению, поэтому решение этих задач — очень трудоемкий процесс.

При решении же обобщенного случая задачи, часто можно использовать частичные решения и применить метод ветвей и границ. Это не облегчает поиск наилучшего решения задачи, поэтому не поможет получить точное решение для частной задачи. Например, сложнее найти самый короткий Гамильтонов путь в сети, чем найти произвольный Гамильтонов путь для той же сети.

==========222

С другой стороны, эти вопросы обычно относятся к различным входным данным. Обычно вопрос о существовании Гамильтонова пути возникает, если сеть разрежена, и сложно сказать, существует ли такой путь. Вопрос о кратчайшем Гамильтоновом пути возникает обычно, если сеть достаточно плотная и существует множество таких путей. В этом случае легко найти частичные решения, и метод ветвей и границ может сильно упростить решение задачи.

Резюме

Можно использовать деревья решений для моделирования различных задач. Поиск наилучшего решения задачи соответствует при этом поиску наилучшего пути в дереве. К сожалению, деревья решений для многих интересных задач имеют огромный размер, поэтому решить такие задачи методом полного перебора можно только для очень небольших задач.

Метод ветвей и границ позволяет отсекать большую часть ветвей в некоторых деревьях решений, что позволяет получать точное решение для задач гораздо большего размера.

Тем не менее, для самых больших задач, даже применение метода ветвей и границ не может помочь. В этом случае, для получения приблизительного решения необходимо использовать эвристический подход для получения приблизительных решений. При помощи методов случайного поиска и последовательных приближений можно найти приемлемое решение, даже если неизвестно, будет ли оно наилучшим возможным решением задачи.

==========223

Глава 9. Сортировка

Сортировка — одна из наиболее активно изучаемых тем в компьютерных алгоритмах по ряду причин. Во-первых, сортировка — это задача, которая часть встречается во многих приложениях. Почти любой список данных будет нести больше смысла, если его отсортировать каким‑либо образом. Часто требуется сортировать данные несколькими различными способами.

Во‑вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных деревьев в массиве.

Наконец, сортировка является одной из немногих задач с точными теоретическими ограничениями производительности. Можно показать, что время выполнения любого алгоритма сортировки, который использует сравнения, составляет порядка O(N * log(N)). Некоторые алгоритмы достигают теоретического предела, то есть они являются оптимальными в этом смысле. Есть даже ряд несколько алгоритмов, которые используют другие методы вместо сравнений, которые выполняются быстрее, чем за время порядка O(N * log(N)).