ترغب بنشر مسار تعليمي؟ اضغط هنا

مسألة المسار الأقصر لجميع العقد في البيان هي , بلا شك , واحدة من أكثر المسائل الأساسية في خوارزميات نظرية البيان . نقدم في هذا البحث خوارزمية بسيطة و فعالة من أجل مسألة المسارات الأقصر في بيان موجه ( أو غير موجه ) . في هذه المسألة نقوم بإيجاد المسار الأقصر من عقدة منبع معطاة إلى جميع العقد الأخرى في هذا البيان و الذي يكون المسار الأقصر فيه هو المسار الذي يملك أقل كلفة ( أي مجموع أوزان الأضلاع ) . أثبتنا بأن تعقيد الخوارزمية المقترحة في هذا البحث يعتمد فقط على أضلاع البيان , و بينا بأن زمن تنفيذها هو زمن خطي قدره (O(m , و هذا يعتبر أفضل أزمنة الخوارزميات على الإطلاق . ثم أجرينا مقارنة بين تعقيد الخوارزمية المقترحة و تعقيد الخوارزمية المقترحة هو الأفضل .
نقدم في هذا البحث خوارزمية فعالة لإيجاد المسار الأقصر في بيان متعدد المنابع, و ذلك باختيار المسار بين المنبع و المسافة التي تعطي طول المسار الأقل وصولا إلى المصب. تعتمد هذه الخوارزمية على مبدأ التكرار للوصول إلى الحل الأمثل لمسألة المسار الأقصر, حيث يتم تكرار خطوات الخوارزمية على جميع الأسهم في البيان. أثبتنا بأن زمن تنفيذ الخوارزمية المقترحة في هذا البحث هو زمن خطي قدره (O(n+L و هو يعتبر أفضل أزمنة الخوارزميات على الإطلاق.
في هذا البحث ندرس إمكانية المساهمة في حل مسألة البائع المتجول Traveling Salesman Problem (TSP , التي هي مسألة من النوع NP-hard و لا توجد حتى الآن خوارزمية تقدم لنا الحل الأمثل لهذه المسألة ، فكل الخوارزميات المستخدمة تعطي حمولاً تقريبية .
كما هو معروف فإن مسألة تلوين بيان باستخدام أقل عدد من الألوان هي مسألة معقدة (NP-Hard) المشكلة تتلخص في كيفية تلوين عقد بيان بأقل عدد ممكن من الألوان . و بحيث لا يكون لأي عقدتين متجاورتين اللون نفسه، أو كيف يمكن تلوين أضلاع هذا البيان بأقل عدد ممك ن من الألون بحيث لا يكون لضلعين يشتركان بعقدة اللون نفسه. نقدم في هذه الورقة البحثية خوارزمية تلوين جديدة لأضلاع بيان. هذه الخوارزمية تُمكننا من الحصول على تلوين ضلعي مستمر لصف من البيانات الشهيرة.
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا