В математиці мережі доріг (автомобільних і не тільки) представляються зваженим графом. Населені пункти (або перехрестя) - це вершини графа, ребра - дороги, ваги ребер - відстані по цих дорогах.
Для зважених графів пропонується безліч алгоритмів. Наприклад, популярний алгоритм Дейкстри для пошуку найкоротшого шляху від однієї вершини до іншої. У всіх цих алгоритмів є загальна принципова (для математики) особливість - вони універсальні, тобто можуть успішно застосовуватися для графів будь-якої конструкції. Зокрема, для кожного алгоритму відома його складність - вона приблизно відповідає збільшенню часу виконання алгоритму в залежності від числа вершин графа. Все це детально можна прочитати, наприклад, в вікіпедії.
Повернемося до практичних завдань. Дороги представляються зваженим графом, але дороги - це не будь-який граф. Іншими словами, не можна з будь-якого графа побудувати дорожню мережу. На відміну від віртуального графа як математичної абстракції, дороги будуються людьми з реальних матеріалів і коштують досить великих грошей. Тому вони прокладаються не абияк, а за певними економічними і практичним правилам.
Ми не знаємо ці правила, однак, працюючи з дорожніми мережами, цілком можна використовувати алгоритми, які ефективні для графів доріг, хоча і не підходять для графів в універсальному або математичному сенсі. Розглянемо тут два таких алгоритму.
Кілька важливих понять і умовностей
1. Ми будемо використовувати зважені неорієнтовані графи з невід'ємними вагами ребер. Зокрема, дороги в рамках регіону (країни) є саме такою граф.
2. Матриця найкоротших відстаней (МКР) - її маленький і простий приклад можна знайти в багатьох дорожніх атласах. Ця табличка зазвичай називається приблизно так: «відстані між найбільш важливими містами». Вона виглядає як частина матриці нижче або вище головної діагоналі (з верхнього лівого в нижній правий кут), тому що з іншого боку головної діагоналі точно такі ж цифри, іншими словами елемент М (i, j) = М (j, i). Це відбувається, тому що граф, як кажуть математики, неорієнтований. Рядки і стовпці відповідають містам (вершин графа). У реальності така таблиця набагато більше, так як в вершини графа, крім міст, входять всі села і перехрестя, але надрукувати таку велику таблицю в атласі, природно, неможливо.
Насамперед продовжимо (подумки) нашу таблицю на верхню частину, отримаємо МКР, симетричну відносно головної діагоналі і далі будемо мати на увазі саме таку таблицю. В цьому випадку, стовпець з деяким номером дорівнює рядку з таким же номером і все одно, яке з понять використовувати. Ми використовуємо і те, і інше, щоб їх перетинати між собою.
Наша МКР може бути: а) відома заздалегідь, тому що ми її підрахували одним з методів пошуку МКР; б) ми можемо не знати МКР, а визначати її через підрядник в міру необхідності. Підрядник - це значить, що для необхідної рядки розраховуються відстані лише від відповідної їй вершини до інших вершин, наприклад, методом Дейкстри.
3. Ще пара понять. Ексцентриситет даної вершини - це відстань від цієї вершини до найвіддаленішої від неї. Радіус графа - це найменший з ексцентриситетом всіх вершин. Центр графа - вершина, ексцентриситет якої дорівнює радіусу.
Як це виглядає на практиці. Центр дорожньої мережі - це місто або перехрестя, найменш віддалений від усіх інших пунктів цієї мережі. Радіус - максимальна відстань від цього центрального вузла до самого віддаленого.
4. Ступінь вершини - кількість ребер, яке приєднане до вершини.
У графів дорожніх мереж, середня ступінь всіх вершин знаходиться в районі від 2 до 4. Це цілком природно - складно і дорого будувати перехрестя з великою кількістю доріг, що примикають, не менше складно потім користуватися такою дорожньою мережею. Графи, з невисокою середнім ступенем вершин називаються розрідженими, як бачимо, графи дорожніх мереж саме такі.
Завдання 1. Пошук радіус і центру графа по матриці найкоротших відстаней
Зауважимо, що у графа може бути кілька центрів, але ми хочемо знайти будь-який з них.
Це далеко не найшвидший спосіб. Для чого потрібно швидше, якщо, здавалося б, радіус і центр графа можна знайти один раз? Наприклад, існують завдання і алгоритми на них, де в ході перебору вершини постійно «переоб'едіняются» в групи, а критерієм для кожної групи є її радіус. У цьому випадку радіус перераховується багаторазово, і швидкість його пошуку стає важливим параметром. Як знайти радіус швидше?
Подивимося, за рахунок чого це виходить. Розглянемо значення в одному рядку матриці МКР, іншими словами, розглянемо відстані від однієї вершини до всіх інших. Нескладно довести, що радіус графа не може бути більше ніж максимальне значення в цьому рядку, і не може бути менше ніж мінімальне значення в цьому рядку. Говорячи математично, ми знайшли верхню і нижню межу числа і якщо вони співпадуть - ми знайдемо число.
Припустимо, ми знайшли значення всього лише в двох рядках А та В. При цьому, максимальне значення в рядку А дорівнює мінімальному значенню в рядку В (ця величина буде стояти на перетині шпальти А і рядка В). Нескладно довести, що А - центр графа, а знайдене значення - його радіус. Завдання вирішена.
У загальному випадку і з точки зору математики це, звичайно, не так. Цілком можна побудувати теоретичний граф в якому доведеться використовувати дуже багато рядків В (майже всі, крім, А). Ось тільки неможливо побудувати реальну дорожню мережу такого виду - грошей не вистачить.
Залишилася остання задача. Як швидко знайти ці вдалі рядки B1, B2 і т.д. Для графів реальних дорожніх мереж це зробити дуже просто і швидко. Це будуть максимально віддалені один від одного вершини, але не обов'язково найвіддаленіші (кажучи математично, знаходити діаметр графа нам не потрібно). Беремо будь-яку вершину, знаходимо для неї найдальшу, для нової знову найдальшу і так, поки пара вершин не виявиться найдальшої один для одного.
Ми отримали пару вершин В1 і В2. Знаходимо для пари вектор М, як описано вище. Рядок, в якій ми знайшли min (M (i)) - претендент на центр, позначимо його А. Якщо в стовпці А значення min (M (i)) - максимальне, то вже знайдені центр і радіус. Якщо ж ні, значить максимальне значення в стовпці А відповідає відстані до іншої вершини (НЕ B1 і не B2). Значить, ми отримали нову вершину B3 в список на пошук вектора М. Як варіант, можна і для B3 пошукати найвіддаленішу вершину і якщо вона не В1 і не B2, додати її як В4. Таким чином, збільшуємо список вершин B, поки центр і радіус ні знайдено.
Завдання 2. Пошук матриці найкоротших відстаней
Найбільш популярні алгоритми пошуку МКР (Флойда-Уоршелла, наприклад) описані тут. Всі вони універсальні, причому один з них - алгоритм Дейкстри з двійковій купою - враховує таке поняття як розріджений граф. Однак він теж не використовує особливості дорожніх мереж.
Ми будемо їх використовувати і на зовсім іншому алгоритмі і на існуючих графах отримаємо прискорення в десятки разів у порівнянні з алгоритмом Дейкстри. Зауважимо відразу, що особливість цього алгоритму в тому, що шукає саме МКР, причому відразу всю і точно (тобто не наближено, що не евристичний).
Розглянемо основну ідею алгоритму. Суть її в тому, щоб видаляти вершини графа без зміни найкоротших відстаней для решти точок. Якщо ми будемо так робити, запам'ятовуючи до яких точках і на яких відстанях була приєднана віддалена вершина, то зможемо видалити всі точки, крім однієї, а потім зібрати їх назад в граф, але з уже підрахованими відстанями.
Почнемо з простого, з вершини зі ступенем 1. Її можна видалити в будь-якому випадку. Через неї не проходить ніяких найкоротших шляхів, крім шляхів до самої вершини, причому йдуть вони саме через ту вершину, до якої була приєднана видаляється вершина.
Нехай А - вершина зі ступенем 2 і приєднана вона в вершин В1 і В2. Якщо маршрут В1-А-В2 довше або дорівнює ребру В1-В2, через точку А не проходить ніяких маршрутів, крім маршрутів до самій точці А (всі інші проходять через В1-В2). Значить, точку А можна видалити. В іншому випадку, тобто якщо В1-А-В2 коротше В1-В2 або ребра В1-В2 взагалі немає, вершину А можна видалити, встановивши вага ребра В1-В2 рівним сумі ваг: | В1-А | + | А-В2 |. Маршрут від А до інших точок проходить або через В1, або через В2, якщо будуть відомі відстані для В1 і В2, відстані від А так же легко обчислити.
За таким же принципом можна видалити вершину з будь-яким ступенем, замінюючи, у міру необхідності, Вi-А-В j на Bi-Bj. Правда, потрібно розуміти, що чим більше ступінь вершини, тим більше можливих ребер треба перевірити. Для вершини ступеня n це число дорівнює n (n-1) / 2.
Теоретично, таким способом можна видалити всі вершини в будь-якому графі, однак, в загальному випадку, нас чекає неприємність, пов'язана з ростом числа ребер. При видаленні вершини зі ступенем n, ступінь вершин, суміжній з видаляється, може: зменшиться на -1, не змінитися, збільшиться до n-2. Звідси випливає, що при видаленні вершин зі ступенем 3 і вище, ступінь інших вершин, в загальному випадку, зростає, граф стає все менш розрідженим і, врешті-решт, видалення вершин перетвориться в досить трудомістке завдання. Алгоритм, в загальному випадку, є вкрай трудомістким і практично марним, але це саме в загальному випадку.
Графи дорожніх мереж мають унікальну особливість такого роду: багато вершин можуть бути видалені не тільки без зростання, але і зі зменшенням ступеня суміжних вершин. Причому, якщо деяка вершина не може бути «успішно» видалена зараз, вона може бути «успішно» видалена пізніше, після видалення деяких, суміжних з нею вершин.
Відповідно, нам просто потрібно на кожному кроці правильно вибирати вершини на видалення, починаючи з тих, які видаляються більш «вдало».
Сам алгоритм більш детально можна подивитися тут. Там описано, як видалити вершину, зберігаючи відстані та шляхи між рештою. Цей процес називається розбиранням. Там описано, як відновити потім граф назад, додаючи вершини в зворотному порядку по одній, як перераховувати при цьому МКР. Цей процес називається складанням.
Там же наведені результати використання алгоритму на графах дорожніх мереж США за посиланням.
Якщо розглядати дорожні мережі не як графи взагалі, а як графи з деякими особливими властивостями, можна створювати і успішно застосовувати більш ефективні алгоритми для багатьох практичних завдань.