![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. тием, поскольку оно подводит нас ближе к компактной и элегантной реализации, которая достигает обеих целей.
Мы полагаем существование двух конкретных задач в рамках модели потоков в сетях, а именно, задачи о максимальном потоке (maxflow) и задачи о потоке минимальной стоимости (mincost-flow). Несложно будет обнаружить их определенную связь с описанными выше моделями решения задач, с моделью кратчайшего пути из главы 21, с LP-моделью (linear-programming model — моделью линейного программирования) из части 8, а также со множеством специальных моделей задач, в том числе и только что обсужденных. На первый взгляд может показаться, что многие из этих задач не имеют ничего общего с задачами о потоках в сетях. Выявление зависимости между заданной задачей и известными задачами часто является важным шагом при разработке подхода к решению этой задачи. Более того, этот шаг часто важен еще и потому, что мы должны иметь представление о той хрупкой границе, которая отделяет тривиальные задачи от труднорешаемых задач, прежде чем предпринимать попытки разработки реализаций. Внутренняя структура задач и различного вида зависимости между задачами, которые мы рассматриваем в этой главе, создают благоприятный контекст для выбора подхода к решению подобного рода задач. В рамках приближенной классификации алгоритмов по категориям, которую мы начали в главе 17, алгоритмы, которые будут изучаться в этой главе, попадают в категорию " легко решаемых", поскольку у нас имеется простые реализации, которые гарантировано выполняются за время, пропорциональное полиному от размера сети. Другие реализации хотя и не гарантируют полиномиального времени выполнения в худшем случае, тем не менее, они компактны и элегантны и, как показала практика, пригодны для решения широкого круга практических задач, аналогичных обсуждаемым здесь. Мы рассмотрим их подробно, поскольку в дальнейшем они принесут нам несомненную пользу. Исследователи по-прежнему заняты поиском более быстродействующих алгоритмов с тем, чтобы стали возможными крупные приложения, а также чтобы снизить себестоимость критических приложений. Идеальные оптимальные алгоритмы решения задач о потоках в сети, обеспечивающие максимально возможное быстродействие, еще ждут своих первооткрывателей. С другой стороны, известно, что некоторые задачи, которые сводятся к задачам о потоках в сетях, решаются эффективнее с помощью специальных алгоритмов. В принципе, мы можем заняться реализацией и совершенствованием таких специализированных алгоритмов. Однако, несмотря на то, что этот поход продуктивен в отдельных случаях, алгоритмы решения множества других задач (отличных от тех, что решаются методом сведения к потокам в сети) не существуют. Но даже в тех случаях, когда специализированные алгоритмы существуют, разработка реализаций, способных превзойти удачные программы, в основе которых лежит задача о потоках в сетях, связана с существенными сложностями. Более того, исследователи продолжают работы по совершенствованию алгоритмов решения задач о потоках в сетях, так что удачные алгоритмы этого типа вполне могут превзойти известные методы решения данной практической задачи. С другой стороны, задачи о потоках в сетях представляют собой специальные случаи еще более общей LP-задачи, которые нам предстоит рассмотреть в части 8. И хотя мы могли воспользоваться (а многие так и делают) алгоритмом решения LP-задач для реше-
|