НОУ ІНТУЇТ | лекція | найкоротші шляхи

негативні ваги

Тепер звернемося до проблеми обробки негативних ваг в задачах пошуку найкоротших шляхів. Можливо, негативні ваги ребер здадуться неприродними, оскільки протягом більшої частини цього розділу ми на наочних прикладах звикли, що ваги представляють відстані або вартості. Однак, як було показано в розділі 21.6, негативні ваги ребер природно виникають, коли до задачі пошуку найкоротших шляхів зводяться інші завдання. Негативні ваги - це не просто математична абстракція; навпаки, вони істотно розширюють можливість застосування завдань пошуку найкоротших шляхів в якості моделі для вирішення інших завдань. Ця потенційна користь спонукає нас шукати ефективні алгоритми для вирішення мережевих завдань, в яких можливі негативні ваги.

на Мал. 21.26 показано невеликий приклад, який демонструє вплив введення негативних ваг в завданню про найбільш коротких шляхах в мережі. Можливо, найбільш важливий ефект полягає в тому, що при наявності негативних ваг найбільш короткі шляхи з малими вагами часто містять більше ребер, ніж шляху з більш високими вагами. У разі позитивних ваг ми намагалися шукати шляхи навпростець; однак при наявності негативних ваг ми шукаємо обхідні шляхи, які містять стільки ребер з негативними вагами, скільки ми зможемо відшукати. Цей ефект перевертає наше наочне розуміння пошуку "коротких" шляхів, яке необхідно для розуміння алгоритмів, так що нам потрібно подолати цей інтуїтивний бар'єр і розглянути це завдання на базовому абстрактному рівні.

Взаємозв'язок між найкоротшими шляхами в мережах і гамільтонових шляхами в графах, показана при доказі леми 21.18, перегукується зі спостереженням, що пошук шляхів низького ваги (які ми називаємо "короткими") рівноцінний пошуку шляхів з великою кількістю ребер (які можна вважати "довгими") . При наявності негативних ваг ми шукаємо швидше довгі шляхи, ніж короткі.

Перша думка, яка приходить на розум, щоб виправити ситуацію - це знайти найменший (найбільший негативний) вага ребра, потім додати абсолютне значення цього числа до всіх ваг ребер, щоб отримати мережу без негативних ваг. Цей наївний спосіб взагалі не працює через те, що найкоротші шляхи в новій мережі ніяк не пов'язані з найкоротшими шляхами в колишньої мережі.

Мал.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 , Найкоротший шлях з 4 в 2 - це шлях 4-3-5-1-2. Якщо збільшити ваги всіх ребер в графі на 0.38, щоб зробити їх все позитивними, вага цього шляху збільшиться з 0.20 до 1.74. Однак вага 4-2 зросте з 0.32 лише до 0.70, так що найкоротшим шляхом з 4 в 2 стане це ребро. Чим більше ребер містить шлях, тим більше він "потяжелеет" від такого перетворення, тому результат з точки зору попереднього абзацу якраз протилежний тому, що потрібно. Але навіть якщо цей наївний підхід не працює, ідея перетворення мережі в еквівалентну без негативних ваг, але з тими ж найкоротшими шляхами, цілком гідна уваги; в кінці розділу ми розглянемо алгоритм на основі цієї ідеї.

Всі наші алгоритми пошуку найкоротших шляхів до сих пір містили одне з двох обмежень на завдання найкоротших шляхів, які дозволяли отримати ефективне рішення: вони забороняли або цикли, які негативні ваги. Чи існують менш суворі обмеження, які можна було б накласти на мережі, що містять як цикли, так і негативні ваги, і все-таки отримати розв'язні завдання найкоротших шляхів? Ми торкнулися відповіді на це питання на початку глави, коли нам знадобилося додати вимогу, що для того, щоб завдання мала б сенс в разі наявності негативних циклів, шляхи повинні бути простими. Можливо, нам слід обмежитися розглядом мереж, які не мають таких циклів?

Найкоротші шляхи в мережах без негативних циклів. Для заданої мережі, яка може містити ребра з негативними вагами, але не містить циклів негативного ваги, потрібно вирішити одну з наступних завдань: знайти найкоротший шлях, що з'єднує дві заданих вершини (завдання пошуку найкоротшого шляху), знайти найкоротші шляхи з заданої вершини в усі інші вершини (завдання з одним джерелом) або знайти найкоротші шляхи, що з'єднують всі пари вершин (завдання для всіх пар вершин).

Доказ леми 21.18 залишає можливість побудови ефективних алгоритмів вирішення цього завдання, оскільки воно втрачає сенс за відсутності негативних циклів. Щоб вирішити задачу пошуку гамильтонова шляху, необхідно мати можливість вирішувати завдання пошуку найкоротших шляхів у мережах з великою кількістю негативних циклів.

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

Лемма 21.19. Завдання календарного планування з кінцевими термінами зводиться до задачі пошуку найкоротших шляхів у мережах, які не містять негативних циклів.

Доведення. Міркування з докази леми 21.15 показують, що побудова в доказі леми 21.16 призводить до мереж, що не містить негативних циклів. З завдання календарного планування ми створюємо завдання різницевих обмежень зі змінними, які відповідають моментам початку робіт, а з завдання різницевих обмежень ми створюємо мережу. Потім ми міняємо знаки всіх ваг, щоб перейти від завдання пошуку найбільш довгих шляхів до задачі пошуку найкоротших шляхів - перетворення, яке звертає знаки всіх нерівностей. Будь простий шлях в мережі з i в j відповідає послідовності нерівностей, що включають змінні. Згортаючи ці нерівності, отримуємо з існування такого шляху, що , Де wij - сума ваг на шляху з i в j. Негативний цикл відповідає 0 в лівій частині цієї нерівності і від'ємного значення в правій частині, тобто такий цикл не може існувати.

Як ми зазначали, коли вперше обговорювали завдання календарного планування в розділі 21.6, це твердження неявно передбачає, що наші завдання календарного планування є розв'язуються (тобто мають рішення). На практиці не слід робити подібне припущення, і частина обчислювальних витрат піде на визначення можливості розв'язання задачі календарного планування з кінцевими термінами. У побудові докази леми 21.19 негативний цикл в мережі означає, що завдання нездійсненне, тому дана задача відповідає наступній.

Виявлення негативних циклів. Чи містить дана мережа негативний цикл? Якщо так, то потрібно знайти один такий цикл.

З одного боку, це завдання не обов'язково проста (прості алгоритми перевірки циклів для орграфов незастосовні); з іншого боку, вона не обов'язково складна (не застосовується і зведення з леми 21.16 з завдання пошуку Гамільтона шляху). Тому спочатку потрібно розробити алгоритм вирішення цієї задачі.

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

Арбітражні операції (валютні спекуляції). Багато газет друкують таблиці курсів світових валют (див., Наприклад, Мал. 21.27 ). Такі таблиці можна розглядати як уявлення матрицями суміжності для повних мереж. Ребро st з вагою x означає, що можна конвертувати одну одиницю валюти s в x одиниць валюти t. Шляхи в мережі задають багатокрокові конверсії. Наприклад, якщо існує також ребро tw з вагою у, то шлях stw представляє спосіб, що дозволяє конвертувати одну одиницю валюти s в xy одиниць валюти w. Можна було б очікувати, що xy дорівнює вазі ребра sw у всіх випадках, однак подібні таблиці є складною динамічною системою, де така послідовність аж ніяк не гарантована. Якщо знайдеться варіант, де xy менше, ніж вага sw, то ми зможемо перехитрити систему. Припустимо, що вага ws дорівнює z, і xyz> 1, тоді цикл stws дозволяє конвертувати одну одиницю валюти s в більш ніж одну одиницю (xyz) валюти s. Тобто можна отримати дохід в 100 (xyz - 1) відсотків, конвертіровав s в t, потім в w і знову в s. Дана ситуація є прикладом арбітражних операцій (arbitrage), які дозволили б нам отримувати безмежні доходи, якби не існувало сил поза моделлю - як, наприклад, обмеження на розмір угод. Щоб перетворити цю задачу в задачу пошуку найкоротших шляхів, прологарифмируем все числа так, щоб ваги шляхів відповідали сумі ваг ребер замість їх множення, а потім змінимо їх знаки, щоб звернути нерівності. При цьому ваги ребер можуть виявитися негативними або позитивними, а найкоротший шлях з s в t дає найкращий спосіб конвертації валюти s в валюту t. Цикл з найменшою вагою вказує кращу можливість для арбітражних операцій, хоча вигідний будь-негативний цикл.

Мал.21.27.

арбітражні операції

Таблиця у верхній частині містить перекладні коефіцієнти однієї валюти в іншу. Наприклад, другий елемент в верхньому ряду означає, що за 1 долар можна купити 1,631 одиниць валюти P. Конвертація $ 1000 в валюту P і назад повинна дати $ 1000 * 1,631 * 0,613 = $ 999, тобто втрата становить $ 1. Однак конвертація $ 1000 в валюту P, потім в валюту Yі назад в долари дає $ 1000 * 1,631 * 0,411 * 1,495 = $ 1002, тобто прибуток 0,2%. Якщо скласти нову таблицю (внизу) з негативних логарифмів всіх чисел, то її можна вважати матрицею суміжності для повної мережі з вагами ребер, які можуть бути як позитивними, так і негативними. У цій мережі вузли відповідають валют, ребра - конвертація, а шляхи - послідовностям конвертацій. Описана конверсія відповідає циклу $ -PY- $ в графі з вагою -0,489 + 0,890 - 0,402 = -0,002. Найкраща можливість для арбітражних операцій відповідає найбільш короткому циклу в графі.

Чи можна виявити в мережі негативні цикли або знайти найкоротші шляхи в мережах, які не містять негативних циклів? Існування ефективних алгоритмів для вирішення цих завдань не суперечить NP-труднощі спільної справи, яка була доведена в лемі 21.18, оскільки зведення задачі пошуку гамильтонова шляху до будь-якої з цих завдань не відомо. А саме, зведення леми 21.18 говорить про те, чого ми не можемо зробити: створити алгоритм, який може гарантовано і ефективно знайти шлях з найменшою вагою в будь-якої заданої мережі, якщо в ній допускаються негативні ваги ребер. Така постановка завдання видається занадто загальною. Однак можна вирішити обмежені версії цього завдання, хоча це і не так легко, як для інших обмежених версій даної задачі (позитивні ваги і ациклічні мережі), які ми вивчили вище в цьому розділі.

У загальному випадку, як було сказано в розділі 21.2, алгоритм Дейкстри не працює при наявності негативних ваг, навіть якщо обмежитися розглядом мереж, в яких немає негативних циклів. на Мал. 21.28 продемонстровано це твердження. Основне обмеження полягає в тому, що в цьому алгоритмі шляху розглядаються в порядку зростання їх довжини. Доказ правильності алгоритму (див. Лему 21.2) передбачає, що додавання ребра до шляху робить цей шлях більш довгим.

Мал.21.28.

Відмова алгоритму Дейкстри (негативні ваги)

У цьому прикладі алгоритм Дейкстри вирішує, що найкоротшим шляхом з 4 в 2 є шлях 4-2 (довжиною 0.32), і упускає коротший шлях 4-3-5-1-2 (довжиною 0.20).

Алгоритм Флойда (Floyd) не потребує такої припущенні і ефективний навіть тоді, коли ваги ребер можуть бути негативними. Якщо немає негативних циклів, він обчислює найкоротші шляхи; примітно, що в разі існування негативних циклів цей аглорітм виявляє принаймні один з них.

Лемма 21.20. Алгоритм Флойда ( Мал. 21.29 ) Вирішує завдання виявлення негативного циклу і завдання пошуку найкоротших шляхів для всіх пар вершин в мережах, які містять негативні цикли, за час, пропорційне V3.

Доведення. Доказ леми 21.8 не залежить від того, чи можуть ваги ребер бути негативними, однак при наявності ребер з негативними вагами потрібна інша інтерпретація результатів. Кожен елемент в матриці свідчить про те, що алгоритм виявив шлях цієї довжини. Зокрема, будь-який негативний елемент на діагоналі матриці відстаней означає наявність принаймні одного негативного циклу. При наявності негативних циклів ми не можемо безпосередньо робити будь-які подальші висновки, тому що шляху, які алгоритм неявно перевіряє, не обов'язково прості: адже деякі з них можуть містити один і більше витків по одному негативного циклу або декільком. Однак якщо негативних циклів немає, то шляху, які обчислюються алгоритмом, прості, оскільки будь-який шлях з циклом означає існування такого шляху, який з'єднує ті ж дві точки, але містить менше ребер і має не більшу вагу (той же шлях з віддаленим циклом).

Доказ леми 21.20 не дає конкретного рецепту, як знайти конкретний негативний цикл, виходячи з матриць відстаней і шляхів, що обчислюються за алгоритмом Флойда. Ми залишаємо це завдання в якості самостійного вправи (див. Вправу 21.122).

Алгоритм Флойда вирішує завдання пошуку найкоротших шляхів для всіх пар вершин у графах, які не містять негативних циклів (див. Мал. 21.29 ). З огляду на відмову алгоритму Дейкстри в мережах, які можуть містити негативні ваги, алгоритм Флойда дозволяє вирішити задачу для всіх пар вершин в розріджених мережах без негативних циклів за час, пропорційне V3. Якщо в таких мережах потрібно вирішити задачу з одним джерелом, можна застосувати це рішення складності V3 для всіх пар вершин. Хоча при цьому виконується багато зайвої роботи, це краще, що ми поки знаємо для завдання з одним джерелом. Чи можна розробити більш швидкі алгоритми для цих завдань - такі, час виконання яких можна порівняти з алгоритмом Дейкстри для позитивних ваг ребер (E lg V для найкоротших шляхів з одного джерела і VE lg V для найкоротших шляхів для всіх пар вершин)? Ми можемо відповісти ствердно на це питання щодо завдання для всіх пар вершин; і можна знизити трудомісткість в гіршому випадку до VE для завдання з одним джерелом.

Мал.21.29.

Алгоритм Флойда (негативні ваги)

Ця послідовність демонструє побудову матриць всіх найкоротших шляхів для орграфа з негативними вагами за допомогою алгоритму Флойда. Перший крок збігається з наведеним на Мал. 21.14 . На другому кроці в гру вступає негативне ребро 5-1, і знаходяться шляхи 5-1-2 і 5-1-4. Алгоритм виконує точно таку ж послідовність кроків релаксації для будь-яких ваг, однак результати відрізняються.

А ось питання подолання бар'єру VE для спільної справи пошуку найкоротших шляхів з одного джерела є, як і раніше відкритим.

Наступний підхід, розроблений Р. Беллманом (R. Bellman) і Л. Фордом (L. Ford) в кінці 1950-х років, надає просту і ефективну основу для вирішення завдань пошуку найкоротших шляхів з одного джерела в мережах без негативних циклів. Щоб обчислити найкоротші шляхи з вершини s, ми (як завжди) використовуємо індексований іменами вершин вектор wt, такий, що wt [t] містить довжину найкоротшого шляху з s в t. У wt [s] заносимо 0, а в усі інші елементи wt - велике сигнальне значення, після чого обчислюємо найкоротші шляхи наступним чином:

Переглядаємо ребра мережі в будь-якому порядку і виконуємо релаксацію уздовж кожного ребра. Виконуємо V таких дій.

Загальний метод виконання V проходів по ребрах з переглядом ребер в будь-якому порядку ми будемо називати алгоритмом Беллмана-Форда (Bellman-Ford). Деякі автори застосовують цей термін для опису ще більш загального методу (див. Вправу 21.130).

Наприклад, для графа, представленого списками суміжності, алгоритм Беллмана-Форда пошуку найкоротших шляхів з початкової вершини s можна реалізувати так. Спочатку занесемо в елементи wt значення, більші, ніж будь-яка довжина шляху, а в елементи spt - порожні покажчики, і потім виконаємо наступний код:

wt [s] = 0; for (i = 0; i <G-> V (); i ++) for (v = 0; v <G-> V (); v ++) {if (v! = s && spt [v] == 0) continue; typename Graph :: adjIterator A (G, v); for (Edge * e = A.beg ();! A.end (); e = A.nxt ()) if (wt [e-> w ()]> wt [v] + e-> wt () ) {wt [e-> w ()] = wt [v] + e-> wt (); st [e-> w ()] = e; }}

Цей код демонструє простоту базового методу. Однак на практиці він не використовується: як незабаром буде показано, його прості модифікації дають реалізації, які більш ефективні для більшості графів.