المشاركات الشعبية

اختيار المحرر - 2020

انهم تصميم خريطة الطريق الأكثر كفاءة في الولايات المتحدة

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

48 عاصمة ولاية في 8 أيام ونصف © © Randal S. Olson

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

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

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

فيديو: 1. Algorithmic Thinking, Peak Finding (كانون الثاني 2020).

ترك تعليقك