تماس با ما

هرگونه پیشنهاد و انتقاد خود را با ما در میان بگذارید

فرض کنید یه گرف جهت دار موزون (که وزن ها مثبت اند) داریم و میخاهیم از هر راس به رئوس دیگه کوتاه ترین مسیر رو پیدا کنیم (این مساله مثل اینه که شما در یک شهر هستید و میخواهید با هواپیما به یک شهر دیگه برید و چند تا مسیر وجود داره و شما از خودتون می پرسید که کدوم مسیر سریع تره یا کدوم مسیر ارزون تره).

یه راه حل برای حل این مساله اینه که همه مسیر هایی که وجود داره رو بدست بیاریم و کوتاه ترین مسیر رو پیدا کنیم، مثلا برای گراف زیر مسیرها از راس p به راس s عبارتند از:

مجموع وزن مسیر نام مسیر
3+6+2=11 p-->t-->r-->s A
7+8+10=25 p-->u-->q-->s B
3+9+8+10=30 p-->t-->u-->q-->s C
7+8+3+6+2=26 p-->u-->q-->t-->r-->s D
3+8+11+10=32 p-->t-->r-->q-->s E
3+8+10=21 p-->t-->q-->s F

 

مشخص میشه که مسیر A از همه مسیر ها کوتاه تره اما این روش یه مشکل بزرگ داره، اگر گراف ما به جای 6 تا گره 20 تا گره داشته باشه و هر راسی هم به بقیه رئوس یه مسیر مستقیم داشته باشه اون وقت 20! مسیر وجود داره یعنی اگه هر ثانیه یک میلیارد مسیر رو چک کنیم 77 سال طور میکشه تا همه مسیر ها رو چک کنیم پس این روش اگرچه روش درستیه اما عملی نیست.
نگران نشید این مساله  راه حل های دیگه ای هم داره که اینقدر پیچیده و طولانی نیست.
برای اینکه متوجه بشید این الگوریتم رو چطور میشه ساخت، یه کم مساله رو موشکافی میکنم:
به نظر شما حالا که کوتاه ترین مسیر از گره p به گره s مسیر p-->t-->r-->s هست آیا میشه ادعا کرد که  کوتاه ترین مسیر از گره t به گره s از گره r میگذره؟

جواب بله است چون اگه مسیر کوتاه تری از t به s وجود داشته باشه میشه از اون در مسیر p به s  هم استفاده کرد و یک مسیر کوتاه تر بدست آورد در اما ما همه مسیر ها رو از p به s بدست اوردیم و دیدیم که کوتاه تر از این مسیر وجود نداره و این تناقض نشون میده که کوتاه ترین مسیر از t به s حتما به صورت t-->r-->s باید باشه یعنی زیر مسیر از t به s هم باید شامل کوتاه ترین مسیرها باشه.
این مطلب  رو در مورد همه گرافها میشه گفت، و در این مساله اصل بهینگی برقراره ( اگر یادتون رفته اصل بهینگی چیه اینجا کلیک کنید)، حالا که متوجه شدیم اصل بهینگی برقراره میتونیم با خیال راحت بگیم که چون گره p فقط به گره t و گره u ارتباط داره پس اگه کوتاه ترین مسیر از گره های  t و u به گره s رو پیدا کنیم یکی از این دو تا مسیر در زیر مسیری از کوتاه ترین مسیر از p به s هستن.

 

پس بر طبق شکل داریم:
کوتاه ترین مسیر از p به s = حدافل ( کوتاه ترین مسیر از u به s به علاوه 7 یا کوتاه ترین مسیر از t به s به علاوه 3)
از شکل پیداست که میشه الگوریتم رو به صورت بازگشتی نوشت اما این کار رو نمیکنیم چون پیچیدگی مساله به صورت نمایی رشد میکنه، در عوض از روش پویا به صورت زیر استفاده میکنیم:

  • گراف رو به صورت یک ماتریس مینویسیم ( یادتون نره که در کامپیوتر چیزی به اسم گراف نداریم اما آرایه دو بعدی داریم که میشه به عنوان ماتریس ازش استفاده کرد).

      p q r s t u
    p 0 9999 9999 9999 3 7
    q 4 0 9999 10 3 9999
    r 9999 11 0 2 9999 9999
    s 9999 9999 6 0 11 9999
    t 9999 8 6 9999 0 9
    u 9 8 9999 9999 9999 0

    چون در کامپیوتر چیزی به اسم بی نهایت وجود نداره به جای عضو بی نهایت در ماتریس من عدد 9999 گذاشتم که وقتی الگوریتم رو توضیح دادم متوجه میشید که تاثیری نداره و مثل همون بی نهایت عمل میکنه، چیزی که از این ماتریس اولیه میشه متوجه شد اینه که کوتاه ترین مسیر از هر راس به رئوس دیگه به نحوی که از هیچ راس دیگری غیر از مبدا و مقصد عبور نکنه رو نشون میده.

  • حالا راس p رو به محاسبات وارد میکنیم، میخواهیم ببینیم که کوچکترین مسیر از هر راس به رئوس دیگه به شرطی که عبور از راس p هم مجاز باشه چقدره؟ جواب ساده اس چون کوچکترین مسیر، یا مسیر مستقیمه یا مسیریه که از راس p میگذره به عبارت دیگه در اولین مرحله داریم
    minlen(a to b)=minimum(len (a to b) , len(a to p)+len(p to b))
    به کمک این قاعده از ماتریس بالا یک ماتریس جدید میسازیم:

       p q r s t u
    p 0 9999 9999 9999 3 7
    q 4 0 9999 10 3 11
    r 9999 11 0 2 9999 9999
    s 9999 9999 6 0 11 9999
    t 9999 8 6 9999 0 9
    u 9 8 9999 9999 12 0

    همینطور که میبینید کوچکترین مسیر از راس q به راس u از بی نهایت به 11 تغییرکرده چونکه از راس q به راس p یک یال به طول 4 هست و از راس p به راس u هم یک یال به طول 7 هست و مجموع این دو میشه 11 که از مسیر مستقیم که بینهایته کمتره.
  • حالا در ادامه راس q رو وارد محاسبات میکنیم، یادتون نره که ماتریس دومی که به دست اوردیم ماتریس کوچکترین مسیرهاست که استفاده از راس p هم مجازه بنابراین کافیه مجموع کوچکترین مسیر از هر راس به راس q و سپس کوچکترین مسیر از راس q به راس مقصد رو حساب کنیم و با عدد قبلی که در اون راس q دخالت نداشت مقایسه کنیم:
    minlen(a to b) = minimum ( minlen(a to b without q vertex),minlen(a to q)+minlen(q to b))
    باز هم یک ماتریس جدید بدست میاد:

      p q r s t u
    p 0 9999 9999 9999 3 7
     q 4 0 9999 10 3 11
     r 15 11 0 2 14 22
    s 9999 9999 6 0 11 9999
    t 12 8 6 18 0 9
    u 9 8 9999 18 11 0
  • همینطور یکی یکی راس های رو اضافه میکنیم و در نهایت وقتی که راس ها تموم شد ماتریس نهایی اندازه کوچکترین مسیر از هر راس به سایر رئوس رو نشون میده، در زیر من بقیه ماتریس ها رو هم اوردم:

    ورود راس r به محاسبات:
      p q r s t u
     p  0 9999 9999 9999 3  7
    q 4 0 9999 10 3 11
    r 15 11 0 2 14 22
    s 21 17 6 0 11 28
    t 12 8 6 8 0 9
    u 9 8 9999 18 11 0

    ورود راس s به محاسبات:
      p q r s t u
     p 0 9999 9999 9999 3 7
     q 4 0 16 10 3 11
    r 15 11 0 2 13 22
    s 21 17 6 0 11 28
    t 12 8 6 8 0 9
    u 9 8 24 18 11 0

    ورود راس t به محاسبات:
      p q r s t u
    p  0 11 9 11 3 7
     q 4 0 9 10 3 11
     r 15 11 0 2 13 22
    s 21 17 6 0 11 20
    t 12 8 6 8 0 9
    u 9 8 17 18 11 0

    ورود راس u به محاسبات:
      p q r s t u
    p 0 11 9 11 3 7
    q 4 0 9 10 3 11
    r 15 11 0 2 13 22
    s 21 17 6 0 11 20
    t 12 8 6 8 0 9
    u 9 8 17 18 11 0
    در واقع برای محاسبه طول کوتاه ترین مسیر از هر راس به سایر رئوس کاری که داریم فقط تعدادی محاسبه روی ماتریسیه که از گراف میسازیم و بس، حالا الگوریتمش رو به زبان ++C مینویسم:
    void floyd()
    {
      for(int i=0;i<6;i++)
        for(int j=0;j<6;j++)
          for(int k=0;k<6;k++)
            graph[j][k]=minimum(graph[j][k],graph[j][i]+graph[i][k]);
    }
    

    برای اینکه مساله کامل جا بیفته یه فایل اکسل آماده کردم ( برای دانلود اینجا کلیک کنید) که میتونید ماتریس رو در اون وارد کنید و خودش الگوریتم رو پیاده میکنه و همه این ماتریس هایی که من نوشتم رو حساب میکنه.
    واضحه که پیچیدگی این الگوریتم هم میشه O(n3) چونکه سه تا حلقه تو در تو هست و در کل پیچیدگی در بد ترین حالت با پیچیدگی در حالت میانگین برابره که علتش هم واضحه.

  • الگوریتمی که من نوشتم کامله اما یه مشکل داره و اونم اینه که مشخص نمیکنه که کوتاه ترین مسیر از چه راسهایی عبور میکنه بنابراین نیاز به کمی اصلاح داره، برای اصلاح یک آرایه دو بعدی که اسمش رو p میزاریم، به ابعاد همون ماتریس اولیه ایجاد میکنیم و همه درایه های اون روبرابر شماره ستون میکنیم که در مورد ماتریس 6 در 6 میشه این شکلی:

      p q r s t u
    p 1 2 3 4 5 6
     q 1 2 3 4 5  6
    r 1 2 3 4 5  6
    s 1 2 3 4 5  6
    t 1 2 3 4 5  6
    u 1 2 3 4 5  6

    سپس هر مرحله که تغییری در طول مسیر مینیمم ایجاد شد راسی که این تغییر رو ایجاد کرده در این آرایه ثبت میکنیم مثلا در همین ماتریس های بالایی وقتی که راس t رو به محاسبات وارد کردیم ردیف اول ماتریس سه تا بی نهایت تبدیل به 11 و 9 و 11 شده پس میشه در جای اونها در ماتریس p عدد 5 رو بزاریم تا ماتریس این شکلی بشه:

      p q r s t u
    p 1 5 5 5 5 6
     q 1 2 3 4 5 6
     r 1 2 3 4 5 6
     s 1 2 3 4 5 6
    t 1 2 3 4 5 6
    u 1 2 3 4 5 6

    به این ترتیب وقتی که کار تموم شد ماتریس این شکلی میشه:


      p q r s t u
    p 1 5 5 5 5 6
     q 1 2 5 4 5 1
     r 2 2 3 4 4 2
     s 3 3 3 4 5 5
    t 2 2 3 3 5 6
    u 1 2 5 2 2 6

    اعداد موجود در این ماتریس به ما میگه که کوتاه ترین مسیر از هر گره به سایر گره ها از چه گره ای میگذره (البته به صورت بک عدد) مثلا بر طبق این ماتریس کوتاه ترین مسیر از گره p به گره s از گره 5 که همون t میشه میگذره.
    حالا الگوریتم اصلاح شده رو دوباره میزارم:

    void floyd()
    {
      for(int i=0;i<6;i++)
        for(int j=0;j<6;j++)
          for(int k=0;k<6;k++)
            if(graph[j][k] > graph[j][i] + graph[i][k])
            {
              graph[j][k] = graph[j][i] + graph[i][k];
              p[j][k] = i;
            }
    }
    

 حالا فقط یک مطلب باقی میمونه و اونم اینه که از روی ماتریس p چطور میشه کوتاه ترین مسیر رو پیدا کرد؟

خب جواب به این صورته که درایه های ماتریس p به ما میگه که کوتاه ترین مسیر از یک راس به راس دیگه از کدوم راس عبور میکنه البته به صورت عددی یعنی هر عدد مخصوص یک راسه و من الگوریتم رو برای این به این صورت نوشتم چون اگه بخواهیم الگوریتمی بنویسیم که کوتاه ترین مسیر رو نشون بده این آرایه به این صورت کار رو خیلی راخت میکنه، الگوریتم محاسبه کوتاه ترین مسیر به این صورته (واضحه که به صورت بازگشتی پیاده سازی شده) :

void path(int a, int b)
{
  char vert[6]={'p','q','r','s','t','u'}
  if( p[a][b] == b) cout << vert[b];
  else 
  {
    cout << vert[a] << "-->" ;
    path(p[a][b],b);
  }
}

در صورتی که گراف ما دارای یال با طول منفی نباشه این پیچیدگی این الگوریتم حداکثر از درجه O(n) میشه چون حداکثر میشه از همه گره ها که تعدادشون n هست عبور کنیم (اثبات این قضیه دیگه با خودتون) اما اگه گراف یالی با طول منفی داشته باشه اون وقت قضیه فرق میکنه که البته در فرضیات اولیه مساله گفتیم گراف ما سال با طول منفی نداره.

اما اگر به جای هر عدد در جدول p حرف مخصوص اون رو بگذاریم جدول این شکلی میشه:

  p q r s t u
p p t t t t u
 q p q t s t p
 r q q r s s q
 s r r r s t t
t q q r r t u
u p q t q q u

مثلا در جدول روبروی سطر s و ستون p نوشته r که به این معنیه که کوتاه ترین مسیر از s به p از راس r میگذره، برای پیدا کردن بقیه مسیر کافیه از همین جدول کوتاه ترین مسیر از r به p  رو پیدا کنیم که میشه q و کوتاه ترین مسیر از q به p هم طبق جدول مسیر مستقیمه، پس مشخصه که کوتاه ترین مسیر از s به p به صورت s-->r-->q-->p میشه

 در ضمن میشه الگوریتم رو به این صورت نوشت تا از ابتدا همین جدول رو تولید کنه:

void floyd()
{
  char vert[5]={'p','q','r','s','t','u'};
for(int i=0;i<6;i++) for(int j=0;j<6;j++) for(int k=0;k<6;k++) if(graph[j][k] > graph[j][i] + graph[i][k]) { graph[j][k] = graph[j][i] + graph[i][k]; p[j][k] = vert[i]; } }

 این ماتریس آخری که گفتم بیشتر به درد کسی میخوره که خودش مستقیم میخاد مسیر رو پیدا کنه و گر نه همون ماتریس اولی که عددی بود خیلی بیشتر به درد میخوره.


برای اطلاعات بیشتر:

https://fa.wikipedia.org/

http://www.algorithmha.ir/

http://maktabkhooneh.org/video/qodsi-algorithm-8

بی کارت

 مدیریت کارت های بانکی

دانلود اپلیکیشن بی کارت از بازار:
https://goo.gl/cyNai2

تبلیغات


  تهران هاست
ارائه کننده خدمات میزبانی وب

 


 

مهندس رضا زنگنه

انجام هرگونه تعمیرات PC و لب تاپ در اصفهان

09387652826