ارسل ملاحظاتك

ارسل ملاحظاتك لنا







خوارزمية حاسوبية لحل مسألة أقصر طريق

المصدر: المجلة العراقية للعلوم الإحصائية
الناشر: جامعة الموصل - كلية علوم الحاسوب والرياضيات
المؤلف الرئيسي: نائب، إبراهيم (مؤلف)
المؤلف الرئيسي (الإنجليزية): Nayeb, Ibrahim
المجلد/العدد: ع 18
محكمة: نعم
الدولة: العراق
التاريخ الميلادي: 2010
الصفحات: 51 - 69
ISSN: 1680-855X
رقم MD: 421194
نوع المحتوى: بحوث ومقالات
قواعد المعلومات: EcoLink
مواضيع:
رابط المحتوى:
صورة الغلاف QR قانون

عدد مرات التحميل

13

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

This research aims to finding the shortest path between two Centers S and T which are connected by a network of roads of certain length and certain material or time costs, (as the word Centre could be cities or storage depots or production centers or centers of import and export) by using the new proposed programmable algorithm which depends on converting the road network, to the matrix in which number of columns and rows is equal to the number of the arcs of the under-study network (What ever the size of the road network of the studied problem is), and its elements are: either (1). which means that there is an arc connecting the two centers, or (0) which means that there is no arc connecting the two centers, and then processing this matrix in three basic stages: First: the stage of identifying the number of paths in the network: by counting the number of elements that are equal to (1) in the first row of the matrix, which represents the initial number of tracks, then moving to the following lines and counting the number of elements that is equal to (1) if they are more than one we will have other paths their number is equal to the initial number of elements that is equal to (1) minus one, and add this number to the number of tracks, and so on. Second: the stage of limiting the number of arcs, which is embedded in each path by identifying the number of the line and column of the elements that are equal to (1). Third: The stage of counting the lengths of the paths according to the arcs embedded in each path and comparing them to determine the shortest one.

ISSN: 1680-855X