في مقال سابق ، وصفت خوارزمية تسمح لك ببناء طرق أكثر إثارة للاهتمام (على عكس الطرق الأقصر ، مثل جميع طرق Yandex-Google) بين نقطتين. خوارزمية تحميل مشاهد ، والحدائق ، وغيرها من الأشياء ممتعة ومثيرة للاهتمام للمشاة من خريطة الشارع المفتوحة ووضع طريق من خلالها. نتيجة لذلك ، يمكن أن يكون المسار أطول بـ 10-20٪ ، ولكنه أكثر إمتاعًا وإثارة.
صور المدينة - Alex 'Florstein' Fedorov
في التعليقات ، كتب الكثيرون أنه بالإضافة إلى الطرق بين نقطتين ، سيكونون مهتمين ببناء طرق دائرية من شأنها أن تبدأ وتنتهي في نفس النقطة وتتناسب مع حد زمني معين. على سبيل المثال ، إذا كان لديك ساعتان للقطار أو لمقابلة الأصدقاء ، فلن يكون لديك وقت للذهاب إلى مكان بعيد خلال هذا الوقت ، لكن من الممكن أن تمشي ومشاهدة الجمال في مكان قريب.
بعد عدد من التجارب ، قمت بتكوين خوارزمية جينية تبني طرقًا جيدة جدًا (بالنسبة لي) في هذا الموقف. تحت وصف القط لمبدأ العملية وبعض الأمثلة.
لذلك ، يريد المستخدمون أن يكونوا قادرين على القيام بجولة قصيرة في المنطقة المحيطة والعودة إلى نقطة البداية في الوقت المحدد (عادة 1-2 ساعات). كما اتضح فيما بعد ، فإن هذا النوع من المشي في الطلب. على سبيل المثال ، تصف المقالة "أنماط حركة السياح داخل الوجهة" دراسة مسارات 250 سائحًا في هونغ كونغ ، في حين بدأ 40٪ من السياح استكشاف المدينة من طريق دائري داخل دائرة نصف قطرها 500 متر من الفندق. ومع ذلك ، غالبًا ما يتجول الناس ، ولا يمكن رؤية ما هو مثير للاهتمام في الجوار.
تكون المهمة معقدة إذا لم تكن في المركز السياحي (أينما ذهبت - ستجد شيئًا مثيرًا للاهتمام في كل مكان) ، ولكن في مكان ما في الضواحي حيث تحتاج إلى البحث عن المعالم السياحية.
نصف القطر واختيار المعالم السياحية
لبناء طريق ، نحتاج أولاً إلى تحديد مناطق الجذب التي نريد زيارتها. ولهذا تحتاج إلى تحديد منطقة بحثهم حول نقطة البداية. إذا حدد المستخدم الحد الأقصى لوقت المشي في دقائق M ، فستكون النقطة الأكثر بعدًا التي يمكنك الوصول إليها والقبض عليها في الوقت المناسب هي نقطة على مسافة (V * M / 2) ، حيث V هي سرعة المشاة.
يمكن اعتبار متوسط السرعة المفضلة للمشاة 1.4 متر في الثانية. ومع ذلك ، عندما يزور شخص ما أبطأ قليلاً ، حيث يقضي وقتًا إضافيًا في جولة. لقد بنيت بعض الطرق في جميع أنحاء المدينة وسرت على طولها ، قارنت توقيت المشي مع ما تنبأ به التطبيق. ونتيجة لذلك ، اتضح أن متوسط سرعة المشي أقل بنسبة 20٪ تقريبًا ، أي حوالي 1.1 م / ث. نظرًا لأنني توقفت بشكل دوري لالتقاط الصور ، والتحقق من الخريطة ، وأحيانًا عبرت الطريق مرة أخرى لاختيار أفضل زاوية أو شراء الآيس كريم.
لقد أجريت تجارب في مناطق غير مألوفة في المدينة ، باستخدام خوارزمي هناك يمكنك أن تجد كل أنواع الأشياء المثيرة للاهتمام التي لم أسمع عنها من قبل. على سبيل المثال ، نصب تذكاري للنشرة الأولى.
سيؤدي اختيار نقطة اهتمام على مسافة قصوى إلى إنشاء مسار دائري منحل. نظرًا لأن المشاة لم يعد لديه وقت للذهاب في أقصر طريق في خط مستقيم ، فسيكون قادرًا على زيارة هذا الجذب فقط ، والذهاب إليه والعودة على طول الشارع نفسه ، كما هو موضح بالسهم الأحمر.
هنا يمكننا إما الذهاب إلى الحديقة بعيدًا ، أو زيارة عدة نقاط في وقت أقرب
لكن هذا الموقف يتناقض مع فكرة الطرق الدائرية المثيرة للاهتمام ، لأنه في الواقع لم نر سوى شارعًا واحدًا وكائنًا واحدًا ، لكنني أريد أن أرى أكثر من ذلك. لذلك ، ووفقًا لنتائج التجارب ، تم اختيار نصف قطر يساوي ثلث المسافة القصوى. باستخدام نصف قطر البحث هذا ، سيكون لدى المشاة ما يكفي من الوقت للوصول إلى أبعد نقطة مهمة على طول نصف القطر ، ثم ، إذا لزم الأمر ، السير بنفس المسافة على طول الوتر بحثًا عن أشياء أخرى مثيرة للاهتمام ، ثم العودة في الوقت المناسب.
قضايا النهج الأمامي
حسنًا ، لقد وضعنا قائمة عوامل الجذب المرشحة. يبقى الآن اختيار أي منهم وبالترتيب الذي نريد تفتيشه. على الأرجح ، لن يكون لدينا وقت لزيارتهم ، لذلك نحن بحاجة إلى اختيار المجموعة الفرعية الأكثر إثارة للاهتمام منهم.
أولاً ، حاولت صياغة وبناء خوارزمية تسلسلية بسيطة. ومع ذلك ، سرعان ما واجهت عددا من المشاكل.
إذا نظرنا في الموقف من الشكل أعلاه ، فليس من الواضح من أين نبدأ بناء المسار. إذا كانت الحديقة هي الأهم ، ولكن جاذبيتها البعيدة ، فبداية من ذلك ، سنحصل على نسخة منقوصة ، كتبنا عنها سابقًا.
الحل الواضح التالي هو تجميع المعالم بطريقة أو بأخرى ومحاولة البحث عن المسار إلى المجموعة الأكثر ربحية ، ثم المشي داخلها. لكن هنا مرة أخرى ، كل شيء غير واضح: من أي مجموعة تبدأ ، أي طريق يجب أن تذهب. يمكنك دائمًا الوقوع في فخ النوع الذي سلكناه بطريقة خاطئة واندفعنا إلى "الصحراء" - وهي منطقة خالية من المعالم السياحية وليس لدينا ما يكفي من الوقت للمضي فيها والعودة إلى نقطة البداية.
في مرحلة ما ، أصبح من الواضح لي أنني كنت أمارس عمل الخوارزمية الجينية عمليًا: أرسم طرقًا مختلفة على الخريطة وأحاول تحديد مقدار ما أرغب شخصيًا في ذلك.
الخوارزمية الجينية
بعد تلقي قائمة مرقمة من عوامل الجذب ، يجب أن تختار الخوارزمية مجموعة فرعية مرتبة ، والتي ستشكل أساس المسار الدائري. المسار النهائي في هذه الحالة هو أحد مواقع العديد من عوامل الجذب الرئيسية (لا نريد التكرار وليس مطلوبًا استخدام جميع الكائنات الممكنة).
بمعرفة صيغة عدد المواضع من n إلى k ، يمكننا تقدير عدد الخيارات الممكنة. إذا أخذنا في الاعتبار الطريق الذي يستغرق ساعة حول ساحة القصر في سانت بطرسبرغ ، فسيكون هناك 54 مرشحًا لعوامل الجذب الرئيسية بعد التصفية والتجميع في دائرة نصف قطرها 1320 مترًا (كما هو موضح أعلاه).
العصيدة الجهنمية من كومة من المعالم السياحية في الوسط ، خرج تصحيح مناطق الرؤية المحسوبة وفقًا لخوارزمية المادة السابقة
تم توضيح مبدأ الاختيار والفرز في مقال سابق ، بالإضافة إلى أننا نحذف بالإضافة إلى ذلك الكائنات التي يقل اهتمامها عن 3 (من أجل هذه الأشياء الثانوية ، من غير المحتمل أن يكون الشخص مستعدًا للذهاب بعيدًا ، ما لم يكن هناك شيء آخر قريب). وبالتالي ، يمكن حساب العدد المحتمل من المسارات من خلال صيغة عدد المواضع من 54 إلى 5 ، وهي 379501200. بالنسبة إلى طريق مدته ساعتان ، داخل نصف قطره منها 151 نقطة مهمة بالفعل ، سيكون هذا الرقم مساوياً لـ 73423236600. حسنًا ، هذا كثير جدًا للبحث البسيط.
الكروموسومات والعوامل الوراثية
الكروموسومات في هذه الحالة هي خط يكون فيه كل عنصر هو رقم عنصر الجذب الرئيسي المقابل. لمثل هذه المهام التي تكون فيها الكروموسومات عبارة عن تباديل أو ترتيبات ، هناك متغيرات محسنة خاصة من العوامل الوراثية. يحتفظ هؤلاء المشغلون بخاصية الكروموسوم ليظلوا التقليب أو وضع مجموعة العناصر الأولية.
- يستخدم كروس المعين جزئيا (PMX) لعبور.
- بالنسبة للطفرة ، يستخدم تبادل أماكن جينات عشوائية (Swap Mutator).
يمكن العثور على وصف لعمل هؤلاء المشغلين بأمثلة ، على سبيل المثال ، في العمل "الخوارزميات الجينية لمشكلة البائع المتجول: مراجعة للتمثيلات والمشغلين".
وظيفة اللياقة البدنية
يجب أن تأخذ وظيفة اللياقة البدنية في الاعتبار العوامل التالية لبناء مسار دائري مثير للاهتمام:
- يجب أن يكون الاهتمام الكلي لجميع مناطق الجذب الرئيسية التي تمت زيارتها أكبر حجم ممكن.
- يجب أن يكون إجمالي وقت السفر أقرب ما يمكن إلى المستخدم المحدد ، ويجب ألا يكون المسار أطول أو أقصر بكثير. الطرق القصيرة مسموح بها فقط عندما لا يوجد ما يكفي من مناطق الجذب القريبة.
- الطريق لا ينبغي أن يعبر نفسه. لكل تقاطع ذاتي ، نضيف نسب جزاء إلى القيمة الإجمالية للدالة.
- يجب أن يكون شكل الطريق بالقرب من الدائرة ، ويجب أن يستحوذ على أكبر منطقة ممكنة في المدينة وتجنب الحالات المتدهورة. للقيام بذلك ، وضعنا في وظيفة نسبة مساحة الشكل الموصوفة من قبل الطريق إلى منطقة الدائرة التي تم البحث فيها المعالم السياحية.
هنا مثال على رحلة ذهابا وإيابا جيدة. يمر عبر متنزهين ولا يزور المكان نفسه مرتين
فيما يلي مثال لطريق غير ناجح بشكل واضح. يحتوي على فروع مسدود ، حيث سيتعين على المشاة العودة مرة أخرى على طول المسار الذي تم فحصه ، والتقاطعات الذاتية. عند التقاطعات ، عادةً ما يضيع الوقت دون جدوى لإعادة فحص الأجزاء التي تم مشاهدتها بالفعل في المدينة.
تم الحصول على المسار السيئ بالفعل من خلال علم الوراثة ، حيث تم تعطيل النقطتين 3 و 4 لوظيفة اللياقة البدنية (غرامات لعبور النفس ومساحة صغيرة)
الفروق الدقيقة
أثناء الاختبار ، ظهرت بعض الفروق الدقيقة.
تم تجاوز الحد الزمني
أثناء عمل علم الوراثة ، نحسب طول المسار على طول الخطوط المستقيمة بين النقاط. وبعد تحديد كائنات للاتصال باستخدام الخوارزمية الجينية ، نحن نبحث عن المسار بينهما باستخدام الخوارزمية من المقالة السابقة. في هذه الحالة ، قد يصبح المسار أطول ويزحف مع مرور الوقت. بعد كل شيء ، في المدينة في كثير من الأحيان أقصر طريق على طول الشارع يمكن أن يكون عدة مرات أطول من خط مستقيم.
في المتوسط ، يكون الفرق في العادة حوالي 10-20 ٪ ، ونحن نضعه في وظيفة اللياقة البدنية (أي أن علم الوراثة يبحث عن طريق بهامش زمني ، ثم يتم تناوله عند وضع طريق مفصل). في بعض الأحيان لا يكفي ذلك - يجب عليك إعادة حساب المسار مرة أخرى. لدينا مثل هذه الأماكن في المدن حيث الفرق بين الطرق "مثل الطيور" و "مثل المشاة" كيلومترات.
بين نقاط من 50 مترا في خط مستقيم ، ولكن كيلومتر ونصف على طول الأرصفة والممرات الالتفافية.
ومع ذلك ، على الرغم من ذلك ، تتجاوز الخوارزمية أحيانًا الوقت الذي يحدده المستخدم ، ولكن بعد ذلك يمكن لأي شخص أن يقرر لنفسه ما إذا كان لديه ما بين 10 إلى 15 دقيقة إضافية أو ما إذا كان عليه إكمال السير مبكرًا.
البندقية
عندما كانت الخوارزمية جاهزة ، قررت إضافة أفضل المدن السياحية في أوروبا للمتعة. اتضح أنها مثيرة للاهتمام: المدن مختلفة في كل مكان ، وميزات التعيين في OSM ، أيضًا ، كنتيجة لذلك ، كان علي دائمًا إنهاء شيء ما.
على وجه التحديد ، تعطل البحث عن طرق دائرية في البندقية. نظرًا لأن هذا مثال فريد لمدينة ذات مناطق غير ذات صلة - يتم فصل الجزر عن طريق القناة الكبرى ، والتي لا توجد جسور فيها ، لا يمكن العبور إلا بالعبّارة.
ونتيجة لذلك ، حددت الخوارزمية جزءًا من الكائنات الموجودة على أحد جانبي المضيق ، جزءًا من الجانب الآخر ، ثم لم تتمكن من العثور على مسار أرض بينها وسقوطه. اضطررت لإضافة التحقق من قابلية الوصول إلى جميع مناطق الجذب من نقطة البداية.
في بعض الأحيان لا يزال يتعين عليك العودة بنفس الطريقة
في المثال الموجود في الحديقة أعلاه ، هناك جزء من الطريق يجب أن تعود فيه بنفس الطريقة - هذه شبه جزيرة صغيرة تقف عليها نصب تذكاري مع طائرة. الطريق الوحيد يؤدي إلى هذه الجزيرة ، وسيكون من الضروري العودة على طولها. لذلك ، لا يمكن حظر هذه المبالغ المستردة بالكامل. تزيد الخوارزمية الخاصة بهذا من وزن جميع الحواف التي تم نقلها بالفعل ، مما يقلل من احتمال العودة على طولها ، لكن لا يزال يجعل ذلك ممكنًا.
رغم أنه في بعض الأحيان لا يزال يعمل بشكل سيء. على سبيل المثال ، يشكون من الكاتدرائية الرئيسية في كالينينغراد. تقع على جزيرة في منتصف النهر يمر عبره الجسر. من هذا الجسر هناك نزول واحد وطريق واحد إلى الكاتدرائية ، ويبدو أن الخوارزمية تزيد من ثقل هذا المسار فقط ، مما يجعل العودة إليه غير مربحة. نتيجة لذلك ، لم يسبق له أن وصل إلى الكاتدرائية ، على الرغم من أنها واحدة من مناطق الجذب الرئيسية في المدينة. لا يزال يتطلب نوعا من الصقل.
النتائج
الخوارزمية الجينية شيء لا يمكن التنبؤ به ، لذلك في بعض الأحيان تكون عربات التي تجرها الدواب وعرة متعرجة غريبة. ولكن بشكل عام ، أنا راض عن النتيجة. ما هو لطيف بشكل خاص ، الخوارزمية لا تعمل فقط في المركز السياحي (حيث لا تشكل مشكلة في الاستمتاع) ، ولكن أيضًا في ضواحي المدينة. حيث ، في كثير من الأحيان ، دون تلميحات ، من الصعب العثور على شيء مثير للاهتمام.
حتى في أكياس النوم في الجنوب الغربي من سان بطرسبرغ ، يمكنك العثور على ما يكفي من الآثار لممارسة المشي لمدة ساعتين
يمكنك تجربة الخوارزمية بنفسك في واحدة من 77 مدينة معتمدة على موقعنا Sight Safari أو في تطبيق Android الخاص بنا (نعم ، لقد انتهينا من ذلك في النهاية).
من المثير للاهتمام بشكل خاص كيف ستعمل الخوارزمية في المدن ذات التضاريس والارتفاعات المعقدة. أضفنا دعمًا لتحليل الارتفاع إلى مكتبة باثفايندر Graphopper ، لكن لا يمكننا التحقق من كونه - بيتر بطيء جدًا في المدينة.
بشكل عام ، حاول كتابة المراجعات ، هي الطرق التي يتم بناؤها بشكل صحيح. يمكنك تقديم طلب على الفور لإضافة مدن جديدة.