परिवहन ग्राफ (अवधारणा) + स्रोत में सबसे छोटा रास्ता खोजें

मेरे पास एक बार एक प्रोजेक्ट था जो शहर के नक्शे के साथ जुड़ा हुआ था। और यह विचार उत्पन्न हुआ कि चूंकि मार्गों और सार्वजनिक परिवहन के संगत स्टॉप के साथ एक नक्शा है, तो उस पर बिंदु A से बिंदु B तक के रास्ते की खोज क्यों न करें।

चूंकि हार्डवेयर, जहां यह स्थित होना चाहिए था, एक बहुत ही संकीर्ण इंटरनेट चैनल है, खोज को पूरी तरह से स्थानीय स्तर पर करना होगा, अर्थात, सर्वर क्षमताओं को शामिल किए बिना। इसके अलावा, निश्चित रूप से, मैं उपयोगकर्ता का ध्यान नहीं खोना चाहता था और उसे जितनी जल्दी हो सके परिणाम दे सकता था।

लगभग एक या दो घंटे के लिए मैं बैठा रहा और कुछ भी नहीं सोच सका, और फिर यह विचार आया कि मैं मार्ग पर विचार कर सकता हूं, न कि कई स्टॉप, बल्कि 1 बिंदु के रूप में। और अगर मैं मार्गों को एक बिंदु पर मोड़ता हूं, तो मुझे एक बहुत सरल ग्राफ मिलता है।
विचार अच्छा लगा, और मुझे अच्छा लगा।

पहली बात यह थी कि साइटों से मार्गों को परिवहन करना था। फिर उसने गिनती पर काम करने की ठानी।
यह एक मुश्किल काम नहीं था, हम मार्ग के हर पड़ाव को लेते हैं और देखते हैं कि निर्धारित त्रिज्या में किसी अन्य मार्ग के ठहराव हैं या नहीं। त्रिज्या ने 600 मीटर (नवीनतम संस्करण 400 मीटर में) लिया - अनुमानित दूरी जो एक व्यक्ति को एक स्टॉप से ​​दूसरे स्थान पर पैर में दर्द के बिना चल सकता है अगर हस्तांतरण की आवश्यकता होती है। संभवतः, यह दूरी कम हो सकती है, कहते हैं, 200 मीटर तक, चौराहे पर एक स्टॉप से ​​दूसरे तक की दूरी इस दूरी से अधिक नहीं होती है।

इसलिए, इन सभी जोड़तोड़ के बाद, मुझे एक ग्राफ मिला, जिसके अनुसार आप जल्दी से एक मार्ग से दूसरे मार्ग का निर्माण कर सकते हैं। इस प्रकार, हमें एक ग्राफ मिला है जो एक शहरी परिवहन मार्ग से दूसरे तक के बदलावों के बारे में जानकारी संग्रहीत करता है, एक तरह का मेटा-ग्राफ।

कई महीनों के लिए, एल्गोरिथ्म को दो बार फिर से लिखा गया था, फिर मैं नवीनतम कार्यान्वयन के बारे में अधिक विस्तार से बात करूंगा।

वीडियो की गुणवत्ता भयानक है, लेकिन मुझे यह नहीं मिला है कि इसे बेहतर कैसे बनाया जाए।



चरणों को पूरा करने में लिया गया औसत समय:

gpt - 0.009 s, क्लिक बिंदु पर निकटतम स्टॉप का पता लगाएं
grt - 0.001, मार्ग से मार्ग का सबसे छोटा मार्ग खोजें
उपयुक्त - 0.0001, हमारे मार्ग में स्टॉप और टर्निंग पॉइंट्स जोड़ें
सभी - 0.01 सी, कुल पथ खोज निष्पादन समय

जानकारी:

हमारे पास शहर का एक निश्चित नक्शा है, जिसके साथ शहर के परिवहन मार्ग (90 मार्ग) मुद्रित हैं और इन मार्गों से संबंधित संगत स्टॉप के निर्देशांक हैं।

मानचित्र पर, मार्ग इस तरह दिखते हैं:

Php में डेटा अपलोड करें

मेरे सभी MYSQL- आधारित सॉफ्टवेयर कार्यान्वयन बहुत धीमे थे। मैंने बेस से दूर जाने का फैसला किया। मैंने डेटा को एक सरणी में अनलोड किया और सॉकेट के माध्यम से काम करने का फैसला किया। मेरे मामले में, अपलोड किए गए डेटा में लगभग 19MB RAM लगता है।
मुख्य सरणी हमारी $ ग्रेफ सरणी है। यह कुंजियों की त्रि-आयामी सारणी है जिसमें:

• 1 मुख्य मार्ग जिससे हम बदलते हैं
• दूसरी कुंजी जिसमें हम बदलते हैं
• तीसरा स्थानान्तरण बिंदु

  $r = $this->db->query(' select routeFrom rf, routeTo rt, markerFrom mf, markerTo mt, distance d from route_cross_points RCP '); $kf = 0; foreach($r as $k => $v) { $this->graf[(int)($v['rf'])][(int)($v['rt'])][] = array((int)($v['mf']), (int)($v['mt']), (float)($v['d'])); } $graf[$idFrom][$idTo] = array( 0 => $v1, //  ,        1 => $v2 //  ,        ..... ); 

चूंकि एक मार्ग का ठहराव दूसरे के 2 पड़ावों के बीच गिर सकता है या मार्ग 1 से अधिक बिंदु पर स्पर्श करते हैं, इसलिए हमें स्थानान्तरण के कई विकल्प मिलेंगे। तो, $ v1, $ v2 ये स्थानान्तरण हैं।

स्मृति में भी मार्ग के भीतर दूरी के साथ एक सरणी है, अर्थात्, फार्म का एक सरणी:
$ मार्गडिस्टेंस [$ idRoute] [$ pFrom] [$ pTo] = (फ्लोट);
जहां:

• $ idRoute - हमारे मार्ग की आईडी,
• $ pFrom - किसके साथ जाना है,
• $ pTo - जहां जाने के लिए रुकें,
• (फ्लोट) - सार इकाइयों में पथ का मूल्य।

  $rt = $this->db->query(' select route_id rni, POINT1 p1, POINT2 p2, distance d from route_distance '); foreach($rt as $k => $v) { $this->routeDistance[(int)($v['rni'])][(int)($v['p1'])][(int)($v['p2'])] = (int)($v['d']); } 

रास्ता खोजो

खोज शुरू करने के लिए हमें एक पड़ाव खोजने की जरूरत है जिसके साथ हम जाएंगे और कहां। हमने ($ idFrom) और जहाँ ($ idTo) जाने के लिए निकटतम स्टॉप पाया, हमने स्थापित किया कि स्टॉप मार्गों से संबंधित हैं, रास्ता खोजने का प्रयास करें।

1 परिवर्तन वाला मार्ग खोजने के लिए:

  if(isset($graf[$idFrom][$idTo])) { //      1   . } 

एक पथ के लिए एक खोज, उदाहरण के लिए, 2 स्थानान्तरण के साथ, इस तरह से लागू किया जाता है:

  foreach($graf[$idFrom] as $keyOne => $one) { if(isset($graf[$idTo][$keyOne])) { //        ,   ,        . } } 

तदनुसार, एक मार्ग खोजने के लिए, उदाहरण के लिए, 3 स्थानान्तरण के साथ, निम्नानुसार लिखें:

  foreach($graf[$idFrom] as $keyOne => $one) //             { foreach($graf[$idFrom] as $keyTwo => $two)//           { if(isset($graf[$keyOne][$keyTwo])){ } } } 

इन ऑपरेशनों के बाद, हमें $ id1 -> $ id2 -> $ id3 -> $ id4 के मार्गों का एक सेट मिलता है। जहाँ $ id * मार्ग आईडी है।
इसके बाद, हमें यह समझने की जरूरत है कि कौन सा रास्ता सबसे तेज है। हमारे पास एक स्टार्ट स्टॉप ($ pStart) और एक एंड स्टॉप ($ pEnd) है। इसके अलावा, $ ग्राफ तालिका से, हम हस्तांतरण बिंदुओं को जानते हैं (जहां, जहां और दूरी) $ v1, $ v2 के हमारे मूल्य हैं।
मैं $ id1 -> $ id2 के लिए लिखूंगा। उन्हें सभी स्थानान्तरणों पर डेटा में जोड़ें:

  $id1($pStart, $v1['from']) -> $id2($v1['to'], $pEnd) $id1($pStart, $v2['from']) -> $id2($v2['to'], $pEnd) $id1($pStart, $v3['from']) -> $id2($v3['to'], $pEnd) 

थोड़ा स्पष्ट, उस मार्ग का मूल्यांकन करने के लिए जिसे आपको सब कुछ जोड़ने की आवश्यकता है:

  $routeDistance[$id1][$pStart][$v1['from']] + $v1['distance'] + $routeDistance[$id2][$v1['to']][$pEnd]; $routeDistance[$id1][$pStart][$v2['from']] + $v2['distance'] + $routeDistance[$id2][$v2['to']][$pEnd]; $routeDistance[$id1][$pStart][$v3['from']] + $v3['distance'] + $routeDistance[$id2][$v3['to']][$pEnd]; 

$ मार्गडिस्टेंस [$ id1] [$ pStart] [$ v1 ['से']] - मार्ग के अंदर की दूरी।
$ v1 ['दूरी'] - कितना समय रोपाई में लगाया जाता है, अमूर्त इकाइयों में भी।

तदनुसार, गणना की गई राशियों का न्यूनतम मूल्य, यह हमारा वांछित पथ होगा। फिर हम उस स्टॉप को बहाल करते हैं जो मार्ग के अंदर हैं, लेकिन मार्ग में प्रवेश करने और उससे बाहर निकलने के बिंदु के बीच हैं।

उदाहरण

सुविधा के लिए, हम कई मार्ग चुनेंगे:



हम मार्गों को बिंदुओं में बदलते हैं और ग्राफ प्राप्त करते हैं:



मान लें कि हमें मार्ग 2 से 5 की आवश्यकता है।
हमारे ग्राफ के अनुसार, हमें ऐसे रास्तों का चयन करना है:



आगे हम प्राप्त मार्गों के साथ काम करते हैं। हमें यह पता लगाने की जरूरत है कि कौन सा मार्ग सबसे तेज है।

मार्ग के "आकर्षण" के मूल्य की गणना:

1. हम मार्ग की शुरुआत का रास्ता रोकते हैं और दूसरे मार्ग में स्थानांतरण के सभी संभावित ठहराव होते हैं। Path_distance तालिका का उपयोग करते हुए, हम मार्ग के भीतर प्रारंभ स्टॉप से ​​स्थानांतरण के स्टॉप तक की लंबाई पाते हैं।
2. अब आपको प्रत्यारोपण के लिए समय पर विचार करने की आवश्यकता है। मार्ग_क्रॉस_पॉइंट तालिका के अनुसार गणना की गई लंबाई को उस स्टॉप के बीच जोड़ें, जिसके साथ हम बदल रहे हैं और जिस स्टॉप के लिए हम बदल रहे हैं।
3. प्रत्येक मार्ग के लिए दोहराएँ।

हमारे नमूने से पहली पंक्ति लें



$ मार्गडिस्टेंस [2] [p.1] [p.3] + d1 + $ मार्गडिस्टेंस [३] [p.5] [p.6] + d3 + $ मार्गडिस्टेंस [५] [p.7] [p.8] ] = (फ्लोट)
$ मार्गडिस्टेंस [2] [p.1] [p.4] + d2 + $ मार्गडिस्टेंस [३] [p.5] [p.6] + d3 + $ मार्गडिस्टेंस [५] [p.7] [p.8] ] = (फ्लोट)
$ मार्गडिस्टेंस - मार्ग के भीतर की दूरी।
डी * - प्रत्यारोपण के लिए समय।
p.1 - जहां हम जा रहे हैं वहां रुकें।
p.8 - जहां हम जा रहे हैं उसे रोकें।
d1 - p.3 और p.5 के बीच की दूरी

न्यूनतम संख्या सबसे अच्छा तरीका है।

क्या गायब है और कैसे विकसित करना है:

- जबकि एल्गोरिथ्म सड़कों के मौजूदा नेटवर्क को ध्यान में नहीं रखता है और परिवहन ए से स्टॉप तक एक पैदल यात्री मार्ग नहीं रखता है और, तदनुसार, प्राप्त मार्ग से प्वाइंट बी तक सार्वजनिक परिवहन के अंतिम पड़ाव से;
- बेशक, आप आगे मार्गों की लागत की गणना कर सकते हैं और यदि आवश्यक हो, तो वैकल्पिक रूप से मापदंड का विकल्प दर्ज करें जिसके द्वारा एक मार्ग (न्यूनतम लागत, समय, स्थानान्तरण, आदि) चुनने के लिए, जबकि डिफ़ॉल्ट रूप से हम लक्ष्य मानदंड बनने के लिए न्यूनतम हस्तांतरण परिवर्तनों पर विचार करते हैं;
- यदि मार्ग की लंबाई के आधार पर किराए की शुरुआत की गई थी, तो एल्गोरिथ्म को जोड़ने के लिए बहुत कुछ नहीं होगा;

स्रोत डाउनलोड खोल दे। पथ में रूसी वर्ण नहीं होना चाहिए।