بخشی از مقاله
تحليل مساله كوتاهترين مسير در گراف جهت دار
اگر يك گراف جهت دار باشد فرض كنيد هر لبه با وزن مشخص مي گردد و هزينه رفتن مستقيم از گره i به j را مشخص ميسازد بزودي الگوريتم دايجسترا را كه براي يافتن كوتاهترين مسير در گراف با وزن هاي مثبت كاربرد دارد را بيان ميكنيم . در این بخش و بخش بعدي دو مساله مرتبط با گراف را بيان خواهيم كرد .
1 ) گراف G را در نظر بگيريد ( وزن دار ) اگر این گراف داراي سيكل منفي باشد آنگاه يك سيكل جهت دار c مثل :
2) اگر گراف شامل هيچ دوره ( سيكل) منفي نباشد يافتن مسيري به نام p از گره آغازي s و گره پاياني t با كمترين هزينه : بايد كمترين باشد به ازاي هر مسير از s به t . این مساله به هر دو نام مسير با كمترين هزينه و كوتاهترين مسير ناميده مي شود .
طراحي و آناليز الگوريتم :
اكنون با شروع تعريف مجدد الگوريتم دايجسترا كه براي يافتن كوتاهترين مسير در گراف هايي كه وزن منفي ندارند شروع ميكنيم .
در این گراف يك مسير از s به t با ملاقات چندين دفعه دوره ( سيكل ) C بدست مي آيد .
كوتاهترين مسير با شروع از گره آغازين s به هر نود v در يك گراف اصولا يك الگوريتم حريصانه است . ايده اصلي از يك مجموعه S تشكيل شده است كه كوتاهترين مسير از هر نود s به هر نود داخل مجموعه S شناخته شده است . در این شكل این الگوريتم را نشان مي دهيم با شروع ميكنيم . ما ميدانيم كوتاهترين مسير از s به s داراي هزينه صفر است زمانيكه هيچ لبه با وزن منفي نداشته باشيم . سپس این عنصر را به طور حريصانه به مجموعه اضافه ميكنيم . در طي مرحله اول الگوريتم حريصانه ما كمترين هزينه لبه هاي گره s را تشكيل خواهيم
داد . بعبارت ديگر يعني : . يك نكته مهم با توجه به الگوريتم دايجسترا این است كه كوتاهتري مسير از s به v با يك يال نمايش داده مي شود بنابراين بلافاصله نود v را به مجموعه S اضافه ميكنيم . پس مسير مسلما كوتاهترين مسير به v است اگر هيچ يالي با هزينه منفي نداشته باشيم . مسير هاي ديگر از s به v بايد از يك يال خارج شده از s كه حداقل هزينه بيشتري نسبت به لبه (s,v) داشته باشند شروع ميشوند .
این ايده همواره صحيح نيست بويژه زماني كه داراي لبه هاي با وزن منفي هستيم .
يك ايده برنامه نويسي پويا :
يك روش برنامه نويسي پويا سعي بر حل این مساله براي يافتن كوتاهترين مسير از s به t زمانيكه لبه با وزن منفي داشته باشيم اما سيكل ( دوره ) با طول منفي نداشته باشيم . زر مساله i مي تواند كوتاهترين مسير را تنها بوسيله استفاده از i گره اوليه پيدا كند . این ايده بلافاصله جواب نمي دهد بلكه با اعمال اندكي تغييرات جواب دلخواه را به ما ميدهد . الگوريتم Bellman-Ford algorithm اين الگوريتم را بوسيله برنامه نويسي پويا مطرح كرده و حل كرده اند .
(6.22)
اگر G دورهای منفی نداشته باشد؛ پس کوتاهترین مسیر ساده از S به t وجود دارد.(یعنی گره ها تکرار نمی شوند.) و از اینرو در نهایت n-1 یال دارد.
اثبات: تا زمانی که هر دور هیچ هزینه منفی نداشته باشد؛ کوتاهترین مسیر P از s به t با بیشترین تعداد از یالها هیچ راس v را مرور نمی کند. اگر P ؛ راس v را تکرار کند؛ ما می توانیم بخش مابین عبورهای متوالی از v را حذف کنیم. که این عمل هزینه کمینه و یال بیشینه را نتیجه می دهد.
اجازه دهید OPT(i,v) را برای تفکیک کمترین هزینه یک مسیر v-t با استفاده از بیشترین یال i مورد استفاده قرار دهیم. مطابق مساله (6.22) اصی ترین مشکل؛ محاسبه OPT(n-1.s) است.(ما می توانیم به جای ساخت الگوریتم؛ زیر مسائل مرتبط با کمینه هزینه مسیر s-v را با استفاده از بیشترین یالi جایگزین کنیم. این یک موازی طبیعی با الگوریتم دایجسترا شکل خواهد داد. اما در پروتوکل های مسیر یابی که بعدا شرح خواهیم داد؛ این یک روش طبیعی نخواهد بود.)
اکنون راه ساده ای را برای بیان OPT(i,v) با استفاده از زیرمسائل کوچکتر نیازداریم. ما دیداه طبیعی تری که نکات بسیاری حالات مختلف را در بر می گیرد را مرور خواهیم کرد؛ این مثال دیگری است از اصل "انتخابهای چند مسیره" که در الگوریتم مساله کوچکترین مربعات بخش شده خواهیم دید.
اجازه دهید؛ مسیر بهینه p OPT(i,v) را که در شکل 6.22 نمایش داده شده است را اثبات کنیم.
• اگر مسیر p در حداکثر i-1 مورد استفاده قرار گیرد؛ در اینصورت خواهیم داشت:
OPT(i, v) = OPT(i −1, v)
• اگر مسیر p ؛ i یال را مورد استفاده قرار دهد و اولین یال (v,w) باشد؛ در اینصورت:
OPT(i, v) = cvw + OPT(i − 1, w)
این موارد ما را به فرمول بازگشتی زیر می رساند:
(6.23) If i > 0 then
OPT(i, v) = min(OPT(i − 1, v), min
w∈V
(OPT(i − 1, w) + cvw)).
با استفاده از فرمول بازگشتی؛ ما الگوریتم برنامه نویسی پویای زیر را برای محاسبه هزینه OPT(n-1) خواهیم داشت:
Shortest-Path(G, s, t)
n = number of nodes in G
Array M[0 . . . n − 1, V]
Define M[0, t] = 0 and M[0, v] = ∞ for all other v ∈ V
For i = 1, . . . , n − 1
For v ∈ V in any order
Compute M[i, v] using the recurrence (6.23)
Endfor
Endfor
Return M[n − 1, s]
صحت متد بصورت مستقیم از استقراء (6.23) پیروی می کند. ما می توانیم زمان اجرای برنامه را محدود کنیم. جدول M؛ n به توان دو ورودی دارد؛ و هر ورودی می تواند O(n) زمان محاسبه داشته باشد؛ پس حداکثر n گره w ∈ V برای مرور کردن وجود دارد.
(6.24) متد "کوتاهترین مسیر" به درستی کمترین هزینه یک مسیر s-t را در گرافی که فاقد دور منفی است محاسبه می کندو و در زمان O(n3) اجرا می کند. داده جدول M که هزینه های معین زیربرنامه ها را دربردارد کوتاهترین مسیر را با استفاده از حداکثر i یال با O(in) بدست می دهد که این عمل با تراک بک در کوتاهترین زیربرنامه ها حاصل می شود.
بعنوان یک مثال؛ مرور گراف در شکل 6.22؛ جایی که هدف؛ یافتن کوتاهترین مسیر از هر گره به t است؛ جدول سمت راست آرایه M و ورودی های مطابق با هزینه های M[i,v] از الگوریتم را نمایش می دهد.
چنانچه ما اجازه دهیم مسیر از بیشترین شمار یالها استفاده کند؛ یک تک ردیف از جدول؛ مطابق با کوتاهترین مسیر از یک گره خاص به t است.
به عنوان مثال؛ کوتاهترین مسیر از گره d به t چهار بار به روز شده است؛ یعنی از d-t؛ به d-a-t به d-a-b-e-t و در نهایت به d-a-b-e-c-t انجام می شود.
ضمایم: بهينه سازيهاي مهم الگوریتم
در حالتی که گراف G یالهای زیادی ندارد ما واقعا می توانیم یک تحلیلگر زبان اجرای بهتری تهیه کنیم. گراف جهت دار A با n گره می تواند n2 یال داشته باشد؛ چنانچه آنها می توانند بصورت بالقوه یالی بین دو جفت از گره ها داشته باشند. اما بسیاری گرافها کم پشت تر از این هستند و زمانی که ما با گرافی با همه یالهای m کار می کنیم بصورت معنی داری از n به توان 2 کمتر می شود. ما قبلا دیدیم که در حالات قبلی کتاب؛ این حالت می توانست برای نوشتن زمان اجرا بر حسب m,n مفید باشد؛
از این راه می توانیم تسریع در گرافها را با یالهای نسبتا کمتری تعیین کنیم. اگر ما کمی بیشتر در تحلیل متد بالا دقیق شویم می توانیم محدودیت زمان اجرا را تا O(mn) بهبود دهیم و این مهم بدون تغییر قابل توجهی در الگوریتم ممکن می شود.
(6.25)
متد "کوتاهترین مسیر" می تواند با زمان O(mn) انجام شود.
اثبات: مرور محاسبه ورودی آرایه M(i,v) مطابق حالت بازگشتی (6.23) است.
M[i, v]= min(M[i − 1, v], min
w∈V
(M[i − 1, w]+ cvw)).
در صورتی که n گره ممکن w وجود داشته باشد؛ ما وانمود می کنیم که آن می تواند زمان O(n) را برای محاسبه این کمینه صرف کند!
البته ما فقط نیاز داریم؛ کمینه تمام گره های w را برای هر v که یک یال به w دارد را محاسبه کنیم؛ اجازه دهید ما از nv برای تفکیک این شماره استفاده کنیم. پس آن؛ زمان O(nv) را برای محاسبه آرایه ورودی M[i,v] صرف می کند. ما مجبوریم یک ورودی برای هر گره v و هر داده بین
0 ≤ i ≤ n − 1 را محاسبه کنیم بنابر این این محدوده زمان اجرای زیر را نتیجه می دهد
در بخش سه؛ ما عینا این نوع از تحلیل را برای الگوریتم های گراف دیگر انجام می دهیم؛ و از (3.9) را برای محدود کردن عبارت برای گراف غیر جهت دارد مورد استفاده قرار دادیم.
اینجا ما با گرافهای جهت دار تعامل داریم. و nv تعداد یالهای خارج شده از v را مشخص می کند. از این جهت؛ راحتتر از بدست آوردن هزینه برای حالات جهت دار است؛ هر یال بدرستی یکی از ره ها در v را ترک م کند و بنابراین هر یال عینا یکبار در این عبارت شمارش می شود. بنابراین ما داریم برابر m است.
با تجزیه این عبارت؛ برای زمان اجرا؛ ما محدوده زمان اجرای O(mn) را خواهیم داشت. همچنین می توانیم بصورت معنی داری حافظه موردنیاز را فقط با تغییر کوچکی در پیاده ساز بهبود ببخشیم. مشکل عمده بسیاری از الگوریتم های برنامه نویسی پویا؛ فضای زیاد مورد استفاده آنهاست. که ناشی از آرایه M است که نیاز به ذخیره دارد. در الگوریتم Bellman-ford آنطور که گفته شد این آرایه از درجه n به توان 2 است؛هرچند ما اکنون نشان می دهیم که چگونه می توان آن را به O(n) کاهش داد. سریعتر از ذخیرهm[i,v] برای هر هزینه i ؛ استفاده خواهیم کرد. هزینه تنهای m[v] را برای هر گره v؛ طول کوتاهترین مسیر؛ از v به t که ما تا به حال یافته ایم. هنوز الگوریتم را برای تکرارهای i = 1, 2, . . . , n − 1 تکرار می کنیم اما نقش i اکنون به سادگی بعنوان یک شمارنده خواهد بود؛ در هر تکرار؛ و برای هر گره v ما بروزرسانی را اجرا خواهیم کرد.
M[v]= min(M[v], min
w∈V
(cvw + M[w])).
تمام الگوریتم M[v]؛ طول تعدادی مسیر از v به t است و پس از چرخش به روزرسانی ها؛ هزینه m[v] بیشتر از طول کوتاهترین مسیر از vبه t با استفاده ازحداکثر یالهای i نخواهد بود.
پس از آنه ذخیره آرایه M که فهرست های گره ها را ذخیره می کند؛ این فقط کار حافظه o(n) را نیاز دارد.
تابع bellman fordدر زبان c++:
procedure BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices
// and edges, and modifies the vertices so that their distance and
// predecessor attributes store the shortest paths.
// Step 1: Initialize graph
for each vertex v in vertices:
if v is source then v.distance := 0
else v.distance := infinity
v.predecessor := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge uv in edges:
u := uv.source
v := uv.destination // uv is the edge from u to v
if v.distance > u.distance + uv.weight:
v.distance := u.distance + uv.weight
v.predecessor := u
// Step 3: check for negative-weight cycles
for each edge uv in edges:
u := uv.source
v := uv.destination
if v.distance > u.distance + uv.weight:
