Задача китайського листоноші

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

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

Методи розв'язання задачі

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle D(i)=d^{-}(i)-d^{+}(i)}$ (4)

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

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

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

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

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

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

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

Див. також

• Задача комівояжера
• Ейлерів цикл

Посилання

1. "Chinese Postman Problem". Архів оригіналу за 17 жовтня 2008. Процитовано 13 січня 2010.

Література

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