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

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

ارسال:
  

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پاسخنامه تشریحی طراحی الگوریتم موسسه ماهان برای درس طراحی الگوریتم کنکور ۹۱ مهندسی MSsoftware ۸ ۶,۸۸۳ ۰۴ بهمن ۱۳۹۱ ۰۱:۰۲ ق.ظ
آخرین ارسال: fa_karoon
  تست ۳۸ طراحی الگوریتم سال ۸۵ پشتکار ۱۰ ۳,۲۵۴ ۲۹ دى ۱۳۹۱ ۱۰:۲۴ ب.ظ
آخرین ارسال: csharpisatechnology
  تست ۴۰ طراحی الگوریتم نرم افزار ۸۶ reyhaneh64 ۲ ۱,۸۵۹ ۲۹ دى ۱۳۹۱ ۰۳:۱۲ ب.ظ
آخرین ارسال: csharpisatechnology
  بررسی سوالات طراحی الگوریتم ۹۱ مهندسی کامپیوتر -گرایش هوش fatima1537 ۸۶ ۳۴,۹۳۴ ۲۰ اسفند ۱۳۹۰ ۱۰:۴۰ ب.ظ
آخرین ارسال: anyone
  تست (مرتبه اجرایی ) طراحی الگوریتم کنکور ۹۱ vijay ۷ ۳,۵۷۳ ۱۵ اسفند ۱۳۹۰ ۰۶:۳۴ ب.ظ
آخرین ارسال: لهمشد
  بررسی سوالات طراحی الگوریتم ۹۱ فناوری اطلاعات uniquegirl ۲۸ ۸,۷۶۷ ۰۷ اسفند ۱۳۹۰ ۱۲:۲۶ ق.ظ
آخرین ارسال: rotbe
  تست (گراف) طراحی الگوریتم آی تی کنکور ۹۱ vijay ۴ ۲,۹۳۵ ۰۱ اسفند ۱۳۹۰ ۰۷:۴۰ ق.ظ
آخرین ارسال: MSZ
  تست مرتبه اجرایی طراحی الگوریتم کنکور ۹۱ vijay ۲ ۲,۶۶۶ ۳۰ بهمن ۱۳۹۰ ۰۲:۵۴ ب.ظ
آخرین ارسال: arixooo
  تست ۳۲ طراحی الگوریتم سال ۹۰ Anahita.R ۳ ۲,۳۳۸ ۲۶ بهمن ۱۳۹۰ ۱۲:۳۶ ب.ظ
آخرین ارسال: atharrashno
  تست (درخت) طراحی الگوریتم آی تی سال ۸۸ netsupport ۲ ۱,۷۸۳ ۲۴ بهمن ۱۳۹۰ ۰۷:۳۳ ب.ظ
آخرین ارسال: homa

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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