الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

أقصر الطرق من النقطة A إلى النقطة B

بدأه bilal2005 في 6 فبراير 2009 · 8 رد · 10,784 مشاهدة · في قسم المواضيع الهامة في قسم السي /سي++
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

في هذا الدرس إن شاء الله سنتناول من أهم المفاهيم المستعملة في علوم البرمجيات وهي خوارزمية أقصر الطرق

فضلت أن أضع الدرس في هذا القسم لأنني أريد أن أكتب الكود بلغة السي بلس بلس وإن شاء الله سأضع الكود بلغة الجافا

سأحاول عن أضع مقدمة نضرية ومن ثم أدعمها بأمثلة ومن ثم أضع الكود

بسم الله نبدأ

نفرض مثلا أنك تريد ان تذهب من مكان إلى مكان آخر و ليس لديك الوقت الكافي فماذا ستفعل ؟؟؟

بالطبع ستسلك أقرب طريق من المكان الذي انت موجود فيه إلى المكان الذي تريد الذهاب إليه فكيف عرفت أن ذلك الطريق هو أقصر طريق ؟؟

قد تبدوا الإجابة سهلة : فالإجابة المنطقية هي أنني أعرف أن المسافة التي سلكتها هي أقصر مسافة عن الطرق الأخرى

هذا من أرض الواقع

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

مثال آخر إفرض أن لديك خارطة وتريد أن تعرف اقرب مسافة بين مدينتين على أن تضع المسافة بين التقاطعات

فكيف ستجد أقصر الطريق

الجواب نجده عند خوارزمية ديجيكسترا

خوارزمية ديجيكسترا هي من أشهر الخوارزميات بالطبع توجد هوارزميات أخرى مثل خوارزمية فورد وبيولمان و...

لكن ديجيكسترا من أشهرهم

أولا تعتمد هذه الخوارزمية ان يكون اولا هناك جراف ( رسم مبياني ) (آسف لا أعرف التسمية العربية الدقيقة ) وهذا الجراف يجب أن يختوى على عقدة و ونقطة الوصول وعلى ان يكون الجراف موجه وان تكون المسافة معروفة بين كل عقدة

مثال post-51778-1233933348_thumb.jpg

في هذا الشكل نرى هناك 5 عقد والدوائر التي وضعتها على رؤوس الأسهم لتبين ان الجراف موجه

إذن كيف سنعرف أقصر مسافة بين العقدة A والعقد D و C

سأشرح الخوارزمية مع المثال

في الشكل أعلاه نريد حساب أقرب مسافة بين A وD و C

سأضع جدول يشرح حالة الجراف في حالته البدئية

post-51778-1233933181_thumb.jpg

في الجدول نرى ان العقدة A فيها 0 لأنها العقدة التي فيها أقصر مسافة وتحت الصفر نلاحظ وجود نقطة سوداء كبيرة للدلالة على ان هذه العقدة هي التي سننطلق منها للعقد لآخرى لأنها تحتوي على أقل رقم .

رمز الانهاية للدلالة على اننا لا نعرف المسافة الفاصلة بين العقدة A والعقد الأخرى

ننطلق من العقدة A

العقدة A إلى أي من العقد تصب إنها تصب في العقدتين B و E

نرى ان المسافة التي بين العقدة A و B هي : 10

والمسافة التي بين العقدة A و E هي : 5

في هذه الصورة وضحت المسارين بلون مختلف

post-51778-1233933701_thumb.jpg

إذن أقصر المسافة بين العقدتين هي : 5

هذا الجدول يبين ذلك

post-51778-1233933786_thumb.jpg

نلاحظ في الجدول أننا وضعنا الرقم 10 تحت العقدة B وبالقرب من 10 وضعنا الحرف A ليدل على أن المسار آت من العقدة A

وتحت العقدة E وضعنا الرقم 5 بإطار لنبين ان الرقم 5 هو المسار الأقصر من العقدة A وبين العقدتين B و E

بما اننا وجدنا ان العق دة E فيها أقل رثم نبدا منها لهذا في الجدول الأخير وتحت الرقم 5 وضعت نقط سوداء للدلالة على اننا سوف نبدأ منها

إذن نذهب إلى العقدة E

نرى ان العقدة E تؤدي إلى كل من العقد B و C و D

لنرى الصورة التبيانية لحالة العقد

post-51778-1233934423_thumb.jpg

نرى ان العقدة B تحتوي على الرقم 8 والعقدة C تحتوي على الرقم 14 والعقدة D تحتوي على الرقم 7

من أين اتت هذه الارقام

لنحلل الشكل

قلنا أن أقل رقم بين العقدة A والعقدتين B و E هو 5

والمسافة التي بين العقدة E والعقدة B هي 3 كما في الشكل إذن وبالتالي تكون المسافة بين العقدة A وB هي 8 إذن أقصر مسار للوصول إلى العقدة B هي بالمرور على العقدة E ثم الوصول إلى العقدة B لأن المسافة بالمرور على العقدة E ومن ثم الوصول للعقدة B هي 8

أما من العقدة A إلى B مباشرة فهي 10

كذلك الأمر بالنسبة للعقدة C أي نضيف 5 على المسافة التي بين العقدة E و العقدة C فتصبح 14

وكذلك بالنسبة للعقدة D فتصبح 7

نضع جدول بين الأمر

post-51778-1233934905_thumb.jpg

من خلال الجدول نرى أن 7 هو أقل رقم الآت من العقدة E

الحين ننطلق من العقدة D

لأنه ومن خلال الجدول نرى ان العقدة D في أقل رقم من العقد الاخرى الذي هو الرقم 7

العقدة D تؤدي فقط إلى العقدة C

إذن تصبح العقدة C تساوي 7+6=13

نلاحظ ان العقدة D لا توصل للعقدة B إذن العقدة B تبقى تساوي 8

نلاحظ الصورة للحالة الجديدة

post-51778-1233935388_thumb.jpg

الجدول لتحليل الصورة

post-51778-1233935472_thumb.jpg

إذن نلاحظ في الجدول ان العقدة B تحتوي على أقل رقم الآت من العقدة E

ونلاجظ ان العقدة B تعطي للعقدة C إذن

نقوم بإظافة 8 على المسافة التي بين العقدة B و C فتصبح العقدة C تساوي 9

إذن خلاصة الامر للوصول إلى العقدة C من أقصر الطرق نسلك العقدة E ومن ثم العقدة B وأخيرا نصل إلى العقدة العقدة الهدف C

وللوصول إلى العقدة D من أقصر الطرق نسلك العقدة E ونصل إلى العقدة D

اترككم مع الصورة النهائية

post-51778-1233935853_thumb.jpg

والجدول التوضيحي

post-51778-1233935872_thumb.jpg

في هذا المال طبقنا خوارزيمة ديجيكسترا للوصول إلى العقدتين D و C من أقرب الطرق

سأكمل لا حقا إن شاء الله بمثال اخر مع تحيل الخوارزمية ووضع الكود لها بالسي بلس بلس لأن اصابعي ألمتني والبرد عندنا قارص

والسلام عليكم ورحمة الله

تم تعديل هذه المشاركة بواسطة bilal2005 في 6 فبراير 2009 في 19:01

1
#2

موضوع مهم في الخوارزميات :)

تابع وفقك الله ربما نصل إلى النقاش في الخوارزميات التي يكون فيها الـ graph غير موجه حينها تدخل مفاهيم أخرى مثل trial و path .. في هذا الأمر ويصبح الموضوع أكثر "متعة" (كما في حل المتاهات للبحث عن الطريق الأقصر) :D

تم تعديل هذه المشاركة بواسطة Xacker في 6 فبراير 2009 في 20:03

Do as I say, not as I do

We are Anonymous. We are Legion. We don't forgive. We don't forget

#3

الله يعطيك العافية

بس ننتظر التطبيق ..:)

#4

هذا كود بسيط بالسي ++ حول خوارزمية ديجيكسترا .

#include<iostream.h>
class dijkstra
{
private:
 int graph[15][15];
 int set[15],predecessor[15],mark[15],pathestimate[15];
 int source;
 int num_of_vertices;
public:
 int minimum();
 void read();
 void initialize();
 void printpath(int);
 void algorithm();
 void output();
};
void dijkstra::read()
{
 cout<<"enter the number of vertices\n";
 cin>>num_of_vertices;
 while(num_of_vertices<=0)

{
  cout<<"\nthis is meaningless,enter the number carefully\n";

cin>>num_of_vertices;

}
 cout<<"enter the adjacent matrix:\n";
 for(int i=1;i<=num_of_vertices;i++)
 {
  cout<<"\nenter the weights for the row\n"<<i;
  for(int j=1;j<=num_of_vertices;j++)
  {
   cin>>graph[j];
   while(graph[j]<0)
   {
	cout<<"\nu should enter the positive valued weights only\nenter the value again\n";
	cin>>graph[j];
   }
  }
 }
cout<<"\nenter the source vertex\n";
cin>>source;
}

void dijkstra::initialize()
{
 for(int i=1;i<=num_of_vertices;i++)
 {
  mark=0;
  pathestimate=999;
  predecessor=0;
 }
 pathestimate[source]=0;
}
void dijkstra::algorithm()
{
 initialize();
 int count=0;
 int i;
 int u;
while(count<num_of_vertices)
 {
  u=minimum();
  set[++count]=u;
  mark=1;
  for(i=1;i<=num_of_vertices;i++)
  {
   if(graph>0)
   {
	if(mark!=1)
	{
	if(pathestimate>pathestimate+graph)
	{
	 pathestimate=pathestimate+graph;
	 predecessor=u;
	}
	}
   }
  }
 }

}

void dijkstra::printpath(int i)
{
cout<<endl;
if(i==source)
{
cout<<source;
}
else if(predecessor==0)
cout<<"no path from "<<source<<" to "<<i;
else
{
printpath(predecessor);
cout<<".."<<i;
}
}
void dijkstra::output()
{
 for(int i=1;i<=num_of_vertices;i++)
 {
 printpath(i);
 if(pathestimate!=999)
  cout<<"->("<<pathestimate<<")\n";
 }
 cout<<endl;
}
int dijkstra::minimum()
{
int min=999;
 int i,t;
 for(i=1;i<=num_of_vertices;i++)
 {
  if(mark!=1)
  {
   if(min>=pathestimate)
   {
   min=pathestimate;
   t=i;
   }
  }
 }
 return t;
}
void main()
{
 dijkstra s;
 s.read();
 s.algorithm();
 s.output();
}
llback.jpg

اشهد ان لا إله إلا الله وان محمدا ً رسول الله

#5
اقتباس
ربما نصل إلى النقاش في الخوارزميات التي يكون فيها الـ graph غير موجه حينها تدخل مفاهيم أخرى مثل trial و path .. في هذا الأمر ويصبح الموضوع أكثر "متعة"

بإذن الله

سأحاول ان أرفع المستوى لكن بعد ان ناخذ المفاهيم في الخوارزمية وذلك حسب التفاعل من الإخوة

اقتباس
بس ننتظر التطبيق ..

مممممم باين عليك أنك في عجلة من أمرك :lol:

شكرا أخ تايم على الكود

ساحاول رفع درس ثاني في الأيام القليلة القادمة بإذن الله

#6

bilal2005 الموضوع مفيد في انتظار التكملة بارك الله فيك.

tvquran_6.gif

#7
اقتباس
سأكمل لا حقا إن شاء الله بمثال اخر مع تحيل الخوارزمية ووضع الكود لها بالسي بلس بلس لأن اصابعي ألمتني والبرد عندنا قارص

والسلام عليكم ورحمة الله

ننتظر اكماله ,

الموضوع مهم ورائع بنفس الوقت , ( وخصوصا لمطوري الألعاب ) .

ولكن هناك حلقة مفقودة وهي عدم وجود دروس عن ال Graphs .. في المنتدى .. من يتبرّع ويضعها :) .

( بعد اذن مشرفي القسم - أضفت الموضوع لكتاب المنتدى ( نعاونكم شوي :-) )

تم تعديل هذه المشاركة بواسطة الشمري في 9 فبراير 2009 في 02:24

logo1.png تطبيق طمأنينة ، نسخة بيتا على أندرويد

عبدالله الشمّري - Al-Shammari

CodingAlone.com

twitter @abshammeri

abshammeri AT gmail.com

github : abshammeri

#8

تأخرت قليلا عن وضع الدروس لكن إعذروني قليلا بعض مشاغل الحياة

سأضع الدروس في أقرب فرصة وسأحاول خلطها مع دروس الجراف

#9

موضوع حقا رائع

اشكرك اخي

وبارك الله فيك

بانتظار بقية الدروس

مواضيع مشابهة