Намиране на най-краткия път в източниците на транспортния граф (концепция).
Веднъж имах проект, който беше свързан с карта на града. И възникна идеята, че след като има карта с маршрути и съответните спирки на градския транспорт, защо да не потърсиш път от точка А до точка Б на нея.
Тъй като хардуерът, където е трябвало да бъде поставен софтуерът, е с изключително тесен интернет канал, търсенето би трябвало да се извършва изцяло локално, тоест без ангажиране на капацитета на сървъра. Освен това, разбира се, исках да не губя вниманието на потребителя и да му дам резултата възможно най-бързо.
Около час-два седях и не можех да измисля нищо и тогава ми хрумна идеята да смятам маршрута не колкото спирки, а като 1 точка. И ако свия маршрутите до точка, тогава получавам много проста графика. Идеята изглеждаше добра и ми хареса.
Първото нещо, което направих, беше да анализирам транспортни маршрути от сайтове. После се зае с броенето. Това се оказа не трудна задача, вземаме всяка спирка от маршрута и виждаме дали има спирки от друг маршрут в посочения от нас радиус. Радиусът взе 600 м (в последната версия 400 м) - приблизителното разстояние, което човек може да извърви безболезнено пеша от една спирка до друга, ако се наложи прекачване. Това разстояние вероятно може да се намали до да речем 200 м, тъй като разстоянието от една спирка до друга на кръстовището не надвишава това разстояние.
И така, след всички тези манипулации, получих графика, чрез която можете бързо да изградите път от един маршрут до друг. Така получихме графика, която съхранява информация за преходите от един градски транспортен маршрут към друг, нещо като метаграф.
В продължение на няколко месеца алгоритъмът беше пренаписанняколко пъти, тогава ще ви разкажа повече за най-новото внедряване.
Средно време, прекарано в стъпки:
gpt - 0,009 s, намиране на най-близките спирки до точката на щракване grt - 0,001 s, намиране на най-краткия път от маршрута до маршрута apt - 0,0001 s, добавяне на спирки и точки за завой към нашия маршрут всички - 0,01 s, общо време за завършване на търсенето на пътя
Разполагаме с определена карта на града, върху която са нанесени маршрутите на обществения транспорт (90 маршрута) и координатите на съответните спирки, принадлежащи към тези маршрути.
На картата маршрутите изглеждат така:
Данните са представени под формата на следните таблици:
За да не губим време в изчисляване на разстоянието между спирките (в рамките на 1 маршрут) всеки път, когато търсим маршрут, ние го изчисляваме предварително и го записваме в съответната таблица. Вземете таблицата с разстоянията:
След това ще изградим метаграф на преходи, т.е. ще намерим онези спирки на маршрута, в радиуса на които има спирки от други маршрути. Както вече отбелязах, избрах радиус от 400 метра. Резултатът от обработката ще бъде записан в таблицата:
качване на данни в php
Всички мои софтуерни реализации, изградени на базата на MYSQL, бяха много бавни. Реших да се отдалеча от базата. Разтоварих данните в масив и реших да работя през сокета. В моя случай качените данни заемат около 19 MB RAM. Основният масив е масивът $graf. Това е 3D масив, чиито ключове са:
- 1-ви ключов маршрут, от който сменяме
- 2-ри ключ, на който сменяме
- 3-та трансферна точка
Тъй като спирката на един маршрут може да попадне между 2 спирки на друг или маршрутите се докосват в повече от 1 точка, ще получим много опции за трансфери.Така че $v1, $v2 са тези трансплантации.
Също така в паметта има масив с разстояния вътре в маршрута, т.е. масив от формата: $routeDistance[$ > Къде:
- $idRoute - id на нашия маршрут,
- $pFrom - спирка, от която да тръгнете,
- $pTo - спрете къде да отидете,
- (float) – стойност на пътя в абстрактни единици.
Намиране на път
За да започнем търсенето, трябва да намерим спирката, от която ще тръгнем и къде. След като намерим най-близките спирки откъде ($idFrom) и къде ($idTo) да отидем, установихме принадлежността на спирките към маршрутите, ще се опитаме да намерим пътя.
За да намерите маршрут с 1 прекачване:
Търсенето на път, например, с 2 прехвърляния се изпълнява по следния начин:
Съответно, за да намерим пътя, например, с 3 прекачвания, пишем както следва:
След тези операции получаваме набор от маршрути като $id1 -> $id2 -> $id3 -> $id4. Където $id* е идентификаторът на маршрута. След това трябва да разберем кой начин е най-бързият. Имаме начална спирка ($pStart) и крайна спирка ($pEnd). Също така, според таблицата $graf, знаем точките на трансфери (от къде, до къде и разстоянието) това са нашите стойности $v1, $v2. Подпишете $id1 -> $id2. Към тях добавяме данни за всички трансплантации:
Малко очевидно, за да оцените маршрута, трябва да добавите всичко:
$routeDistance[$id1][$pStart][$v1['from']] – разстояние вътре в маршрута. $v1['distance'] - колко време отнема прехвърлянето, също в абстрактни единици.
Съответно минималната стойност на изчислените суми, това ще бъде нашият желан път. След това възстановяваме спирките, които са вътре в маршрута, но се намират между точката на влизане в маршрута и изхода от него.
За удобство ще изберем няколко маршрута:
Сгъване на маршрути в точкии вземете графиката:
Да предположим, че трябва да стигнем от 2 до 5 маршрут. Според нашата графика ще получим следната селекция от пътища:
След това работим с получените маршрути. Трябва да разберем кой от маршрутите е "най-бързият".
Изчисляване на стойността на привлекателността на маршрута:
- Взимаме началната спирка на маршрута и всички възможни спирки за прехвърляне към друг маршрут. Използвайки таблицата route_distance, намираме дължината на пътя от началната спирка в рамките на маршрута до спирката за прекачване.
- Сега трябва да вземете предвид времето за трансплантация. Към изчислената дължина в съответствие с таблицата route_cross_point добавяме дължината между спирката, от която прекачваме, и спирката, до която прекачваме.
- Повтаряме за всеки маршрут.
Нека вземем първия ред от нашата извадка
$routeDistance[2][p.1][ p.3] + d1 + $routeDistance[3][p.5][ p.6] + d3 + $routeDistance[5][p.7][ p.8] = (float) $routeDistance[2][p.1][ p.4] + d2 + $routeDistance[3][p.5][ p.6] + d3 + $routeDistance tance[5][p. 7][ p.8] = (float) $routeDistance – разстояние в рамките на маршрута. d* — време за прехвърляне. стр.1 - спрете от мястото, където отиваме. стр.8 – спрете там, където отиваме. d1 – разстояние между т.3 и т.5
Минималният брой е най-добрият начин.
Какво липсва и как може да се подобри:
- докато алгоритъмът вземе предвид съществуващата пътна мрежа и не положи пешеходен маршрут от точка А до спирка на транспорта и съответно от последната спирка на обществения транспорт от получения маршрут до точка Б; - разбира се, можете също да изчислите цената на маршрутите в бъдеще и, ако е необходимо, да въведете избор на критерий, по който да изберете маршрут (минимална цена, време, трансфери и т.н.), докато по подразбиранеприемете целевия критерий за минимум трансфери; — ако бяха въведени тарифи, които зависят от дължината на маршрута, тогава не би трябвало да се добавя много към алгоритъма;
Изтегляне на източници. Разопаковайте. Пътят не трябва да съдържа български символи.
Hardcore conf в C++. Каним само професионалисти.