بررسی الگوریتم دایجسترا در پیمایش گراف

info

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

بررسی الگوریتم دایجسترا در پیمایش گراف

  • اصلی
  • تعداد صفحات: 39
  • نوع فونت: نازنین 14
  • فرمت پروژه: ورد 2003
  • زبان: فارسی
  • تاریخ بارگذاری: 19/11/91

بررسی الگوریتم دایجسترا در پیمایش گراف

 

چکیده :
 
در نظریه گراف، الگوریتم دیکسترا یکی از الگوریتم‌های پیمایش گراف است که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دِیْکْسْترا در سال ۱۹۵۹ ارایه شد. این الگوریتم یکی از الگوریتم‌های پیمایش گراف است که مسئلهٔ کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همهٔ رأس‌های گراف را به دست می‌دهد. همچنین می‌توان از این الگوریتم برای پیدا کردن کوتاه‌ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاه‌ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.
 
 سایر عناوین موجود
 
مقدمه :3
نام گذاری4
مسئله یافتن کوتاهترین مسیر4
الگوریتم‌ها6
الگوریتم دیکسترا:6
الگوریتم بلمن-فورد:6
الگوریتم جستجوی *A:6
الگوریتم فلوید-وارشال:6
الگوریتم جانسون:6
نظریهٔ بی نظمی‌ها:6
کاربردها7
مسائل مرتبط7
درخت کوتاه‌ترین مسیر8
مسئلهٔ درخت کوتاه‌ترین مسیر9
روند9
این الگوریتم چگونه کار می‌کند؟10
الگوریتم11
پیاده‌سازی11
پیچیدگی زمانی12
کاربردها12
مسیریابی (Routing)13
درباره الگوریتم دیکسترا (دایجسترا)13
شبه کد الگوریتم دیکسترا در زیر ارائه شده است14
توضیح بیشتر14
مرتبه اجرایی الگوریتم دیکسترا15
Router  :15
مثال16
الگوریتم Dijkstra16
الگوریتمهای DV18
پیمایش گراف18
جستجوی اول سطح18
جستجوی اول عمق21
ویژگی‌های جستجوی اول عمق23
پیمایش گراف24
جستجوی اول عمق24
جستجوی اول سطح25
درخت پوشای حداقل27
الگوریتم کروسکال28
روند الگوریتم دیکسترا مطابق زیر می باشد :29
به عنوان مثال، گراف زیر را در نظر بگیرید:30
الگوریتم A*:31
الگوریتم بلمن فورد :( Bellman-Ford )34
به مثال زیر توجه کنید:34
الگوریتم فلوید وارشال :( Floyd-Warshall )35
الگوریتم های ژنتیک (GA) :36
 
نتیجه گیری:
در این پژوهش به بررسی الگوریتم دایجسترا در جهت یافتن کوتاه ترین مسیر پیمایش در گراف های وزن دار پرداخته شد ، روش های کلاسیک و مدرن برای تعیین بهترین مسیر را می توان به صورت زیر مقایسه نمود: روش های کلاسیک از قوانین قطعی برای حرکت به نقطه ی بعد در فضای جستجو استفاده می کنند، در حالی که GA از روش های احتمال بهره می گیرد. روش های کلاسیک جستجو را از یک نقطه شروع کرده و سپس مرحله به مرحله به نقطه ی بعد می روند، در حالی که GA برای جستجو از تعداد زیادی نقطه ی پراکنده ، کار را شروع کرده و به صورت موازی کلیه ی فضای جستجو را بررسی می کند.
 
منابع و ماخذ :
منابع فارسی :
 1 -  تننباوم، آرون ام. ساختمان داده ها در C. ترجمه عین اله جعفرنژاد قمی. انتشارات جهاد دانشگاهی مشهد.
2 -  جباریه، علیرضا. ساختمان داده ها. ترجمه و تالیف. انتشارات جهان نو.
3 -  کافمن، الیوت ب. توربو پاسکال. ترجمه فرنگیس شاکری، لیدا جواهر قلم و سهیل صالحی. انشارات باغانی
4 -  مقسمی، حمیدرضا. درس و کنکور ساختمان داده ها. انتشارات گسترش علوم پایه.
5 -  لیپ شوتز، سیمور. اصول ساختمان داد ها. ترجمه حسین ابراهیم زاده قلزم. انتشارات دانشگاه هرمزگان.
6 -  هورویتز، آلیس و ساهنی، سارتج . ساختمان داده ها در پاسکال. ترجمه ملیحه مهدی پور و سهیل صالحی. انتشارات بخشوده
 
منابع انگلیسی :
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, ۲۰۰۱. ISBN ۰-۲۶۲-۰۳۲۹۳-۷.
Udi Manber. Introduction to Algorithms — A Creative Approach. MIT Press and Addison-Wesley, ۱۹۸۹. ISBN ۰-۲۰۱-۱۲۰۳۷-۲.
Donald E. Knuth. The Art Of Computer Programming Vol ۱., Third Edition. Addison-Wesley, ۱۹۹۷. ISBN ۰-۲۰۱-۸۹۶۸۳-۴.
Douglas B. West. Introduction to Graph Theory, Second Edition. Prentice Hall, ۲۰۰۱. ISBN 0-13-014400-2.

نظرات کاربران درباره بررسی الگوریتم دایجسترا در پیمایش گراف

نظری در مورد این محصول توسط کاربران ارسال نگردیده است.
اولین نفری باشید که در مورد بررسی الگوریتم دایجسترا در پیمایش گراف نظر می دهد.

ارسال نظر درباره بررسی الگوریتم دایجسترا در پیمایش گراف

لطفا توجه داشته باشید که ایمیل شما منتشر نخواهد شد.
 
کد امنیتی *
captcha
قیمت: 70,000 ریال
کد محصول 520055