اخبار فناوری و شبکه

اخبار فناوری و شبکه

تازه های شبکه و IT
اخبار فناوری و شبکه

اخبار فناوری و شبکه

تازه های شبکه و IT

پیدا کردن کوتاه ترین مسیر بین دو نقطه در گراف – بازگشتی (Shortest path)

یدا کردن کوتاه ترین مسیر بین دو نقطه در یک گراف اهمیت خیلی زیادی در علوم مختلف مانند الگوریتم  ٫ ریاضی ٫ حمل و نقل ٫تجارت و …. دارد .

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

برای پیدا کردن کوتاه ترین مسیر بین دو نقطه الگوریتم های بسیار زیادی وجود دارد ولی سه الگوریتم با سه روش مختلف وجود دارند که بسیار معروف هستند :  1- الگوریتم به روش بازگشتی (Recursion) : که شامل تقسیم و حل و انواع روش های سرچ می شود. که در این پست ما فضای حالتمان را سرچ کرده ایم.

۲-  الگوریتم به روش برنامه نویسی پویا (Dynamic programming ) : معروف به فلوید

۳- الگوریتم به روش حریصانه  (Greedy ) :معروف به دایکسترا

ما در این پست الگوریتم بازگشتی را بررسی می کنیم و دو الگوریتم دیگر را در پست هایی جداگانه بررسی خواهیم کرد.

فرض کنید گراف زیر را دارید و می خواهید کوتاه ترین فاصله بین دو نقطه دلخواه را پیدا کنید ، ما حل سوال را با این مثال ادامه می دهیم:

graph همین طور که در بالا می بینید گراف دارای راس های v0 – v1- v2-v3-v4  است و راه های موجود بین راس ها با یال های که از آن راس خارج شده و به راس دیگر وارد شده است مشخص شده است و فاصله بین دو نقطه برابر با  عددی است که روی یال نوشته شده است.

ما برای پیدا کردن کوتاه ترین مسیر ها باید گراف را پردازش کنیم برای این کار گراف را به صورت ماتریس مجاورت در می آوریم ، ماتریس مجاورت گراف بالا به صورت زیر است :
فشذمثدر گراف قبل از راس سه به یک راهی وجود نداشت به همین خاطر در ماتریس بالا جاهایی که یالی وجود ندارد مقدار بینهایت (Infinity) گذاشتم .

فرض کنید می خواهیم کوتاه ترین مسیر از گره شماره ۲ را به گره شماره یک پیدا کنیم ، ابتدا گره ی مقصد  را که همان گره ی شماره یک است را در نظر می گیریم و شروع به عقب آمدن می کنیم تا به مبدا حرکت برسیم که اینجا گره شماره دو است  و از میان تمام راه های ممکن کوتاه ترین راه را  انتخاب می کنیم.

به ستون  زیر گره ی شماره یک نگاه کنید که  پنج خانه در زیرش قرار دارد که می گویند :

خانه اول : اگر از نود صفر به یک برویم طول مسیر برابر یک است

خانه دوم : اگر از نود یک به به نود یک برویم طول مسیر برابر صفر است

خانه سوم : اگر از نود دو به نود یک برویم طول مسیر بی نهایت است یعنی در واقع مسیری وجود ندارد

خانه چهارم : اگر از نود سوم به نود یک برویم هزینه بی نهایت است

خانه پنجم : اگر از نود چهار به نود یک برویم هزینه بی نهایت است

پس خانه های زیر نود  یک ، مسیر های منتهی به نود یک را نشان می دهد ، از میان مسیر هایی که به نود یک منتهی می شود فقط مسیر صفر به یک مورد قبول است .

حالا صورت سوال را تغییر می دهیم:

   کوتاه ترین مسیر از نود دو به یک  = کوتاه ترین مسیر از نود دو به نود صفر + فاصله نود صفر تا نود یک

 که حالا همین کار را برای کوتاه ترین مسیر از نود دو به نود صفر می کنیم، همین طور که می بینید دو مسیر داریم که به نود صفر منتهی می شود یکی نود یک به نود صفر که طولی برابر نه دارد و دیگری مسیر نود چهار به نور صفر که طولی برابر سه دارد پس کوتاه تریم مسیر از نود دو به نود صفر اینگونه محاسبه می شود

کوتاه ترین مسیر از نود شماره دو به نود صفر = min( کوتاه ترین مسیر از نود دو به نود یک به علاوه نه ، ک.تاه ترین مسیر از نود شماره دو به نود شماره چهار به علاوه سه)

و همین کار را تا آخر ادامه می دهیم .

فقط ممکن است تو مسیری دایره واز بیفتیم و هیچ وقت خارج نشویم برای حل این مشکل در کد چک می کنیم که اگر نود های نوجود در مسیر از تعداد کل نود های منهای یک بزرگ تر مساوی بود مسیر قابل قبول نیست زیرا طبق اصل لانه کبوتری نودی وجود دارد که حداقل دوبار از آن عبور شده است

کد زیر تابع مربوط به حل بازگشتی مساله است

  int ** table :  ماتریس مجاورت است که به صورت اشاره گر به تابع فرستاده می شود

n : تعداد راس های موجود در گراف است

p: راس مبدا  است

q: راس مقصد است

z: تعداد راس های موجود در مسیر طی شده است

کد زیر یک مثال از کد بالاست که  دارای main  است و برای نمونه مثالی را که بررسی کردیم  را به تابع  فرستادم که مقدار یازده را به عنوان جواب بازگرداند:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Short distance.cpp
//
 
#include "stdafx.h"
#include <iostream>
 
#define inf 2000000000
 
using namespace std;
 
int short_distance(int **table, int n, int p,int q, int z)
{
int min = inf;
int *A;
A = new int[n];
if (p == q)
{
return 0;
}
if (z >= n-1 )
{
return inf;
}
for (int i = 0; i < n; i++)
{
if (table[i][q] != 0 && table[i][q] != inf)
{
A[i] = table[i][q] + short_distance(table, n, p, i, z + 1);
if (min > A[i] && A[i] > 0)
{
min = A[i];
}
}
}
return min;
}
 
int main( )
{
//define table
int **table;
table = new int *[5];
for (int i = 0; i < 5; i++)
{
table[i] = new int[5];
}
 
table[0][0] = 0;
table[0][1] = 1;
table[0][2] = inf;
table[0][3] = 1;
table[0][4] = 5;
 
table[1][0] = 9;
table[1][1] = 0;
table[1][2] = 3;
table[1][3] = 2;
table[1][4] = inf;
 
table[2][0] = inf;
table[2][1] = inf;
table[2][2] = 0;
table[2][3] = 4;
table[2][4] = inf;
 
table[3][0] = inf;
table[3][1] = inf;
table[3][2] = 2;
table[3][3] = 0;
table[3][4] = 3;
table[4][0] = 3;
table[4][1] = inf;
table[4][2] = inf;
table[4][3] = inf;
table[4][4] = 0;
//
 
cout << "Short distance among 2 and 1 :=  " << short_distance(table, 5, 2, 1, 0) << endl << endl;
 
return 0;
}

Ali پنج‌شنبه 3 دی 1394 ساعت 08:37
نظرات 0 + ارسال نظر
امکان ثبت نظر جدید برای این مطلب وجود ندارد.