خوارزمية ديكسترا للآيفون

https://stackoverflow.com/questions/876623

22-08-2019
|

سؤال

من الممكن استخدام وظيفة GPS في iPhone بسهولة منذ إصدار sdk 3.0، ولكن يُحظر صراحةً استخدام خرائط Google.وهذا له نتيجتان في اعتقادي:

سيكون عليك تقديم الخرائط بنفسك
سيكون عليك حساب أقصر الطرق بنفسك.

أعلم أن حساب أقصر طريق قد حير علماء الرياضيات على مر العصور، لكن توم توم وجوجل يقومان بعمل رائع، لذا يبدو أن هذه المشكلة قد تم حلها.أثناء البحث على شبكة الإنترنت، ولأنني لست عالم رياضيات، عثرت على خوارزمية ديكسترا.هل هناك أحد منكم نجح في استخدام هذه الخوارزمية في تطبيق يشبه الخرائط في iPhone؟هل ستكون على استعداد لمشاركتها معي/مع المجتمع؟هل سيكون هذا هو النهج الصحيح، أم هي الخيارات الأخرى؟شكرا جزيلا للنظر فيها.

المحلول

تهدف خوارزمية Dijkstra إلى العثور على أقصر مسار لجميع العقد (من عقدة بداية واحدة).يستخدم مبرمجو الألعاب بحثًا موجهًا مثل A*.حيث تقوم Dijkstra بمعالجة العقدة الأقرب إلى موضع البداية أولاً، تقوم A* بمعالجة العقدة التي يُقدر أنها الأقرب إلى موضع النهاية

الطريقة التي يعمل بها هذا الأمر هي توفير دالة "تقدير" رخيصة من أي موضع محدد إلى نقطة النهاية.وخير مثال على ذلك هو المسافة التي سيطيرها الطائر للوصول إلى هناك.يضيف A* هذا إلى المسافة الحالية من البداية لكل عقدة ثم يختار العقدة التي تبدو على أقصر مسار.

كلما كان تقديرك أفضل، قل الوقت المستغرق للعثور على مسار جيد.إذا كانت هذه المرة لا تزال طويلة جدًا، فيمكنك البحث عن مسار على خريطة بسيطة ثم البحث عن مسار آخر على خريطة أكثر تعقيدًا للعثور على المسار بين الأماكن التي عثرت عليها على الخريطة البسيطة.

تحديثوبعد الكثير من البحث وجدت مقال عن أ* لتتمكن من القراءة

نصائح أخرى

لا أعتقد أن خوارزمية ديكسترا ستكون مفيدة لرسم خرائط العالم الحقيقي، لأنها، كما قال توم ليز (أود أن أعلق على منشوره، ولكني أفتقر إلى مندوب للقيام بذلك)، تتطلب نقطة بداية واحدة.إذا تغيرت نقطة البداية، فيجب إعادة حساب كل شيء، وأتصور أن هذا سيكون بطيئًا جدًا على جهاز مثل iPhone لمجموعة بيانات كبيرة جدًا.

خوارزمية Dijkstra هي O(m log n) للعقد n والحواف m (لمسار واحد) وهي فعالة بما يكفي لاستخدامها في توجيه الشبكة.وهذا يعني أنها فعالة بما يكفي لاستخدامها في عملية حسابية لمرة واحدة.

باختصار، تعمل خوارزمية Dijkstra على النحو التالي:

Take the start node
Assign it a depth of zero
Insert it into a priority queue at its depth key

Repeat:
    Pop the node with the lowest depth from the priority queue
    Record the node that you came from so you can track the path back
    Mark the node as having been visited
    If this node is the destination:
        Break
    For each neighbour:
        If the node has not previously been visited:
            Calculate depth as depth of current node + distance to neighbour
            Insert neighbour into the priority queue at the calculated depth.

Return the destination node and list of the nodes through which it was reached.

خلافًا للاعتقاد الشائع، فإن خوارزمية ديكسترا ليست بالضرورة آلة حاسبة ذات مسار أقصر لجميع الأزواج، على الرغم من أنه يمكن تكييفها للقيام بذلك.

سيكون عليك الحصول على رسم بياني للشوارع والتقاطعات مع المسافات بين التقاطعات.إذا كانت لديك هذه البيانات، فيمكنك استخدام خوارزمية Dijkstra لحساب أقصر طريق.

إذا نظرت إلى التكنولوجيا التي يطلق عليها الطبل "مسارات الذكاء"، فإنها تقيس السرعة الفعلية ووقت السفر لكل امتداد طريق في وقت من اليوم.وهذا يجعل وقت الوصول أكثر دقة.لذا فإن وقت الوصول المتوقع يعتمد أكثر على الحقائق http://www.tomtom.com/page/iq-routes

يعد حساب المسار باستخدام خوارزمية A* سريعًا بدرجة كافية على جهاز iPhone مزودًا ببيانات الخرائط غير المتصلة بالإنترنت.لدي خبرة في القيام بذلك تجاريا.أستخدم خوارزمية A* كما هو موثق في ويكيبيديا، وأحتفظ بشبكة الطرق في الذاكرة وأعيد استخدامها؛بمجرد تحميله، يصبح التوجيه فوريًا حتى على مساحة كبيرة مثل إسبانيا أو النصف الغربي من كندا.

آخذ البيانات من OpenStreetMap أو من مكان آخر وأحولها إلى رسم بياني موجه، على افتراض (وهي الطريقة الصحيحة للقيام بذلك وفقًا لأولئك الذين يعرفون) أن أي طريقين يشتركان في نقطة بنفس المعرف قد تم ربطهما.أقوم بتعيين أوزان لأنواع مختلفة من الطرق بناءً على السرعات المتوقعة، وإذا كان جزء من الطريق ذو اتجاه واحد، فأنا أقوم بإنشاء قوس واحد فقط؛الطرق ذات الاتجاهين لها قوسين، واحد في كل اتجاه.هذا إلى حد كبير كل شيء بصرف النظر عن بعض التعليمات البرمجية المخصصة لمنع المنعطفات الخطيرة وتنفيذ قيود التوجيه.

وقد تمت مناقشة هذا في وقت سابق هنا: ما الخوارزميات التي تحسب الاتجاهات من النقطة أ إلى النقطة ب على الخريطة؟

القي نظرة على CloudMade.يقدمون خدمة مجانية لأجهزة iPhone وiPad تتيح التنقل بناءً على موقعك الحالي.إنه مبني على خرائط الشوارع المفتوحة ويحتوي على بعض الميزات الرائعة مثل إنشاء نمط الخريطة الخاص بك.إنها بطيئة بعض الشيء من وقت لآخر ولكنها مجانية تمامًا.

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow