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

تست ۱۳۳ طراحی الگوریتم مهندسی ۸۸

ارسال:
  

rad.bahar پرسیده:

تست ۱۳۳ طراحی الگوریتم مهندسی ۸۸

این سوال قبلا هم پرسیدم و لی کسی جواب نداده لطفا جواب بدید

در پیمایش bfs یک گراق جهتدار
چرا برای هر یال cross edge‌، (u,v داریم d[v] <= d[u]+1
d[v] نخستین زمان ملاقات گره v است
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

fatima1537 پاسخ داده:

RE: تست ۱۳۳ مهندسی ۸۸

در گراف جهت دار ممکن است دو راس uوv مجاور باشند و در پیمایش گراف‌، دیر‌تر از بقیه گرهها مورد بازدید قرار بگیرند ولی رابطه پدر یا فرزندی با سایر گرهها نداشته باشد . به عبارتی اگر نتوانیم موقع پیمایش گراف مسیری از یک گره به گره دیگر بیابیم و مجبور باشیم مجددا نقطه شروع جستجو را تعیین کنیم راس متقاطع بوجود می آید
در چنین حالتی (یعنی وقتی که راسی پیدا نکنیم) مجبوریم از همان مسیری که گرهها را تا کنون پیمایش کردیم برگردیم و به این ترتیب زمان خاتمه راس‌ها از آخرین راسی که ملاقات شده به اولین راسی که ملاقات شده مشخص میشود . که مسلما آخرین راس (فرزند) ملاقات شده دارای کمترین زمان و اولین راس ملاقات شده دارای بیشترین زمان خاتمه است
حالا که کل گرههای قابل دسترس پیمایش شد باید مجددا دنبال گرههای باقیمانده بگردیم(همان گره مربوط به یال متقاطع که به علت جهت دار بودن یال قابل دسترس نبود)و دوباره برای این گره هم زمان ملاقات و زمان خاتمه کار ثبت خواهد شد. که مسلما زمان ملاقات این گره بیشتر از زمان گرههای قبلی است
در اینشکل هم به ترتیب گرههای u-v-y-x ملاقات میشوند و بعد چون هنوز یال باقیمانده داریم که هنوز ملاقات نشده مجبوریم از x به عقب برگردیم و اینجا زمان خاتمه x را تعیین میکنیم و بعد زمان خاتمه y (که بیشتر از زمان xاست)و... تا به u میرسیم.و دوباره باید از w شروع کنیم. زمان ملاقات و خاتمه wهم مسلما بیشتر از گرههای قبلی است
_____________________________
من فکر میکنم اگر منظور سئوال زمان خاتمه (ترک) گرهها باشه این رابطه درست درمیاد.


فایل‌(های) پیوست شده

۰
ارسال:
  

fatima1537 پاسخ داده:

تست ۱۳۳ مهندسی ۸۸

به نظر من چون در پیمایش bfs داریم گره هها رو به صورت سطحی ملاقات میکنیم. پس این ملاقات به صورت درخت هست. گرههای Uوv همجوارند وv پدر u است پس طبق همون فرمولی که نوشتید:
زمان ملاقات گرهv کوچکتر یا مساوی است با زمان ملاقات گره u بعلاوه ۱ .

۰
ارسال:
  

rad.bahar پاسخ داده:

تست ۱۳۳ مهندسی ۸۸

با تشکر از توضیحتان منظور از یال cross edge همان یال ضلیبی است
یال ضلیبی یالی است که در پیمایش درخت bfs یا dfs هیجکدام از نودهای u , v پدر یا جد یکدیگد نباشند
فرص کنبد گراف ۳ راسی داریم که گره r پدر u و v باشد و یالی از u به v وحود داشته باشد (گراف جهتدار است) انکاه دو پیمایش bfs زیر برای ان وحود دارد ترتیب پیمایش را از راست به چپ ذر نظر بگیرید
v- u - r
u - v - r
پیمایش اول d[v] <= d[u]+1 را نقض می کند جون u زودتر از v ملاقات شده است
یال (u,v) در هر دو پیمایش bfs یال ضلیبی است

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

ارسال:
  

fatima1537 پاسخ داده:

تست ۱۳۳ مهندسی ۸۸

(۰۳ بهمن ۱۳۹۰ ۱۲:۱۰ ق.ظ)rad.bahar نوشته شده توسط:  پیمایش اول d[v] <= d[u]+1 را نقض می کند جون u زودتر از v ملاقات شده است
علامت => آمده یعنی میتونه اینطور تفسیر بشه: زمان ملاقات u بعلاوه یک = زمان ملاقات v



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال درباره طراحی سایت و جدول ahantell ۰ ۹۹ ۰۲ مرداد ۱۳۹۹ ۱۰:۴۳ ق.ظ
آخرین ارسال: ahantell
Video دانلود رایگان نکته و تست احتمال و آمار مهندسی Farzamm ۰ ۲۶۳ ۱۸ خرداد ۱۳۹۹ ۰۱:۲۹ ب.ظ
آخرین ارسال: Farzamm
  طراحی سایت شرکتی ideasoft98 ۰ ۱۰ ۲۶ اسفند ۱۳۹۸ ۰۲:۵۶ ب.ظ
آخرین ارسال: ideasoft98
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۴۷۲ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t
  تاثیر بودجه در انتخاب شرکت طراحی سایت wone ۱ ۲۰ ۲۳ آبان ۱۳۹۸ ۰۱:۱۴ ب.ظ
آخرین ارسال: xiaomi
  طراحی یک سیستم نورانی هوشمند marvelous ۸ ۸۶۸ ۲۸ مرداد ۱۳۹۸ ۰۳:۵۰ ق.ظ
آخرین ارسال: marvelous
Star ایده طراحی یک وب سایت stabesh ۱ ۶۲۹ ۱۹ مرداد ۱۳۹۸ ۱۱:۱۳ ب.ظ
آخرین ارسال: attarud
  طراحی و چاپ کاتالوگ - اصول مهم و کاربردی طراحی بنر aframehr ۰ ۳۸۹ ۲۵ تیر ۱۳۹۸ ۱۲:۵۳ ق.ظ
آخرین ارسال: aframehr
  طراحی گرافیکی simaakbari ۰ ۵۱۸ ۱۶ خرداد ۱۳۹۸ ۰۴:۵۴ ب.ظ
آخرین ارسال: simaakbari
  دانلود آموزش تصویری کلاس درس تحلیل و طراحی الگوریتم های پیشرفته دانشگاه فردوسی jazana ۱۳ ۵,۱۴۷ ۱۰ خرداد ۱۳۹۸ ۰۵:۴۲ ب.ظ
آخرین ارسال: Valipourh20

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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