اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدتصميم خوارزمية بزمن خطي لإيجاد المسار الاقصر في البيان
Design a linear time Algorithm for Finding A shortest path in Graph
2667
4 233
0
(
0
)
تأليف
ناصر أبو صالح( باحث )
تمت اﻹضافة من قبل
Shamra Editor
اسأل ChatGPT حول البحث
نقدم في هذا البحث خوارزمية فعالة لإيجاد المسار الأقصر في بيان متعدد المنابع, و ذلك باختيار المسار بين المنبع و المسافة التي تعطي طول المسار الأقل وصولا إلى المصب. تعتمد هذه الخوارزمية على مبدأ التكرار للوصول إلى الحل الأمثل لمسألة المسار الأقصر, حيث يتم تكرار خطوات الخوارزمية على جميع الأسهم في البيان. أثبتنا بأن زمن تنفيذ الخوارزمية المقترحة في هذا البحث هو زمن خطي قدره (O(n+L و هو يعتبر أفضل أزمنة الخوارزميات على الإطلاق.
In this paper, we introduce an Effective algorithm to find the shortest path in Multiple – Source Graph, by choosing the path between the source and the distance that gives at least the length of the path down to the sink. This algorithm is based on the principle of iteration to access the optimal solution of the shortest-path problem, Where the algorithm steps are repeated for all the darts in the Graph. We proved that the time of implementation of the proposed algorithm in this paper is linear time O(n+L) and This is considered the best times of the algorithms at all.
مراجعة الذكاء الصنعي:
ملخص البحث
يقدم هذا البحث خوارزمية فعالة لإيجاد المسار الأقصر في بيان متعدد المنابع، وذلك من خلال اختيار المسار بين المنبع والمسافة التي تعطي طول المسار الأقل وصولاً إلى المصب. تعتمد الخوارزمية على مبدأ التكرار للوصول إلى الحل الأمثل لمسألة المسار الأقصر، حيث يتم تكرار خطوات الخوارزمية على جميع الأسهم في البيان. أثبتت الدراسة أن زمن تنفيذ الخوارزمية هو زمن خطي قدره O(n + L)، مما يجعلها من أفضل الخوارزميات المتاحة. تتضمن الخوارزمية خطوتين أساسيتين: استبدال السهم بالسهم المعاكس له، وزيادة طول السهم المعاكس تدريجياً حتى يصل إلى طوله الأصلي. يتم تكرار هذه الخطوات على جميع الأسهم في البيان. تتميز الخوارزمية بسهولة التنفيذ وقلة عدد الخطوات اللازمة، مما يجعلها مناسبة للتطبيق في شبكات الأعمال المختلفة.
قراءة نقدية
دراسة نقدية: على الرغم من أن الخوارزمية المقترحة تقدم حلاً فعالاً لمسألة المسار الأقصر بزمن خطي، إلا أن هناك بعض النقاط التي يمكن تحسينها. أولاً، لم يتم التطرق بشكل كافٍ إلى كيفية التعامل مع البيانات الكبيرة والمعقدة التي قد تحتوي على عدد كبير من العقد والأقواس. ثانياً، لم يتم تقديم تحليل شامل لكيفية تأثير التغيرات في الأوزان على أداء الخوارزمية. ثالثاً، يمكن تحسين الخوارزمية لتكون أكثر تكيفاً مع الشبكات الديناميكية التي تتغير فيها الأوزان بشكل مستمر. وأخيراً، يمكن تقديم المزيد من الأمثلة العملية والتطبيقات الواقعية لتوضيح فعالية الخوارزمية بشكل أفضل.
أسئلة حول البحث
-
ما هي الخطوتين الأساسيتين في الخوارزمية المقترحة؟
الخطوتين الأساسيتين هما استبدال السهم بالسهم المعاكس له، وزيادة طول السهم المعاكس تدريجياً حتى يصل إلى طوله الأصلي.
-
ما هو زمن تنفيذ الخوارزمية المقترحة؟
زمن تنفيذ الخوارزمية المقترحة هو زمن خطي قدره O(n + L).
-
ما هي التطبيقات العملية لمسألة المسار الأقصر؟
تملك مسألة المسار الأقصر تطبيقات عملية متعددة مثل شبكات النقل، شبكات الطرق، السكك الحديدية، شبكات التدفق (كهرباء، ماء، نفط، معلومات)، وشبكات الاتصالات.
-
ما هي ميزات الخوارزمية المقترحة؟
من أهم ميزات الخوارزمية المقترحة هي بساطة التنفيذ، الزمن الخطي للتنفيذ، قلة عدد الخطوات اللازمة، وصلاحيتها لجميع أنواع الشبكات مهما كان حجمها.
المراجع المستخدمة
A. Kolokolova " Bellman-Ford algorithm" Applied Algorithms February 14, 2012
Chandy. K. M and Misra. J " Distributed Computation on Graphs: Shortest Path Algorithms" Communications of the ACM , Volume 25, Number I 1, November 1982
(Dijkstra. . W, "A note on two problems in connexion with graphs", Numer Math 1, 269–271. (1959
قيم البحث
اقرأ أيضاً
مسألة المسار الأقصر لجميع العقد في البيان هي , بلا شك , واحدة من أكثر المسائل الأساسية في خوارزميات نظرية البيان . نقدم في هذا البحث خوارزمية بسيطة و فعالة من أجل مسألة المسارات الأقصر في بيان موجه ( أو غير موجه ) . في هذه المسألة نقوم بإيجاد المسار
الأقصر من عقدة منبع معطاة إلى جميع العقد الأخرى في هذا البيان و الذي يكون المسار الأقصر فيه هو المسار الذي يملك أقل كلفة ( أي مجموع أوزان الأضلاع ) . أثبتنا بأن تعقيد الخوارزمية المقترحة في هذا البحث يعتمد فقط على أضلاع البيان , و بينا بأن زمن تنفيذها هو زمن خطي قدره (O(m , و هذا يعتبر أفضل أزمنة الخوارزميات على الإطلاق . ثم أجرينا مقارنة بين تعقيد الخوارزمية المقترحة و تعقيد الخوارزمية المقترحة هو الأفضل .
يمكن تصنيف مسألة المسار الأقصر إلى نوعين مختلفين من المسائل : مسألة المسار الأقصر وحيد (SSSP) المنبع و مسألة المسار الأقصر لجميع العقد (APSP). في هذا البحث أجرينا تحليل و مقارنة بين درجة التعقيد لأشهر خوارزميات المسار الأقصر, و تبين من النتائج التي ح
صلنا عليها بأن جميع الأبحاث تحقق نجاحات ملحوظة و استثنائية في تصميم أفضل الخوارزميات من حيث زمن التنفيذ لحل خوارزميات المسار الأقصر.
تم في هذا البحث تصميم مصفوف هوائي خطي منتظم المسافات و غير منتظم التغذية بطريقة " دولف – تشيبيشيف " , حيث ندرس طريقة التصميم باستخدام مصفوفتين هوائيتين إحداهما ذات عدد عناصر فردي و الثانية بعدد زوجي من العناصر و ذلك عند قيمتين مختلفتين لنسبة الوريقة
الإشعاعية الرئيسة إلى الثانوية ، و عند مسافات بينية مختلفة ، تم حساب معاملات التغذية مع رسم المخطط الإشعاعي لكل حالة ، إضافةً إلى حساب زاوية فتحة الإشعاع عند سوية نصف الاستطاعة و الاتجاهية الموافقة، و رسم منحنى توسيع عرض الحزمة بتابعية نسبة الوريقة الإشعاعية الرئيسة إلى الثانوية و منحنى الاتجاهية بتابعية طول المصفوف.
نحدد محلل pregroup الخطي، من خلال تطبيق بعض التعديلات الرئيسية على الحد الأدنى المحيطي المحدد في (PRILLER، 2007).وتشمل هذه التعامل مع الكلمات ككتل منفصلة، وبالتالي احترام دورها النحوي في الجملة.نحن نثبت صحة خوارزميةنا فيما يتعلق بتحليل الجمل في فئة ف
رعية من قواعد النحو Pregroup.تم تصميم الخوارزمية خصيصا لتنفيذ سلس في بيثون.يؤدي هذا إلى تسهيل تكامله ضمن وحدة تخصيص Discopy ل QNLP ويزيد بشكل كبير من إمكانية تطبيق قواعد النحو Pregroup لتحليل بيانات نصية حقيقية.
نرمز نظرياً لثخانة البيان G ب( Φ(G وتعرف ثخانة البيان بأنها العدد الأصغري من البيانات الجزئية المسطحة(المستوية ) والتي نستطيع الحصول عليها من تحميل البيان الأصلي G والبيان المسطح هو كل بيان يمكن إعادة رسمه في المستوي بدون أن تتقاطع أضلاعه (خطوط التو
صيّل بين الر ؤوس)، لذلك عرفت مسألة تحديد ثخانة البيان كمسألة تنتمي إلى صف المسائل
.NP-complete
سنقدم في هذا البحث تطبيقاً لخوارزمية تجريبية Heuristic Algorithm تعتمد على مفهوم محاكاة تلدين الفلزات الأمثلScheme Simulated Annealing Optimization
New- hick الذي يساعد في تحسين نتائج الخوارزمية التجريبية المقترحة
حيث أعطى حلاً فعالاً وسريعاً في إيجاد ثخانة البيانات التامة والثنائية التامة
عندما يكون عدد رؤوس البيان n<=30 وأبطأ عندما يكون أكبر من ذلك.
أخيرا نعرض نتائج تطبيق هذه الخوارزمية على الخوارزمية التجريبية
فنلاحظ بأنها أعطت حلاً أمثلياً لتحديد ثخانة البيانات التامة والثنائية التامة. كما تمّت برمجة هذه الخوارزمية باستخدام لغة عالية المستوى ++C بمفهوم غرضي التوجه وقد حصلنا على النتائج بتنفيذ البرنامج على حاسوب بمواصفات RAM 2GB, CPU, M350 2.27GHZ
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
