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