किसी डेटाबेस से निकाले गए डेटा के साथ सबसे कम पथ की गणना करना

इसलिए मुझे एक वेब सेवा बनाने की ज़रूरत है जो मेरे एंड्रॉइड के साथ संवाद करेगी आवेदन। मेरे एंड्रॉइड ऐप में ग्राहक दो बिंदु शुरू करते हैं और बस खोजने के लिए यह दो बिंदु मेरी वेब सेवा को भेजा जाएगा उनके बीच सबसे छोटा रास्ता है। मुझे वेब के साथ समस्या है सेवा पक्ष

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

मेरे डेटाबेस में मेरे पास दो टेबल हैं जिनमें बस मार्ग (बस संख्या) है, कोड (स्टेशन आईडी), pt_arret (स्टेशन का नाम)। एक और टेबल है जो स्थान कोड (आईडी स्टेशन), अक्षांश और देशांतर, और शामिल हैं दूरी (एक स्टेशन और स्टेशन के बीच की दूरी है पहले होती है।

0
जोड़ा संपादित
विचारों: 1
(मुझे वर्तनी के गलत होने के लिए खेद है क्योंकि मैं अंग्रेजी को बहुत तेज़ी से नहीं बोलता)
जोड़ा लेखक olfa, स्रोत
कृपया आप अपना प्रश्न सही तरीके से प्रारूपित करने, पूंजीकरण और विरामित करने के लिए समय ले सकते हैं। धन्यवाद।
जोड़ा लेखक NPE, स्रोत

1 उत्तर

आपको एक संरचना बनाना है जो आपको डिजस्ट्रा के एल्गोरिदम का उपयोग करने देगा। ऐसा करने के लिए, आपको डेटाबेस से संबंधित डेटा सभी को पढ़ना होगा। रिलेशनल डेटा से उन्मुख ऑब्जेक्ट में संक्रमण हमेशा अजीब होता है।

आदर्श रूप से आप डेटा प्राप्त करने के लिए प्रति एकल एक सरल, सरल SQL चयन का उपयोग करना चाहते हैं। अनुकूलन मुश्किल है। एक भी चुनिंदा बयान लगभग दस लाख पंक्तियों को तेज़ी से पकड़ सकता है क्योंकि यह एक पंक्ति को पकड़ सकता है; एक चयन में 10 चुनौतियों की तुलना में दस लाख पंक्तियां तेजी से 10 पंक्तियां (मेरे अनुभव में) पकड़ लेंगी। लेकिन यदि आपके डीबी कनेक्शन धीमे हैं (एक संकीर्ण बैंडविड्थ है) तो बहुत अधिक असीमित पंक्तियों को पकड़ना बहुत लंबा लग सकता है।

आप जो पढ़ते हैं उसका ट्रैक रखने के लिए मानचित्र (ट्रीमैप या हैश मैप) का उपयोग करें, ताकि आप "स्टेशन" ऑब्जेक्ट्स पा सकें जो पहले से ही पढ़ी गई हैं और आपकी संरचना में रखी गई हैं और उनसे कनेक्शन जोड़ती हैं।

एक बार जब आप अपनी डेटा संरचना को स्मृति में स्थापित कर लेते हैं, तो डेटाबेस को रीड्रेड करने में देरी को सीमित करने के लिए इसे यथासंभव लंबे समय तक रखने की कोशिश करें।

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

उम्मीद है की यह मदद करेगा। यदि आपने पहले ऐसा कुछ नहीं किया है, तो आपके पास बहुत काम है और आपसे आगे सीखना है। मैंने इस तरह के एक बड़े कार्यक्रम पर काम किया (लेकिन यह भी लिखा डीबी में लिखा गया), और मुझे लगा जैसे मैं ऊपर की तरफ तैर रहा था।

अतिरिक्त:

आप स्मृति में क्या चाहते हैं स्टेशनों (स्टेशन वर्ग वस्तुओं) और मार्गों (मार्ग वर्ग वस्तुओं) का एक सेट है। प्रत्येक स्टेशन में सभी डेटा होंगे जो आपको स्थानों सहित एक स्टेशन का वर्णन करने के लिए आवश्यक हैं। गंभीरता से, इसे एक आईडी की भी आवश्यकता होगी। स्टेशनों को आईडी के रूप में उपयोग करके ट्रीमैप में जाना चाहिए। (यह मेरी पूर्वाग्रह है, कई लोग हैश मैप का उपयोग करेंगे।)

प्रत्येक मार्ग में दो स्टेशनों, एक दूरी या यात्रा के समय, और किसी भी अन्य आवश्यक जानकारी के संदर्भ होंगे।

प्रत्येक स्टेशन भी में संदर्भित मार्गों की एक सूची होगी। मैं लचीलापन के लिए एक लिंक्डलिस्ट की सिफारिश करता हूं। (इस मामले में, ArrayList अप्रयुक्त सरणी तत्वों के साथ बहुत सी जगह बर्बाद करने के लिए उपयुक्त है।) आप डीबी से स्टेशनों को पढ़ना चाहते हैं, फिर मार्ग जानकारी पढ़ें। जैसे ही आप प्रत्येक मार्ग की जानकारी पढ़ते हैं, रूट ऑब्जेक्ट बनाएं, दो स्टेशनों का पता लगाएं, रूट पर संदर्भ जोड़ें, फिर दोनों स्टेशनों की रूट सूचियों में रूट जोड़ें।

अब प्रत्येक स्टेशन के लिए आप इसे छोड़कर सभी मार्गों को खोज सकते हैं, और फिर उन सभी स्टेशनों को खोज सकते हैं जिन्हें आप एक बस यात्रा के साथ प्राप्त कर सकते हैं। उन स्टेशनों से, आप अपने नेटवर्क के माध्यम से अपना रास्ता काम कर सकते हैं। यदि आप इस तरह से सोचना चाहते हैं तो यह संरचना वास्तव में एक "स्पैस सरणी" है।

डिजस्ट्रा के एल्गोरिदम को लागू करना - या कोई अन्य एल्गोरिदम - काफी सरल है। आप विभिन्न उद्देश्यों के लिए पहले से उपयोग किए जाने वाले नोड्स (स्टेशन) और कनेक्शन (मार्ग) ट्रैक करने के लिए स्टेशनों और मार्गों (स्टेशन और रूट कक्षाओं में फ़ील्ड) पर विभिन्न झंडे चाहते हैं। यह आपके कोड को क्या कर रहा है, यह जानने के लिए पेपर की एक शीट पर नक्शा खींचने में मदद कर सकता है (एक छोटे से शुरू करें!)। मेरा अनुभव यह रहा है कि यह सब करने के लिए बहुत कम कोड लेता है, लेकिन यह बहुत सावधान विचार लेता है।

0
जोड़ा
मुझे खेद है, लेकिन मैं जानना चाहता हूं: इस ws को बनाने के लिए मुझे आवश्यक कक्षाएं और कार्य क्या हैं .?? क्योंकि यह मेरा पहला डब्ल्यूएस है, और मुझे नहीं पता कि इस समस्या का विश्लेषण कैसे करें।
जोड़ा लेखक olfa, स्रोत
कोई ऐसा व्यक्ति है जिसने मुझे ऐसा करने की सलाह दी:
जोड़ा लेखक olfa, स्रोत
थ्रेस कुछ ऐसा है जिसने मुझे ऐसा करने की सलाह दी: डिजस्ट्रा के एल्गोरिदम का उपयोग करने के लिए आपको दूरी मैट्रिक्स तैयार करने की आवश्यकता है। यह सभी स्टेशनों के बीच दूरी की एक द्वि-आयामी सरणी है। प्रीफर्ड समाधान है: 1. दोनों टेबल को स्मृति में पॉको डेटा ऑब्जेक्ट्स के रूप में लोड करें। 2. दूरी मैट्रिक्स की गणना करें (यदि आप कर सकते हैं - बड़ी मेमोरी उपयोग से बचने के लिए एक स्पैरस मैट्रिक्स बनाएं)। 3. डिजस्ट्रा के एल्गोरिदम को कॉल करें .... तो जहां MySQL (wich वर्ग में) से डेटा निकालना चाहिए? मुझे खेद है लेकिन मुझे मदद चाहिए :(
जोड़ा लेखक olfa, स्रोत
आपकी सलाह के लिए बहुत बहुत धन्यवाद :) मैं इसे कोड में अनुवाद करने की कोशिश करूंगा, लेकिन अगर आप एक ट्यूटोरियल जानते हैं जो मुझे मदद कर सकता है तो मुझे यूआरएल भेजने की परेशानी न करें, क्योंकि मैं शुरुआत कर रहा हूं और मुझे नहीं पता कि मैं इसे खरोंच से बना सकते हैं। वैसे भी मैं कोशिश करूँगा और आपको फिर से धन्यवाद :)
जोड़ा लेखक olfa, स्रोत
आपकी मदद के लिए बहुत बहुत धन्यवाद :) मुझे आशा है कि मुझे जितनी जल्दी हो सके समाधान मिल जाए क्योंकि मैंने शोध में बहुत समय और 11 दिनों के बाद रिपोर्ट खो दी :(: (.... फिर से धन्यवाद :)
जोड़ा लेखक olfa, स्रोत
@olfa: आपको किस क्षेत्र में सहायता चाहिए? मैं आपकी मदद करने के लिए वेब सेवाओं और एंड्रॉइड को अच्छी तरह से नहीं जानता। मैं एसक्यूएल, जावा, और डिजस्ट्रा के एल्गोरिदम को कार्यान्वित करने के बारे में थोड़ा और विशिष्ट हो सकता हूं।
जोड़ा लेखक RalphChapin, स्रोत
@olfa: क्षमा करें, लेकिन मैं आपको समझ में नहीं आता।
जोड़ा लेखक RalphChapin, स्रोत
@olfa: ध्वनि सलाह। मैंने अपने उत्तर में इसकी व्याख्या को जोड़ा है। आपको थोड़ा और आगे मिलना चाहिए।
जोड़ा लेखक RalphChapin, स्रोत