Задача листоноші

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Задача (китайського) листоноші (англ. Chinese postman problem або англ. Route inspection problem) — задача пошуку найкоротшого циклу в графі, що включає всі ребра. Існують варіанти задачі для орієнтованих та неорієнтованих графів та для графів, частина ребер яких орієнтована, а частина — ні.

Задача отримала назву завдяки Алану Голдману (англ. Alan Goldman) з NIST, оскільки першим дослідником цієї задачі був китайський математик Мей-Ку Кван (англ. Mei-Ku Kuan, 1962).[1]

Методи розв'язання задачі[ред.ред. код]

Для орієнтованого графу: Необхідно розглянути окремо два випадки:

Випадок А. Граф G симетричний.

Випадок Б. Граф G несиметричний.

Випадок А. Якщо граф симетричний, то листоноша може пройти свій маршрут без повторного обходу якої-небудь із дуг, тобто оптимальне рішення задачі листоноші являється Ейлерів маршрут.

Випадок Б. Нехай f(i, j),позначає число повторних обходів дуги (i, j). Листоноші необхідно обрати такі невід’ємні значення змінних f(i, j), які мінімізують загальну довжину повторно обхідних дуг

~\sum^{}_{} {a(i, j)f(i, j)} (1)

При умові, що в кожну вершину він входить стільки разів, скільки виходить із неї, тобто

d^{-} (i) + \sum^{}_{} {f(j, i)} = {d^{+}(i)}+ (i)+\sum^{}_{} {f(i, j)} (2)

Перетворивши рівняння (2), отримуємо

\sum^{}_{} {f(i, j) - f(j, i)} = {d^{-}(i)}+{d^{+}(i)}=D(i) (3)

Таким чином, листоноша бажає мінімізувати вираз (1) при умові, що для всіх вершин графу G задовольняється рівність (3). Ця задача представляє одну із модифікацій задачі про потік мінімальної вартості. Вершини, для яких D(i) < 0, є стоками з граничним значенням сумарного вхідного потоку, рівним – D(i). Вершини, де D(i) > 0, представляють собою джерело з граничним значенням сумарного вихідного потоку, рівне D(i). Вершини, для яких D(i) = 0, є проміжковими вершинами. Значення пропускних здібностей всіх дуг безлімітні. Сформульована задача про потік мінімальної вартості може бути вирішена шляхом введення в граф додаткового джерела і стоку. Додаткове джерело пов'язаний дугами зі усіма іншими джерелами, і всі стоки пов'язані дугами з додатковим стоком. Значення пропускної здатності кожної дуги, що виходить з додаткового джерела, рівно граничному значенню сумарного потоку джерела, яке інцидентне цій дузі. Так як праві частини всіх рівностей, (3) - цілі числа, то можна стверджувати, що за допомогою описаного алгоритму визначення потоку мінімальної вартості будуть отримані невід'ємні цілі значення f(i, j). Визначивши цілочисельні оптимальні значення змінних f(i,j) побудуємо граф G*, В якому дуга (i, j), що з'єднує вершини i і j для всіх (i, j) ~\mathcal {2} A, повторюється f(i, j) + 1 раз. З рівністю (3) такий граф G* є симетричним. Тепер для графа G* за допомогою методу, описаного для випадку А, може бути знайдений Ейлером маршрут. Останній на графі G* відповідає маршруту листоноші па графі G, в якому дуга (i,j) обходиться [f(i,j) + 1] разів. Так як оптимального значення f(i, j) мінімізують вираз (1), одержуваний на графі G* Ейлерів маршрут повинен відповідати оптимальному маршрутом листоноші на графі G.

Для змішаного графу: Необхідно розглянути окремо два випадки: Випадок А. Граф G симетричний.

Випадок Б. Граф G несиметричний.

Випадок А.Нехай G = (X, A) – будь-який парний змішаний граф. Оптимальний маршрут листоноші (якщо він існує) може бути знайдено наступним чином. Позначимо через U множину всіх неорієнтованих дуг, а через V – множину всіх орієнтованих дуг в графі G. Для кожної дуги в U виберемо вихідний напрямок. Назвемо отриманий орієнтований граф графом G_\mathrm{d}. Для кожної вершини і графа G_\mathrm(d) обрахуємо

D(i)=d^- (i)-d^+ (i) (4)

Якщо D(i) < 0, то вершина і є стоком з граничною величиною сумарного вхідного потоку, рівному D(i). Якщо D(i) > 0, то вершина і є джерелом з граничною величиною сумарного виходить потоку D(i) - Якщо D(i) = 0, то вершина i є проміжною. Якщо в графі всі вершини є проміжними, то граф-парний симетричний орієнтований граф. Для отримання оптимального маршруту листоноші на такому графі треба знайти Ейлерів маршрут, який відповідає оптимальному маршруту листоноші на графі G. В іншому випадку необхідно побудувати граф G - (X, A'), в якому: (а) Кожна дуга (i, j) ~\mathcal {2} V заміщується дугою (i, j) ~\mathcal {2} A' з необмеженою величиною пропускної здатності і вартістю, рівної довжині дуги (i, j). (б) Кожній дузі (i, j) ~\mathcal {2} U і відповідає пара дуг (i, j) і (j, i) в A'. Кожна з цих дуг має необмежену величину пропускної здатності і вартість, рівну довжині дуги (i, j) ~\mathcal {2} A. (в) Кожній дузі (i, j) ~\mathcal {2} U відповідає також орієнтована дуга (i, j) ~\mathcal {2} A', напрямок якої протилежно напрямку дуги, прийнятому в G_\mathrm(d). Ця дуга називається фіктивною дугою. Припишемо фіктивної дузі вартість, рівну нулю, і величину пропускної здатності, рівну 2. З урахуванням визначених вище для графа G_\mathrm(d) граничних значень потоків, що виходять із джерел і входять до стоки, скористаємося алгоритмом побудови потоку мінімальної вартості для пошуку на графі {G'} потоку мінімальної вартості, що задовольняє потреби всіх стоків. Якщо такого потоку не існує, то не існує і маршруту листоноші. В іншому випадку нехай через f(i, j) позначається величина потоку, який протікає по дузі (i, j) графа G', отриманого в результаті рішення задачі про потік мінімальної вартості. Нагадаємо, що потік, отриманий за допомогою описаного вище алгоритму побудови потоку мінімальної вартості, є невід'ємним і цілочисловим. У ході докази того, що алгоритм забезпечує отримання рішення задачі листоноші, буде показано, що але кожної фіктивної дузі протікає потік, рівний 0 або 2. Побудуємо далі граф G*, В якому:

(a) Кожна не-фіктивного дуга (i, j) ~\mathcal {2} V графа G' замінюється [f(i, j) + 1] дугами (i, j) графа G*.

(б) Кожна не-фіктивна дуга (i, j) ~\mathcal {2} U графа G' замінюється f(i,j) дугами (i,j) графа G*.

(в) Якщо потік у фіктивній дузі дорівнює двом одиницям, то в граф G* включається одна така дуга.

(г) Якщо потік у фіктивній дузі дорівнює нулю, то в граф G* включається одна така дуга з протилежного орієнтацією. Таким чином, якщо у фіктивній дузі потік дорівнює нулю, то вибраний вихідний напрямок дуги графа G_\mathrm(d) зберігається і в графі G*, якщо ж потік у фіктивній дузі дорівнює двом одиницям, то напрямок орієнтації відповідної дуги графа G_\mathrm(d) в графі G* змінюється на протилежне.

Граф G* є парним симетричним орієнтованим графом. Для отримання оптимального маршруту листоноші на такому графі треба знайти Ейлерів цикл.

Випадок Б. Алгоритму розв'язання даної задачі не існує

Дивіться також[ред.ред. код]

Посилання[ред.ред. код]

  1. «"Chinese Postman Problem"». Архів оригіналу за 2013-07-05. 

Література[ред.ред. код]

  • Майника Э. (1981). Алгоритмы оптимизации на сетях и графах. М.: Мир. с. 323.