روی خط خبر

  • 12120
  • الگوریتم دایجسترا :: .NET Developer

منبع: 12120
امتیاز: 5 5

الگوریتم دایجسترا :: .NET Developer از وبلاگ .NET Developer 12120

الگوریتم دایجسترا :: .NET Developer

نام این الگوریتم بر اساس نام ارائه دهنده هلندی آن، یعنی اِدسخِر دایکسترا انتخاب شده است. در منابع فارسی آن را به شکل های دِیکسترا، دکسترا، دایکسترا، دایجسترا، دیجسترا، دایجکسترا و دیجکسترا هم نوشته شده است، ولی جیمِ آن در تلفظ هلندی آن تلفظ نمی شود، لذا دو مورد اول صحیح هستند. الگوریتم دایجسترا راه کاری برای پیدا کردن کم وزن مسیر از رأس مشخص آغاز به بقیه رئوس در گراف جهت دار و وزن دار (با وزن های مثبت) می دهد. وزن یک مسیر در گراف وزن دار برابر مجموع وزن یال های آن است. جهت دار نبودن یال ها هم مشکلی ایجاد نمی کند و می توان برای یال های غیر جهت دار دو یال فرض کرد. لگوریتم فرض کنید 1≤ s≤n که در آن رأس s رأس آغاز است و فرض کنید: dist(r)=0 و به ازای هر v≠r: dist(v)=∞ فرض کنید مجموعه ی T برابر رئوسی باشد که تا کنون کم وزن ترین مسیر آن ها را پیدا کرده ایم. این الگوریتم در هر مرحله نزدیک ترین رأس به s را که تا کنون به مجموعه ی T اضافه نشده را انتخاب می کند (مثلا x) و آن را به مجموعه ی T اضافه می کند و فاصله ی دیگر رأس ها را با توجه به فاصله ی x بروز می کند. به ازای هر رأس v خارج T:.... dist(v)=min(dist(v),dist(x)+w(x,v)) که در آن w(x,v) برابر وزن یال بین x و v است. این الگوریتم در هر مرحله رأسی را که کوتاه ترین فاصله ی آن تا s پیدا شده است را به T اضافه می کند. زیرا کوتاه ترین مسیر این رأس از یکی از رأس های T می گذرد که در مراحل قبلی فاصله آن ها بدست آمده و دیگر رئوس را بروز کرده اند. در نظریه گراف، الگوریتم دیکسترا (به انگلیسی: Dijkstra's algorithm) یکی از الگوریتم های پیمایش گراف است که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دیْکْسْترا در سال ۱۹۵۹ ارائه شد. این الگوریتم یکی از الگوریتم های پیمایش گراف است که مسئلهٔ کوتاه ترین مسیر از مبدأ واحد را برای گراف های وزن داری که یال با وزن منفی ندارند، حل می کند و در نهایت با ایجاد درخت کوتاه ترین مسیر، کوتاه ترین مسیر از مبدأ به همهٔ رأس های گراف را به دست می دهد. همچنین می توان از این الگوریتم برای پیدا کردن کوتاه ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاه ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد. الگوریتم دیکسترا یکی از الگوریتم های مورد استفاده برای محاسبه کوتاه ترین مسیر تک منبع (single-source shortest path) است و مشابه الگوریتم پریم می باشد در صورتی که گراف یال با وزن منفی داشته باشد، این الگوریتم درست کار نمی کند و می بایست از الگوریتم های دیگر نظیر الگوریتم بلمن-فورد که پیچیدگی زمانی آن ها بیشتر است استفاده کنیم. خط مشی الگوریتم دیکسترا، مشابه با روش حریصانهٔ استفاده شده در الگوریتم پریم برای پیدا کردن زیر درخت فراگیر بهینه است. روند الگوریتم دایکسترا مطابق زیر می باشد: ۱- انتخاب راس مبدا پیمایش گراف و پیمایش درخت هرس آلفا بتا A* B* Beam الگوریتم بلمن–فورد جستجوی ابتدا بهترین جستجوی دوجهته الگوریتم جستجوی اول سطح D* الگوریتم جستجوی عمق اول جستجوی عمق محدود الگوریتم دیکسترا الگوریتم فلوید-وارشال الگوریتم تپه نوردی جستجوی عمق اول عمیق کننده تکراری الگوریتم جانسون Lexicographic breadth-first Uniform-cost رده:الگوریتم های جستجو جستار وابسته برنامه ریزی پویا Search games ۲- مجموعهٔ S، شامل رئوس گراف، معین می شود. در شروع، این مجموعه تهی بوده و با پیشرفت الگوریتم، این مجموعه رئوسی که کوتاه ترین مسیر به آن ها یافت شده است را در بر می گیرد. ۳- راس مبدأ با اندیس صفر را در داخل S قرار می دهد. ۴- برای رئوس خارج از S، اندیسی معادل، طول یال + اندیس راس قبلی، در نظر می گیرد. اگر راس خارج از مجموعه دارای اندیس باشد، اندیس جدید کمترین مقدار از بین اندیس قبلی و طول یال + اندیس راس قبل، می باشد. ۵- از رئوس خارج مجموعه، راسی با کمترین اندیس انتخاب شده و به مجموعهٔ S اضافه می گردد. ۶- این کار را دوباره از مرحلهٔ ۴ ادامه داده تا راس مقصد وارد مجموعهٔ S شود. در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهندهٔ مسافت بین مبدأ و مقصد می باشد. در غیر این صورت هیچ مسیری بین مبدأ و مقصد موجود نمی باشد. همچنین برای پیدا کردن مسیر می توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهندهٔ راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن رئوس قبلی از مقصد به مبدا، کوتاه ترین مسیر بین دو نقطه نیز یافت می شود. هدف در حین اجرای الگوریتم دو چیز به طور ضمنی نگهداری می شود. یکی مجموعهٔ {\displaystyle S} از رأس هایی که وزن کوتاه ترین مسیر از مبدأ تا آن ها مشخص شده و دیگری دنبالهٔ {\displaystyle d}  که برای هر رأس {\displaystyle v} ، مقدار {\displaystyle d_{v}}  برابر وزن کوتاه ترین مسیر از مبدأ تا {\displaystyle v}  است به شرطی که تمام رأس های این مسیر به جز {\displaystyle v}  از رئوس داخل {\displaystyle S}  باشند. {\displaystyle S}  در ابتدا تهی و مقادیر {\displaystyle d}  برای همهٔ رئوس به غیر از مبدأ بی نهایت است و مقدار آن برای مبدأ صفر گذاشته می شود. الگوریتم در هر مرحله رأسی خارج {\displaystyle S}  را که {\displaystyle d}  برای آن کمترین است انتخاب و به مجموعهٔ {\displaystyle S}  اضافه می کند و سپس مقادیر {\displaystyle d}  را برای رئوس همسایهٔ آن رأس به روز می نماید. در صورتی که نیاز به تشکیل درخت کوتاه ترین مسیر باشد، الگوریتم می بایست دنبالهٔ {\displaystyle \pi }  را که {\displaystyle \pi _{v}}  پدر رأس {\displaystyle v}  در درخت کوتاه ترین مسیر است، به همراه دنبالهٔ {\displaystyle d}  به روز کند. کاربردها از جمله مهمترین کاربردهای این روش می توان به محاسبهٔ کوتاه ترین فاصلهٔ دو نقطه در یک شهر از طریق راه های زمینی اشاره نمود. برای محاسبهٔ کوتاه ترین مسیر بین دو نقطه باید نقاط مورد نظر در یک نقشه را علامت گذاری کرد و با استفاده از مشخصات نقاط (طول، عرض و ارتفاع) فاصلهٔ دو نقطه را در هر بار عملیات محاسبه نمود. توجه داریم که در ترافیک سرعت خودروها به شدت پایین آمده و این امر می تواند در انتخاب کوتاه ترین مسیر تأثیر گذار باشد چرا که ممکن است بین دو نقطه a,b راه های ۱و۲ موجود باشد که راه ۱ اتوبان و از خارج شهر و راه ۲ از داخل شهر عبور می کند. فرض کنید فاصلهٔ a,b از طریق راه ۱ حدود ۱۰ کیلومتر و از طریق راه ۲ حدود ۷ کیلومتر باشد ولی راه ۲ علی رقم فاصلهٔ کمتر دارای ترافیک سنگین است در نتیجه می توان انتظار داشت که در ساعات شلوغی استفاده از راه ۱ بهتر باشد. از آن جا که اساس محاسبات در این روش بر پایهٔ فاصله بین دو نقطه است می توان کاهش سرعت را با افزایش فواصل هم ارز نمود چرا که اگر رابطهٔ سرعت و فاصله را خطی در نظر بگیریم (D=V.T)تاثیر کاهش سرعت و افزایش مسافت یکسان است. از این رو لازم است تا ضرایب تعدیلی در فواصل بین نقاط ضرب شده و این مسائل را در محاسبات لحاظ کرد. از جمله مهم ترین این ضرایب می توان به ۳ مورد زیر اشاره نمود: ۱-ضریب ترافیک و شلوغی ۲-ضریب عرض معبر ۳-ضریب شیب که نشانگر افت سرعت در سر بالایی هااست. گرچه تعیین این ضرایب برای نقاط مختلف شهر نیازمند کارشناسان متخصص ترافیک و بررسی های آماری دقیق می باشد ولی می توان انتظار داشت که در اکثر موارد این ضرایب بین مقادیر ۱ تا ۲ بسته به شرایط تغییر کنند نمونه و مثال using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace DijkstraAlgorithm { class Dijkstra { private static int MinimumDistance(int[] distance, bool[] shortestPathTreeSet, int verticesCount) { int min = int.MaxValue; int minIndex = 0; for (int v = 0; v < verticesCount; ++v) { if (shortestPathTreeSet[v] == false && distance[v] <= min) { min = distance[v]; minIndex = v; } } return minIndex; } private static void Print(int[] distance, int verticesCount) { Console.WriteLine("Vertex Distance from source"); for (int i = 0; i < verticesCount; ++i) Console.WriteLine("{0}\t {1}", i, distance[i]); } public static void DijkstraAlgo(int[,] graph, int source, int verticesCount) { int[] distance = new int[verticesCount]; bool[] shortestPathTreeSet = new bool[verticesCount]; for (int i = 0; i < verticesCount; ++i) { distance[i] = int.MaxValue; shortestPathTreeSet[i] = false; } distance[source] = 0; for (int count = 0; count < verticesCount - 1; ++count) { int u = MinimumDistance(distance, shortestPathTreeSet, verticesCount); shortestPathTreeSet[u] = true; for (int v = 0; v < verticesCount; ++v) if (!shortestPathTreeSet[v] && Convert.ToBoolean(graph[u, v]) && distance[u] != int.MaxValue && distance[u] + graph[u, v] < distance[v]) distance[v] = distance[u] + graph[u, v]; } Print(distance, verticesCount); } static void Main(string[] args) { int[,] graph = { { 0, 6, 0, 0, 0, 0, 0, 9, 0 }, { 6, 0, 9, 0, 0, 0, 0, 11, 0 }, { 0, 9, 0, 5, 0, 6, 0, 0, 2 }, { 0, 0, 5, 0, 9, 16, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 6, 0, 10, 0, 2, 0, 0 }, { 0, 0, 0, 16, 0, 2, 0, 1, 6 }, { 9, 11, 0, 0, 0, 0, 1, 0, 5 }, { 0, 0, 2, 0, 0, 0, 6, 5, 0 } }; DijkstraAlgo(graph, 0, 9); Console.ReadKey(); } } } خروجی Vertex Distance from source 0 0 1 6 2 15 3 20 4 22 5 12 6 10 7 9 8 14 جهت استفاده سور رو قرار میدم دانــــــلود سورس دایجسترا

نام این الگوریتم بر اساس نام ارائه دهنده هلندی آن، یعنیاِدسخِر دایکستراانتخاب شده است. در منابع فارسی آن را به شکل های دِیکسترا، دکسترا، دایکسترا، دایجسترا، دیجسترا، دایجکسترا و دیجکسترا هم نوشته شده است، ولی جیمِ آن در تلفظ هلندی آن تلفظ نمی شود، لذا دو مورد اول صحیح هستند.الگوریتم دایجسترا راه کاری برای پیدا کردن کم وزن مسیر از رأس مشخص آغاز به بقیه رئوس در گراف جهت دار و وزن دار (با وزن های مثبت) می دهد. وزن یک مسیر در گراف وزن دار برابر مجموع وزن یال های آن است. جهت دار نبودن یال ها هم مشکلی ایجاد نمی کند و می توان برای یال های غیر جهت دار دو یال فرض کرد.لگوریتمفرض کنید 1≤ s≤n که در آن رأس s رأس آغاز است و فرض کنید:dist(r)=0و به ازای هر v≠r:dist(v)=∞فرض کنید مجموعه ی T برابر رئوسی باشد که تا کنون کم وزن ترین مسیر آن ها را پیدا کرده ایم. این الگوریتم در هر مرحله نزدیک ترین رأس به s را که تا کنون به مجموعه ی T اضافه نشده را انتخاب می کند (مثلا x) و آن را به مجموعه ی T اضافه می کند و فاصله ی دیگر رأس ها را با توجه به فاصله ی x بروز می کند. به ازای هر رأس v خارج T:....dist(v)=min(dist(v),dist(x)+w(x,v))که در آن w(x,v) برابر وزن یال بین x و v است. این الگوریتم در هر مرحله رأسی را که کوتاه ترین فاصله ی آن تا s پیدا شده است را به T اضافه می کند. زیرا کوتاه ترین مسیر این رأس از یکی از رأس های T می گذرد که در مراحل قبلی فاصله آن ها بدست آمده و دیگر رئوس را بروز کرده اند.در نظریه گراف، الگوریتم دیکسترا (به انگلیسی: Dijkstra's algorithm) یکی از الگوریتم های پیمایش گراف است که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دیْکْسْترا در سال ۱۹۵۹ ارائه شد.این الگوریتم یکی از الگوریتم های پیمایش گراف است که مسئلهٔ کوتاه ترین مسیر از مبدأ واحد را برای گراف های وزن داری که یال با وزن منفی ندارند، حل می کند و در نهایت با ایجاد درخت کوتاه ترین مسیر، کوتاه ترین مسیر از مبدأ به همهٔ رأس های گراف را به دست می دهد. همچنین می توان از این الگوریتم برای پیدا کردن کوتاه ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاه ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.الگوریتم دیکسترا یکی از الگوریتم های مورد استفاده برای محاسبه کوتاه ترین مسیر تک منبع (single-source shortest path) است و مشابه الگوریتم پریم می باشد در صورتی که گراف یال با وزن منفی داشته باشد، این الگوریتم درست کار نمی کند و می بایست از الگوریتم های دیگر نظیر الگوریتم بلمن-فورد که پیچیدگی زمانی آن ها بیشتر است استفاده کنیم.خط مشی الگوریتم دیکسترا، مشابه با روش حریصانهٔ استفاده شده در الگوریتم پریم برای پیدا کردن زیر درخت فراگیر بهینه است.روند الگوریتم دایکسترا مطابق زیر می باشد:۱- انتخاب راس مبداپیمایش گراف و پیمایش درختهرس آلفا بتاA*B*Beamالگوریتم بلمن–فوردجستجوی ابتدا بهترینجستجوی دوجهتهالگوریتم جستجوی اول سطحD*الگوریتم جستجوی عمق اولجستجوی عمق محدودالگوریتم دیکستراالگوریتم فلوید-وارشالالگوریتم تپه نوردیجستجوی عمق اول عمیق کننده تکراریالگوریتم جانسونLexicographic breadth-firstUniform-costرده:الگوریتم های جستجوجستار وابستهبرنامه ریزی پویاSearch games۲- مجموعهٔ S، شامل رئوس گراف، معین می شود. در شروع، این مجموعه تهی بوده و با پیشرفت الگوریتم، این مجموعه رئوسی که کوتاه ترین مسیر به آن ها یافت شده است را در بر می گیرد.۳- راس مبدأ با اندیس صفر را در داخل S قرار می دهد.۴- برای رئوس خارج از S، اندیسی معادل، طول یال + اندیس راس قبلی، در نظر می گیرد. اگر راس خارج از مجموعه دارای اندیس باشد، اندیس جدید کمترین مقدار از بین اندیس قبلی و طول یال + اندیس راس قبل، می باشد.۵- از رئوس خارج مجموعه، راسی با کمترین اندیس انتخاب شده و به مجموعهٔ S اضافه می گردد.۶- این کار را دوباره از مرحلهٔ ۴ ادامه داده تا راس مقصد وارد مجموعهٔ S شود.در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهندهٔ مسافت بین مبدأ و مقصد می باشد. در غیر این صورت هیچ مسیری بین مبدأ و مقصد موجود نمی باشد.همچنین برای پیدا کردن مسیر می توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهندهٔ راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن رئوس قبلی از مقصد به مبدا، کوتاه ترین مسیر بین دو نقطه نیز یافت می شود.هدفدر حین اجرای الگوریتم دو چیز به طور ضمنی نگهداری می شود. یکی مجموعهٔ {\displaystyle S} از رأس هایی که وزن کوتاه ترین مسیر از مبدأ تا آن ها مشخص شده و دیگری دنبالهٔ {\displaystyle d} که برای هر رأس {\displaystyle v}، مقدار {\displaystyle d_{v}} برابر وزن کوتاه ترین مسیر از مبدأ تا {\displaystyle v} است به شرطی که تمام رأس های این مسیر به جز {\displaystyle v} از رئوس داخل {\displaystyle S} باشند. {\displaystyle S} در ابتدا تهی و مقادیر {\displaystyle d} برای همهٔ رئوس به غیر از مبدأ بی نهایت است و مقدار آن برای مبدأ صفر گذاشته می شود. الگوریتم در هر مرحله رأسی خارج {\displaystyle S} را که {\displaystyle d} برای آن کمترین است انتخاب و به مجموعهٔ {\displaystyle S} اضافه می کند و سپس مقادیر {\displaystyle d} را برای رئوس همسایهٔ آن رأس به روز می نماید. در صورتی که نیاز به تشکیل درخت کوتاه ترین مسیر باشد، الگوریتم می بایست دنبالهٔ {\displaystyle \pi } را که {\displaystyle \pi _{v}} پدر رأس {\displaystyle v} در درخت کوتاه ترین مسیر است، به همراه دنبالهٔ {\displaystyle d} به روز کند.کاربردهااز جمله مهمترین کاربردهای این روش می توان به محاسبهٔ کوتاه ترین فاصلهٔ دو نقطه در یک شهر از طریق راه های زمینی اشاره نمود. برای محاسبهٔ کوتاه ترین مسیر بین دو نقطه باید نقاط مورد نظر در یک نقشه را علامت گذاری کرد و با استفاده از مشخصات نقاط (طول، عرض و ارتفاع) فاصلهٔ دو نقطه را در هر بار عملیات محاسبه نمود. توجه داریم که در ترافیک سرعت خودروها به شدت پایین آمده و این امر می تواند در انتخاب کوتاه ترین مسیر تأثیر گذار باشد چرا که ممکن است بین دو نقطه a,b راه های ۱و۲ موجود باشد که راه ۱ اتوبان و از خارج شهر و راه ۲ از داخل شهر عبور می کند. فرض کنید فاصلهٔ a,b از طریق راه ۱ حدود ۱۰ کیلومتر و از طریق راه ۲ حدود ۷ کیلومتر باشد ولی راه ۲ علی رقم فاصلهٔ کمتر دارای ترافیک سنگین است در نتیجه می توان انتظار داشت که در ساعات شلوغی استفاده از راه ۱ بهتر باشد. از آن جا که اساس محاسبات در این روش بر پایهٔ فاصله بین دو نقطه است می توان کاهش سرعت را با افزایش فواصل هم ارز نمود چرا که اگر رابطهٔ سرعت و فاصله را خطی در نظر بگیریم (D=V.T)تاثیر کاهش سرعت و افزایش مسافت یکسان است. از این رو لازم است تا ضرایب تعدیلی در فواصل بین نقاط ضرب شده و این مسائل را در محاسبات لحاظ کرد. از جمله مهم ترین این ضرایب می توان به ۳ مورد زیر اشاره نمود: ۱-ضریب ترافیک و شلوغی ۲-ضریب عرض معبر ۳-ضریب شیب که نشانگر افت سرعت در سر بالایی هااست. گرچه تعیین این ضرایب برای نقاط مختلف شهر نیازمند کارشناسان متخصص ترافیک و بررسی های آماری دقیق می باشد ولی می توان انتظار داشت که در اکثر موارد این ضرایب بین مقادیر ۱ تا ۲ بسته به شرایط تغییر کنندنمونه و مثالusing System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace DijkstraAlgorithm { class Dijkstra { private static int MinimumDistance(int[] distance, bool[] shortestPathTreeSet, int verticesCount) { int min = int.MaxValue; int minIndex = 0; for (int v = 0; v < verticesCount; ++v) { if (shortestPathTreeSet[v] == false && distance[v] <= min) { min = distance[v]; minIndex = v; } } return minIndex; } private static void Print(int[] distance, int verticesCount) { Console.WriteLine("Vertex Distance from source"); for (int i = 0; i < verticesCount; ++i) Console.WriteLine("{0}\t {1}", i, distance[i]); } public static void DijkstraAlgo(int[,] graph, int source, int verticesCount) { int[] distance = new int[verticesCount]; bool[] shortestPathTreeSet = new bool[verticesCount]; for (int i = 0; i < verticesCount; ++i) { distance[i] = int.MaxValue; shortestPathTreeSet[i] = false; } distance[source] = 0; for (int count = 0; count < verticesCount - 1; ++count) { int u = MinimumDistance(distance, shortestPathTreeSet, verticesCount); shortestPathTreeSet[u] = true; for (int v = 0; v < verticesCount; ++v) if (!shortestPathTreeSet[v] && Convert.ToBoolean(graph[u, v]) && distance[u] != int.MaxValue && distance[u] + graph[u, v] < distance[v]) distance[v] = distance[u] + graph[u, v]; } Print(distance, verticesCount); } static void Main(string[] args) { int[,] graph = { { 0, 6, 0, 0, 0, 0, 0, 9, 0 }, { 6, 0, 9, 0, 0, 0, 0, 11, 0 }, { 0, 9, 0, 5, 0, 6, 0, 0, 2 }, { 0, 0, 5, 0, 9, 16, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 6, 0, 10, 0, 2, 0, 0 }, { 0, 0, 0, 16, 0, 2, 0, 1, 6 }, { 9, 11, 0, 0, 0, 0, 1, 0, 5 }, { 0, 0, 2, 0, 0, 0, 6, 5, 0 } }; DijkstraAlgo(graph, 0, 9); Console.ReadKey(); } } }خروجیVertex Distance from source 0 0 1 6 2 15 3 20 4 22 5 12 6 10 7 9 8 14 جهت استفاده سور رو قرار میدمدانــــــلود سورس دایجسترا

در صورتیکه پست با عنوان الگوریتم دایجسترا :: .NET Developer دارای محتوای نامناسب میباشد بر روی گزینه درخواست حذف مطلب کلیک نمائید تا از دسترس خارج گردد.

× ×