MLD

3. ноември 2013

Алгоритъмът на Дейкстра, публикуван през 1959, е класически метод за търсене на най-къс път в граф. Може да се използва върху всеки граф с неотрицателни тегла на ребрата. Приложен върху пътна мрежа („върхове“ са кръстовищата, „ребра“ — пътищата между тях, а „тегло“ на ребрата mdash; времето за пътуване), сам по себе си е неудобно бавен. Проблемът е, че ако търся например най-бързия път от Карлсруе до Берлин (около шест часа), алгоритъмът трябва да мине през всички места, където мога да отида за шест часа. Тоест, по някое време алгоритъмът ще се мотае из улиците на Париж, Милано и Амстердам, търсейки някакъв таен тунел, по който мога да стигна оттам до Берлин за по-малко от час. Звучи тъпо, но все пак алгоритъмът трябва да работи върху всякакви графи, включително такива, където подобни ситуации са възможни.

Използвайки допълнителна факти, известни за пътната мрежа, има различни методи да се ускори търсенето (говорим за това да стане няколко милиона пъти по-бързо). В общи линии идеята е предварително да се пресметне някаква информация, която после да се използва за ускоряване на отделните запитвания. Един от начините е да се използва MLD, или Multi-Level Dijkstra, т.е. многослойна Дейкстра. За тази цел графът се разбива на части - например по държавните граници. За всяка държава се пресмята най-краткия път от всеки граничен пункт до всеки друг. Когато се търси път от една точка до друга, най-напред се намират най-кратките пътища от началната точка до всички гранични пунктове на началната държава, след това от всички гранични пунктове на крайната държава до целта, и накрая се работи само върху един малък граф, който съдържа само граничните пунктове. Това се прави на няколко нива - например държавите се разделят по същия начин на области и т.н. Давам държавните граници само като лесно разбираем пример, иначе те не са непременно удобни разделители — целта е отделните разделения да са слабо свързани помежду си, съответно силно свързани вътрешно, и да са относително еднакви по размер.

Като част от дипломната си работа трябва да модифицирам едно MLD, така че да може да прави и още нещо, освен да търси най-кратки пътища. Кодът е много оплетен и съм заседнал на това от месеци насам. Започвам да се отчайвам и същевременно да се вбесявам... едно такова гадно смесено чувство...