![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Отрицательные веса
Теперь обратимся к теме, связанной с отрицательными весами в задачах поиска кратчайших путей. Возможно, отрицательные веса ребер покажутся неестественными, поскольку на протяжении большей части этой главы мы на интуитивных примерах привыкли, что веса представляют расстояния или стоимости. Однако, как было показано в разделе 21.6, отрицательные веса ребер возникают естественным путем, когда к задаче поиска кратчайших путей сводятся другие задачи. Отрицательные веса являются не только математической абстракцией; напротив, они существенно расширяют применимость задач кратчайших путей в качестве модели для решения других задач. Эта потенциальная польза побуждает нас искать эффективные алгоритмы для решения сетевых задач, допускающих наличие отрицательных весов. Глава 21, Кратчайшие пути
РИСУНОК 21.26. ТИПОВАЯ СЕТЬ С ОТРИЦАТЕЛЬНЫМИ РЕБРАМИ Это та же типовая сеть, что и сеть, показанная на рис. 21.1, за исключением того, что ребра 3-5 и 5-1 являются отрицательными. Естественно, данное изменение существенным образом воздействует на структуру кратчайших путей, что легко заметить путем сравнения матриц расстояний и путей справа с соответствующими матрицами на рис. 21.9. Например, кратчайший путь из 0 в 1 в этой сети есть 0-5-1, и он имеет длину 0, тогда как кратчайший путь из 2 в 1 есть 2-3-5-1 с длиной -0.17. Рисунок 21.26 представляет небольшой пример, который иллюстрирует влияние введения отрицательных весов в задаче о наиболее коротких путях в сети. Возможно, при этом наиболее важный эффект состоит в том, что когда присутствуют отрицательные веса, то наиболее короткие пути с малыми весами имеют тенденцию содержать больше ребер, чем пути с более высокими весами. В случае положительных весов нашей целью было искать кратчайшие расстояния; однако, при наличии отрицательных весов мы ищем обходные пути (detours), которые используют столько ребер с отрицательными весами, сколько мы сможем отыскать. Этот эффект производит переворот в нашем интуитивном понимании поиска алгоритмов " коротких" путей, так что нам потребуется преодолеть этот барьер интуиции и рассмотреть данную задачу на базовом абстрактном уровне. Отношение между кратчайшими путями в сетях и гамильтоновыми путями в графах, показанное при доказательстве свойства 21.18, связано с нашим наблюдением, что поиск путей низкого веса (которые мы называем " короткими") равноценен поиску путей с большим количеством ребер (которые мы могли бы считать " длинными"). При наличии отрицательных весов мы ищем скорее длинные пути, нежели короткие. Первая мысль, которая приходит на ум, дабы исправить ситуацию, — это найти наименьший (наиболее отрицательный) вес ребра, затем добавить абсолютное значение этого числа ко всем весам ребер, чтобы превратить сеть в такую, которая не имеет отрицательных весов. Это наивное приближение вообще не работает из-за того, что кратчайшие пути в новой сети не имеют никакого отношения к кратчайшим путям в прежних сетях. Например, в сети приведенной на рис. 21.26, кратчайший путь из 4 в 2 есть 4-3-5-1-2. Если увеличить на 0.38 веса всех ребер в графе, чтобы сделать их все положительными, вес этого пути возрастет от 0.20 до 1.74. Однако вес 4-2 возрастет в действительности с 0.32 до 0.70, так что это ребро станет кратчайшим путем из 4 в 2. Чем больше ребер имеет путь, тем больше он страдает от такого преобразования, поэтому результат, по сравнению с тем, что мы наблюдали в предыдущем параграфе, как раз противоположен тому, что требуется. Даже если эта наивная идея не работает, цель преобразования сети в эквивалентную, без отрицательных весов, но с теми же кратчайшими путями, вполне достойна внимания; в конце раздела мы рассмотрим алгоритм достижения упомянутой цели.
|