توجيه عقدة العبور

في الرياضيات التطبيقية ، يمكن استخدام توجيه عقد العبور لتسريع توجيه أقصر مسار عن طريق الحساب المسبق للاتصالات بين عقد الوصول المشتركة إلى شبكة فرعية ذات صلة بالسفر لمسافات طويلة. ^{[ 1 ]}

تم وضع إطار عمل لتوجيه عقد النقل في عام 2007 ^{[ 1 ]} ، وظهرت العديد من التطبيقات العملية في السنوات اللاحقة، مثل الأساليب التي تستخدم الشبكات، والتسلسلات الهرمية للطرق السريعة ^{[ 2 ]} ، والتسلسلات الهرمية للانكماش ^{[ 3 ]} . يُعد توجيه عقد النقل أسلوبًا ثابتًا يتطلب معالجة مسبقة للمسافات بين أزواج العقد المهمة في الرسم البياني (انظر أدناه كيفية اختيار هذه العقد). ولم يُنشر أي أسلوب ديناميكي ^{[ 4 ] .}

حدس

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

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

الإطار العام

يبدأ توجيه عقد العبور باختيار عقد العبور $T\subseteq V$ كمجموعة فرعية من جميع العقد $V$ من شبكة الطرق.
لكل عقدة $v\in V$ مجموعات مخصصة من عقد الوصول الأمامي ${\overrightarrow {A}}(v)\subseteq T$ وعقد الوصول العكسي ${\overleftarrow {A}}(v)\subseteq T$ يتم اختيارها من بين جميع عقد العبور.
الآن، المسافات الزوجية بين عقد العبور $D_{T}$ والمسافات بين العقد $v$ وعقد الوصول المقابلة لها $d_{A}$ يتم حسابها وتخزينها.
يمكن الآن حساب المسافة بين عقدتين على النحو التالي: $d(s,t)=\min _{u\in {\overrightarrow {A}}(s),v\in {\overleftarrow {A}}(t)}d_{A}(s,u)+D_{T}(u,v)+d_{A}(v,t)$

مرشح الموقع

قد لا تتطلب المسارات القصيرة بين نقاط البداية والوجهة القريبة أي محطات عبور. في هذه الحالة، يؤدي الإطار المذكور أعلاه إلى مسافات غير صحيحة لأنه يُجبر المسارات على المرور بمحطة عبور واحدة على الأقل.

لتجنب هذا النوع من المشاكل، يمكن استخدام مرشح الموقع . بالنسبة لمواقع البداية والوجهة المحددة، يحدد مرشح الموقع ما إذا كان ينبغي تطبيق توجيه عقدة العبور أو استخدام روتين احتياطي (استعلام محلي).

أمثلة ملموسة

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

كيف يتم اختيار نقاط العبور؟
كيف يتم اختيار نقاط الوصول؟
أي مرشح محلي يجب استخدامه؟
كيف ينبغي التعامل مع الاستعلامات المحلية؟

تجيب الأمثلة التالية لتطبيقات هذا الإطار على هذه الأسئلة باستخدام طرق أساسية مختلفة مثل تجميع العقد في خلايا شبكة متراكبة ^{[ 2 ]} وتطبيق أكثر تطوراً يعتمد على التسلسلات الهرمية للانكماش . ^{[ 3 ]}

النهج الهندسي باستخدام الشبكات

في النهج القائم على الشبكة ، يتم تقسيم المربع المحيط بجميع العقد بالتساوي إلى خلايا مربعة.

كيف يتم اختيار عقد الوصول؟

لكل خلية $C$ يمكن العثور على مجموعة من عقد الوصول من خلال النظر إلى منطقة داخلية $I$ مكونة من 5x5 خلايا ومنطقة خارجية $O$ من 9x9 خلايا حول $C$ التركيز على العقد المتقاطعة (نهايات الحواف التي تعبر حدود $C$ ، $I$ أو $O$ )، عقد الوصول لـ $C$ هل تلك العقد هي $I$ التي تشكل جزءًا من أقصر مسار من عقدة ما في $C$ إلى عقدة في $O$ . كعقد وصول لعقدة عشوائية $v\in C$ جميع نقاط الوصول لـ $C$ يتم اختيارها (النقاط الحمراء في الصورة على اليمين).

كيف يتم اختيار نقاط العبور؟

مجموعة عقد العبور هي بالضبط اتحاد جميع مجموعات عقد الوصول.

أي مرشح محلي يجب استخدامه؟

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

كيف ينبغي التعامل مع الاستعلامات المحلية؟

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

متطلبات المساحة

يجب تخزين المسافات المحسوبة مسبقًا بين كل عقدة وعقدة الوصول المقابلة بالإضافة إلى المسافات الزوجية بين عقد العبور في جداول المسافة.

في تطبيق الشبكة الموضح أعلاه، يتطلب ذلك 16 بايت من مساحة التخزين لكل عقدة في مخطط الطرق. يحتوي مخطط كامل لشبكة الطرق في الولايات المتحدة الأمريكية على 23,947,347 عقدة. ^{[ 5 ]} لذا، يلزم حوالي 383 ميجابايت من مساحة التخزين لحفظ جداول المسافة.

استخدام التسلسلات الهرمية للانكماش

كيف يتم اختيار نقاط العبور؟

بحسب التعريف، ينقل التسلسل الهرمي الانكماشي العقد المهمة (أي العقد التي تشكل جزءًا من العديد من أقصر المسارات) إلى أعلى التسلسل الهرمي. وبالتالي، يمكن اختيار مجموعة من عقد العبور كـ $k$ أعلى مستويات التسلسل الهرمي للانكماش.

كيف يتم اختيار عقد الوصول؟

عقد الوصول الأمامي لعقدة $v$ يمكن العثور عليها من خلال إجراء بحث تصاعدي في التسلسل الهرمي للانكماش بدءًا من $v$ أثناء البحث التصاعدي ، لا يتم تخفيف القيود على الحواف الخارجة من عقد العبور التي تم العثور عليها سابقًا. عندما لا يتبقى في البحث أي عقد تصاعدية أخرى للاستقرار، تصبح عقد العبور التي تم استقرارها هي عقد الوصول إلى $v$ . يمكن إيجاد عقد الوصول العكسي بطريقة مماثلة.

أي مرشح محلي يجب استخدامه؟

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

كيف ينبغي التعامل مع الاستعلامات المحلية؟

تستخدم الاستعلامات المحلية خوارزمية الاستعلام العادية لتسلسل الانكماش.

انظر أيضاً

مراجع

باست ، هـ .؛ فونكه، س.؛ ساندرز، ب.؛ شولتس، د. (27 أبريل 2007). "التوجيه السريع في شبكات الطرق ذات عقد العبور". مجلة ساينس . 316 (5824): 566. رمز Bibcode : 2007Sci...316..566B . doi : 10.1126/science.1137521 . ISSN 0036-8075 . PMID 17463281. S2CID 16559205 .
باست ، هولجر؛ فونكه، ستيفان؛ ماتييفيتش، دوماغوي؛ ساندرز، بيتر؛ شولتس، دومينيك (2007-01-06)، "الانتقال إلى استعلامات أقصر مسار في وقت ثابت في شبكات الطرق"، وقائع ورشة العمل التاسعة لعام 2007 حول هندسة الخوارزميات والتجارب (ALENEX) ، جمعية الرياضيات الصناعية والتطبيقية، ص 46-59 ، doi : 10.1137/1.9781611972870.5 ، ISBN 9781611972870{{citation}}: CS1 maint: work parameter with ISBN ( link )
1 2 أرز، جوليان؛ لوكسن، دينيس؛ ساندرز، بيتر (2013)، "إعادة النظر في توجيه عقدة العبور"، الخوارزميات التجريبية ، سبرينغر برلين هايدلبرغ، ص 55-66 ، arXiv : 1302.5611 ، Bibcode : 2013arXiv1302.5611A ، doi : 10.1007/978-3-642-38527-8_7 ، ISBN 9783642385261، S2CID 14371800 {{citation}}: CS1 maint: work parameter with ISBN ( link )
↑ شولتس، دومينيك؛ ساندرز، بيتر (2007)، "توجيه عقد الطرق السريعة الديناميكي"، الخوارزميات التجريبية ، سلسلة محاضرات في علوم الحاسوب، المجلد 4525، سبرينغر برلين هايدلبرغ، الصفحات 66-79 ، doi : 10.1007/978-3-540-72845-0_6 ، ISBN 9783540728443
↑ "التحدي التاسع لتنفيذ DIMACS: أقصر المسارات" . users.diag.uniroma1.it . تم الاطلاع عليه بتاريخ 15 يوليو 2019 .

[:0-1] باست ، هـ .؛ فونكه، س.؛ ساندرز، ب.؛ شولتس، د. (27 أبريل 2007). "التوجيه السريع في شبكات الطرق ذات عقد العبور". مجلة ساينس . 316 (5824): 566. رمز Bibcode : 2007Sci...316..566B . doi : 10.1126/science.1137521 . ISSN 0036-8075 . PMID 17463281. S2CID 16559205 .

[:1-2] باست ، هولجر؛ فونكه، ستيفان؛ ماتييفيتش، دوماغوي؛ ساندرز، بيتر؛ شولتس، دومينيك (2007-01-06)، "الانتقال إلى استعلامات أقصر مسار في وقت ثابت في شبكات الطرق"، وقائع ورشة العمل التاسعة لعام 2007 حول هندسة الخوارزميات والتجارب (ALENEX) ، جمعية الرياضيات الصناعية والتطبيقية، ص 46-59 ، doi : 10.1137/1.9781611972870.5 ، ISBN 9781611972870{{citation}}: CS1 maint: work parameter with ISBN ( link )

[:2-3] 1 2 أرز، جوليان؛ لوكسن، دينيس؛ ساندرز، بيتر (2013)، "إعادة النظر في توجيه عقدة العبور"، الخوارزميات التجريبية ، سبرينغر برلين هايدلبرغ، ص 55-66 ، arXiv : 1302.5611 ، Bibcode : 2013arXiv1302.5611A ، doi : 10.1007/978-3-642-38527-8_7 ، ISBN 9783642385261، S2CID 14371800 {{citation}}: CS1 maint: work parameter with ISBN ( link )

[4] شولتس، دومينيك؛ ساندرز، بيتر (2007)، "توجيه عقد الطرق السريعة الديناميكي"، الخوارزميات التجريبية ، سلسلة محاضرات في علوم الحاسوب، المجلد 4525، سبرينغر برلين هايدلبرغ، الصفحات 66-79 ، doi : 10.1007/978-3-540-72845-0_6 ، ISBN 9783540728443

[5] "التحدي التاسع لتنفيذ DIMACS: أقصر المسارات" . users.diag.uniroma1.it . تم الاطلاع عليه بتاريخ 15 يوليو 2019 .

[ 4 ] .

[ 5 ]

اللغة	العربية (RTL)
روابط موسوعية	22 رابطاً
المصدر الأصلي	ويكيبيديا ↗