الرئيسية / الاخبار / تطبيق Google Trips يحدد مسارات الرحلات باستخدام خوارزمية من 1736

تطبيق Google Trips يحدد مسارات الرحلات باستخدام خوارزمية من 1736

تخيل بائع متجول مع قائمة المدن يريد السفر اليها لمرة واحدة فقط أثناء عبور أقصر مسافة ممكنة، قبل أن يعود إلى موقع البداية. وقد تمت دراسة “مسألة البائع المتجول” هذة على مدى عقود، وأصولها يمكن ارجاعه الى ورقة بحثية مكتوبة في 1736. الخوارزميات المستخدمة في حل هذه المشكلة تساعد الآن في تخطيط مسارات السفر من خلال تطبيق السفر الجديد جوجل، Google Trips.

google-trips-algorithm-2

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

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

بالعودة إلى 1736، تفكر عالم الرياضيات السويسري ليونارد يولر بسؤال ممل: هل يمكن لشخص يتجول في مدينة كنيغسبرغ عبور كل جسور المدينة السبعة مرة واحدة فقط؟ في ورقته حول هذا الموضوع، وضعت يولر نظام عام لتخطيط هذه المشكلة بصريا، والتي يمكن تطبيقها على أي تصميم وكمية من النقاط والمسارات بينهما. وقد سماها هندسة المكان (Geometry of Place)، ولكن العلماء يعرفونها الآن باسم نظرية الرسم البياني (Graph Theory).

konigsberg

في حالة كنيغسبرغ، كان من المستحيل عبور كل جسر مرة واحدة فقط، وأساس المشكلة هو في حقيقة أن هناك سبعة منها. عندما عرضت في رسم بياني مجرد، مع الإشارة إلى اليابسة ك “نقطة لقاء” والجسور ك “حواف” التي تربط بينها، لاحظ يولر أن انجاز دورة كاملة وزيارة كل حافة مرة واحدة فقط ليست ممكنة إلا مع عدد زوجي من الحواف.

إذا كيف يرتبط هذا مع اتخاذ قرار بشأن المعالم التي تريد زيارتها في باريس؟ حسنا، لقد ألهم فريق البحث جوجل من هذه الفكرة، وبدأ في دراسة الكيفية التي يمكن أن تستخدم كأساس لخوارزمية مسار سفر الذي يضم أكبر عدد ممكن من “الحواف” المثيرة للاهتمام، وتقرر أي منها تقترح عليك ومساعدة المسافرين على التنقل بينها بكفاءة . هذه الدوائر تعود مرة أخرى إلى مشكلة البائع المتجول التي ذكرناها في وقت سابق، والتي يحلها فريق جوجل (على وجه التقريب) مع خوارزمية Christofides.

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

google-trips-algorithm-1

ولكن مسافر قد لا يرغب في زيارة كل مكان تقترحة جوجل تلقائيا. لإنشاء خوارزمية أكثر ديناميكية لتخطيط المسارات يوميا، Google Trips يأخذ في الاعتبار أيضا “قيم” من نسبة الشعبية إلى تكلفة الزيارة. أشياء مثل الشعبية، الموقع، التميز، واهتمامات المستخدم تؤخذ في الحسبان، لذلك إذا كان مكان خارج المسار العام ومشابه جدا لشيء آخر على الطريق، فإن Google Trips قد لا يشملة في المسار. إذا كان الزائر يريد على وجه التحديد رؤية المكان الذي تتجاهله الخوارزمية (أو العكس بالعكس)، فانها مرنة بما فيه الكفاية لبناء مسار جديد حول تلك التفضيلات.

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

Google Trips متوفر الآن على أجهزة اندرويد و iOS.