В математиката, мрежата от пътища (пътни и други), представено претеглена графика. Места (или кръстовища) - това е върха, ръбове - път ръбове тегло - разстояния по тези пътища.
За претеглените графики той предлага много алгоритми. Например, популярен Дейкстра алгоритъм за намиране на най-краткия път от един връх в друг. Всички тези алгоритми имат общ принцип на (за математика) функция - те са универсални, т.е. може да се използва успешно за графиките на всеки дизайн. По-специално, за всеки алгоритъм, известен сложност - тя грубо съответства на увеличение на времето за изпълнение алгоритъм според броя на върховете. Всичко това може да се прочете в подробности, например в Уикипедия.
Да се върнем към практическите проблеми. Road е претеглена графика, но на пътя - това не е всеки графика. С други думи, тя не може да бъде на всяка графика за изграждане на пътна мрежа. За разлика от виртуална графика като математическа абстракция, пътища са построени от хора от действителните материали и са доста много пари. Така че те да не се поставят безразборно, но според някои икономически и практически правила.
Ние не знаем правилата, обаче, работи с пътни мрежи, е възможно да се използват алгоритми, които са в сила за пътища графики, въпреки че не е подходяща за универсален или графики в математическия смисъл на думата. Помислете два такива алгоритъм.
Няколко важни понятия и конвенции
1. Ние ще използва претеглените неориентирани графиките с не-отрицателни крайни тегла. По-специално, пътищата в областта (държавата) представляват точно такава графика.
2. матрица на кратки разстояния (MKR) - той е малък и прост пример може да се намери в много пътни атласи. Този етикет обикновено се нарича нещо като "разстоянието между най-важните градове." Изглежда, като част от матрицата е под или над главния диагонал (от горната лява до долната дясна), тъй като другата страна на главния диагонал са същите цифри, с други думи елемент М (I, J) = М (J, I). Това се случва, защото графиката, както казват математиците, ненасочена. Редовете и колоните съответстват на града (горната графика). В действителност, такава таблица е много по-голям, като връх, с изключение на градовете, включени всички села и кръстовищата, но за отпечатване на такава голяма маса в атласа, разбира се, е невъзможно.
Първата стъпка ще продължи да (психически), за да ни маса в горната част, получаваме MCR симетричен по отношение на главния диагонал, и ще продължи да имате предвид, е следната таблица. В този случай, номера на колоната е равна на някои съответствие с един и същ номер все пак, някои от понятията, използвани. Ние използваме нещо, а друг да бъде крос един с друг.
Нашата FIBC може да бъде: а) е известен предварително, защото сме го изчислява един от методите за търсене MKP; б) не можем да знаем CDM и го определи ред по ред, както е необходимо. Ред - това означава, че за желаната линия се изчисляват разстояние само от неговата съответна връх на други върховете, например, метод на Dijkstra.
3. Няколко понятия. Изместването на този възел - разстоянието от върха до най-отдалечените от нея. Граф Radius - е най-малката от ексцентричността на всички върхове. Граф център - отгоре, който е равен на радиуса на ексцентричност.
Как изглежда на практика. Център на пътната мрежа - това е град, или кръстовище, най-отдалечена от всички останали точки на мрежата. Радиус - максимално разстояние от този централен възел за устройството за дистанционно управление.
4. Степен на върховете - броят на ребра, който е свързан към горната част.
В графики на пътни мрежи, средната степен на всички върхове, разположени в зоната от 2 до 4. Това е съвсем естествено - това е трудно и скъпо да се изгради кръстовища с много захранващи пътища, не по-малко трудно след това да използвате тази пътна мрежа. Графики, с ниска средна степен на връх, са оскъдни, както можем да видим графики на пътни мрежи просто така.
Задача 1. графика търсене радиус и център матрични кратки разстояния
Имайте предвид, че на графиката може да бъде няколко центъра, но ние искаме да се намери нито един от тях.
Това не е най-бързият начин. Защо имате нужда от по-бързо, ако на пръв поглед радиус и център на графиката може да се намери един път? Например, има задачи и алгоритми по тях, където в хода на бюст върховете постоянно "pereobedinyayutsya" в групата, както и критериите за всяка група е радиуса. В този случай, радиусът се преизчислява по няколко пъти, и скоростта на неговото търсене се превръща във важен параметър. Как да се намери радиуса на бързо?
Нека да видим, поради което се получава. Помислете за ценностите в един ред MKP матрица, с други думи, помислете разстоянието от един връх до всички останали. Лесно е да се докаже, че радиусът на графиката не може да бъде по-голяма от максималната стойност на този ред, и не може да бъде по-малка от минималната стойност в този низ. Математически погледнато, ние открихме, горната и долната част на границата и ако те съвпадат - ние ще намерим броя.
Да предположим, ние открихме, стойността на само две редици А и В. В този случай, максималната стойност в линията А е равна на минималната стойност в ред Б (тази стойност ще бъде в пресечната точка на колона А и ред Б). Лесно е да се покаже, че A - граф център, и е установено, стойност - радиуса. Проблемът е решен.
Като цяло, от гледна точка на математиката, разбира се, не е така на. Възможно е да се конструира теоретично графика, в която е необходимо да се използва много линии (почти всички с изключение на А). Това просто не е възможно да се изгради реална пътна мрежа на този вид - не е достатъчно пари.
Имаше последната задача. Как бързо да намерите тези успешни линии В1, В2, и т.н. За графики недвижими пътна мрежа се извършва много лесно и бързо. Това ще бъде най-отдалечени един от друг на върха, но не непременно най-отдалечените (математически погледнато, ние откриваме, не се изисква от диаметъра на графиката). Вземете всеки връх, ние откриваме, за него най-отдалечената, за новото обратно най-отдалечената, и така, докато топ двойката няма да се появи най-далеч един от друг.
Имаме няколко върхове В1 и В2. Намираме вектор за двойка М, както е описано по-горе. Един ред, в която ние откриваме минути (М (I)) - претендент за центъра, обозначен с А. Ако в колона А стойност минути (М (I)) - максимум, сте намерили центъра и радиус. Ако не, тогава максималната стойност в колона А съответства на разстоянието до друг връх (не В1 и В2). Така че, ние имаме нов B3 върха на списъка, за да открие най-вектор М. Освен това, можете да търсите за B3 и най-далечното отгоре и ако това не е най-B1 и B2, го добавете като B4. По този начин, увеличаване на списъка на върховете B, а центърът и радиусът няма да бъде намерен.
Задача 2. Намерете най-късото разстояние матрицата
Най-популярната търсачка алгоритми MKR (Floyd-Uorshella, например) са описани тук. Всички те са универсални, а един от тях - Алгоритъм на Дейкстра с двоичен купчина - дава възможност за такова нещо като рядка графика. Въпреки това, той също не използва функциите на пътната мрежа.
Ние ще ги използват, и по съвсем различен алгоритъм и съществуващи колони ще бъдат ускорени в десетки пъти в сравнение с Алгоритъм на Дейкстра. Трябва да се отбележи веднага, че функцията на този алгоритъм е, че тя търси CDM и всички наведнъж и точно (т.е. приблизително, не евристично).
Помислете за основната идея на алгоритъма. Същността на това е да се отстранят върховете непроменени кратки разстояния за останалите точки. Ако направим това, спомняйки си за кой момент и на какво разстояние е бил прикрепен връх, ние можем да премахнете всички точки, с изключение на една, и след това да ги пуснат обратно в брой, но вече изчислява разстояния.
Ще започнем с един прост, от върха със степен на 1. Това може да бъде отстранен, така или иначе. Тя не минава през някои от най-кратките пътища, в допълнение към начините на върха, където и да отидат, е чрез върха, на който е прикрепен за сменяем върха.
Нека А - връх със степен 2, и е прикрепен към върховете В1 и В2. Ако маршрут В1-A-В2 е по-дълъг от или равна на ръб В1-В2 през точка А не премине всички маршрути, в допълнение към точка маршрут себе си на (всички други преминават през В1-В2). Така че, точка А може да бъде отстранен. В противен случай, т.е. ако В1-A-B2 къси В1-В2 и В1-В2 ребра не, възловата точка А може да бъде отстранен чрез определяне на теглото на В1-В2 ребра, равен на сумата от теглата: | В1-А | + | A-B2 |. Маршрут А до други точки или преминава през В1, В2 или чрез ще бъде известен, ако разстоянието за В1 и В2, разстоянието А е толкова лесно да се изчисли.
Същият принцип може да се отстрани от горната част на всяка степен, заместване, ако е необходимо, Bi-A-Vj да Bi-Bj. Въпреки това, той трябва да се разбира, че по-голяма е степента на върхове, толкова по-възможно е необходимо да се провери ребрата. За върховете на степен п е число, равно на п (п-1) / 2.
Теоретично, този начин можете да се премахнат всички върховете във всяка колона, но, като цяло, ние сме в очакване на проблеми, свързани с увеличаване на броя на ръбове. При изтриване на върховете, които имат степен п, степента на върховете, съседен на подвижен, може: намаление с 1, без промяна, се увеличи до N-2. От това следва, че при изтриване на върховете на степен 3 и по-висока, степента на останалите върхове, като цяло, се увеличава, графиката става по-малко само за посветени и, в крайна сметка, премахване на върховете се превръщат в доста трудоемка задача. Алгоритъмът, като цяло, отнема изключително много време и на практика безполезна, но това е в най-общия случай.
Брои на пътни мрежи са уникална функция на този вид: много от върха може да се отстрани, не само без растеж, но също така и намаляване на степента на близост. Освен това, ако определена възлова точка може да бъде "успешно" отстранява сега, това може да бъде "успешно" отстранява по-късно, след отстраняването на някои свързани с тях върхове.
Съответно, ние просто трябва да изберете в началото на всеки етап от премахването на правото, като се започне с тези, които са изтрити повече "успешен".
Алгоритъмът може да бъде видяна тук по-подробно. Там е описано как да изтриете връх, запазвайки разстоянието и пътя между останалите. Този процес е известен като демонтаж. Те обясняват как да се възстанови броят тогава, добавяйки върха в обратен ред, един е да брои с механизма за чисто развитие. Този процес се нарича монтаж.
Също така са дадени резултатите от използване на алгоритъма на графики САЩ пътна мрежа връзка.
Ако ние считаме, пътната мрежа като цяло е като графит, графит и с някои специфични качества, можете да създадете и успешно се използва по-ефективни алгоритми за много практически проблеми.
Свързани статии