Глава 22. Потоки в сетях. шин, а потом обращаться к ним по мере необходимости, мы вызываем функцию phiR, чтобы получить каждое значение потенциала; она проходит вверх по дереву с тем

шин, а потом обращаться к ним по мере необходимости, мы вызываем функцию phiR, чтобы получить каждое значение потенциала; она проходит вверх по дереву с тем, что­бы найти допустимый потенциал, а затем вычисляет все необходимые потенциалы на этом пути. Чтобы реализовать такой подход, мы просто заменяем доступ к массиву phi [и] на функцию, которая определяет стоимость использования вызова функции phiR(u). В худ­шем случае мы вычисляем все потенциалы так же, как и раньше, однако если мы иссле­дуем только несколько подходящих ребер, то мы вычисляем только те потенциалы, ко­торые необходимы для выявления этих ребер.

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

Как мы неоднократно подчеркивали на протяжении всей этой книги, задача анализа и сравнения алгоритмов на графа сложна сама по себе. С появлением сетевого симплек­сного алгоритма эта задача еще больше усложняется за счет различных подходов к реа­лизации и широкому разнообразию приложений, с которыми нам приходится сталкивать­ся (см. раздел 22.5). Какая из реализаций наилучшая? Имеем ли мы право сравнивать реализации, в основу которых положены доказуемые границы для худших случаев? На­сколько точно мы можем выразить в конкретных числах различие в производительности различных реализаций применительно к конкретным приложениям? Должны ли мы ис­пользовать различные реализации, приспособленные под конкретное приложение?

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

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

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