Глава 22. Потоки в сетях. сводимости. Для обширного класса комбинаторных алгоритмов эти задачи представляют собой водораздел

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

У нас есть все основания разрабатывать максимально универсальную модель, посколь­ку чем выше уровень универсальности модели, тем больше задач она охватывает, благо­даря чему повышается коэффициент полезного действия алгоритма, который может ре­шать задачу, сводимую к этой модели. Разработка такого алгоритма может представлять собой трудно решаемую, если не неразрешимую Задачу. Если в нашем распоряжении нет алгоритма, который гарантирует приемлемую эффективность решения, у нас обычно име­ется алгоритм, который хорошо работает на специальных классах задач, которые нас интересуют. Специальные аналитические выкладки дают неконкретные результаты, одна­ко, довольно-таки часто мы опираемся на эмпирические исследования. Действительно, практики обычно проводят апробацию наиболее общей модели из числа доступных (или той, которая предлагает хорошо отлаженный пакет решений) и не идут дальше, если мо­дель не выходит за пределы приемлемого времени. Тем не менее, мы должны избегать использования чрезмерно общих моделей, ибо это может привести к излишним затратам времени на решение тех задач, для которых более специализированные модели могут обеспечить более высокую эффективность.

С другой стороны, мы склонны искать более совершенные алгоритмы решения важ­ных специальных задач, в частности, алгоритмы решения крупных задач или большого числа меньших задач, когда вычислительные ресурсы являются узким местом. Как мы уже могли убедиться на многих примерах в этой книге и в частях 1-4, мы часто находим под­ходящий алгоритм, который позволяет снизить затраты ресурсов во многие сотни и ты­сячи раз и даже больше, что исключительно важно, когда мы измеряем затраты в часах или в долларах. Общий подход, описанный в главе 2, который мы успешно применяли во многих областях, исключительно полезен в таких ситуациях, и мы с нетерпением ждем появления более совершенных алгоритмов в спектре алгоритмов на графах и комбина­торных алгоритмов. Возможно, основной недостаток перенесения центра тяжести на спе­циальные алгоритмы заключается в том, что довольно часто небольшое изменение, вне­сенное в модель, приводит к тому, что алгоритм становится для нее непригодным. В то же время, когда мы прибегаем к помощи чрезмерно обобщенной модели и алгоритма, обеспечивающего решения нашей задачи, мы меньше подвержены воздействиям упомя­нутого недостатка.

Программные библиотеки, охватывающие множество алгоритмов, с которыми мы оз­накомились, можно найти во многих средах программирования. Такие библиотеки, не­сомненно, представляют собой важные ресурсы, которые нужно принимать во внимание при решении конкретных задач. Тем не менее, иногда такими библиотеками трудно пользоваться, они устаревают либо плохо соответствуют текущей задаче. Опытные про­граммисты хорошо представляют себе, насколько важно найти компромисс между ис­пользованием преимуществ библиотечного ресурса и чрезмерной зависимостью от этого ресурса (даже если он преждевременно не устареет). Некоторые из рассмотренных ра­нее реализаций являются эффективными, простыми в разработке и широко используемы-

Часть 5. Алгоритмы на графах