زمان کنونی: ۰۲ مهر ۱۳۹۹, ۰۹:۱۱ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

الگوریتم دیکسترا

ارسال:
  

hamed_k2 پرسیده:

الگوریتم دیکسترا

سلام دوستان عزیز من دوتا سئوال درسی داشتم در مورد الگوریتم دیکسترا اگه واقعا میتونید کمک کنید پایان ترم باید تمرینات رو تحویل بدم با تشکر.
.
.
۱/الگوریتم دیکسترا را طوری اصلاح کنید که ببیند ایا گراف جهت دار, چرخه دارد یا خیر.الگوریتم خود را تحلیل کرده نتایج را با استفاده از نماد مرتبه نشان دهید؟
.
.
۲/ایا الگوریتم دیکسترا را می توان برای یافتن کوتاه ترین مسیر در گرافی با وزن های منفی به کار گرفت؟ برای پاسخ خود دلیل بیاورید.

۰
ارسال:
  

Mohammad-A پاسخ داده:

الگوریتم دیکسترا

برای سوال اول٬ فکر میکنم میشه اینطور گفت که:
ما در الگوریتم دیکسترا٬ یک مجموعه‌ی یال‌های گزیده شده داریم و مجموعه‌ی گره‌هایی که دیده نشدند.
زمانیکه در این الگوریتم Extract_Min رو انجام می‌دیم٬ (فکر میکنم) پیش از اون٬ باید بررسی کنیم که آیا اجتماع یال جدید با مجموعه‌ی قبلی٬ دارای چرخه هست یا خیر. بنابراین باید یک بررسی بین همه‌ی یال‌هایی که انتخاب شدند٬ داشته باشیم. درباره‌ی پیچیدگی زمانی اون میشه بحث کرد.

۲. خیر! چون این الگوریتم یک الگوریتم حریصانه هست٬ در هر مرحله٬ کورکورانه کم‌ترین هزینه رو انتخاب می‌کنه و کاری به یال‌های بعدی نداره. فرضاً اگر مسیری از یک گره تا گره‌ی دیگه با وجود یال منفی (با واسط گره‌ی دیگری) وجود داشته باشه٬ این الگوریتم٬ الزاماً راه حل بهینه رو پیدا نمی‌کنه. (الزاماً پیدا نمی‌کنه٬ ممکنه پیدا کنه ولی روی این موارد٬ ضعیف هست.)

۰
ارسال:
  

hamed_k2 پاسخ داده:

الگوریتم دیکسترا

(۱۲ دى ۱۳۹۰ ۱۰:۵۳ ب.ظ)mam نوشته شده توسط:  برای سوال اول٬ فکر میکنم میشه اینطور گفت که:
ما در الگوریتم دیکسترا٬ یک مجموعه‌ی یال‌های گزیده شده داریم و مجموعه‌ی گره‌هایی که دیده نشدند.
زمانیکه در این الگوریتم Extract_Min رو انجام می‌دیم٬ (فکر میکنم) پیش از اون٬ باید بررسی کنیم که آیا اجتماع یال جدید با مجموعه‌ی قبلی٬ دارای چرخه هست یا خیر. بنابراین باید یک بررسی بین همه‌ی یال‌هایی که انتخاب شدند٬ داشته باشیم. درباره‌ی پیچیدگی زمانی اون میشه بحث کرد.
از بابت جواب سئوال دو دست شما درد نکنه تقریبا به دردم خورد
در مورد سئوال اول میتونید الگوریتم اصلاح شده اش رو بنویسید؟



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  ۱۷۱ نرم افزار و ۱۹۸ الگوریتم - شبانه الگوریتم دانشگاه تهران axarsu ۱ ۸۴۸ ۰۸ شهریور ۱۳۹۵ ۰۸:۳۶ ب.ظ
آخرین ارسال: majidgeek
  ۲۴۲ الگوریتم ،۳۷۱ نرم. الگوریتم برم یا نرم افزار؟ azamcheraghi ۱۱ ۲,۰۱۸ ۰۳ تیر ۱۳۹۵ ۱۱:۳۸ ق.ظ
آخرین ارسال: azamcheraghi
  مشکل در الگوریتم جایگزینی (الگوریتم ساعت ) araz22 ۶ ۲,۱۹۱ ۱۹ مهر ۱۳۹۴ ۱۰:۲۴ ب.ظ
آخرین ارسال: so@
  ۸ الگوریتم ۱۲ نرم افزار ۱۵ علوم -- نرم افزار شریف گرایش الگوریتم ahrmb ۲ ۱,۵۹۳ ۰۸ مهر ۱۳۹۴ ۰۶:۴۳ ب.ظ
آخرین ارسال: ahrmb
  ۱۴۷ نرم افزار و ۱۱۶ الگوریتم - الگوریتم روزانه تهران slaf83 ۱۴ ۳,۳۳۰ ۲۴ شهریور ۱۳۹۴ ۱۱:۴۵ ق.ظ
آخرین ارسال: slaf83
  ۱۸۰ نرم ۱۷۰ الگوریتم الگوریتم تهران-شبانه t.mehr ۶ ۱,۴۵۹ ۲۰ شهریور ۱۳۹۴ ۰۴:۰۴ ب.ظ
آخرین ارسال: tondar.sal
  ۱۲۱ نرم افزار ۱۴۵ الگوریتم - الگوریتم تهران روزانه ali blhj ۲۳ ۳,۶۳۱ ۱۵ شهریور ۱۳۹۴ ۱۰:۵۹ ق.ظ
آخرین ارسال: ali blhj
  درخواست کد الگوریتم زمانبدی FIFOیا سایر الگوریتم های زمان بندی در سی شارپ sepideh1373 ۲ ۱,۲۴۸ ۰۳ اردیبهشت ۱۳۹۴ ۰۶:۱۳ ب.ظ
آخرین ارسال: one hacker alone
  الگوریتم EQL مبتنی بر الگوریتم ژنتیک shabnamtt ۰ ۷۲۶ ۲۷ اسفند ۱۳۹۳ ۱۱:۴۴ ق.ظ
آخرین ارسال: shabnamtt
  الگوریتم دیکسترا alwaysPeace ۴ ۱,۰۳۳ ۲۲ آذر ۱۳۹۳ ۱۱:۱۷ ب.ظ
آخرین ارسال: alwaysPeace

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close