تالار گفتمان مانشت

سئوالات الگوریتم رو بهتر از بقیه جواب دادم ولی درکل مفهومی بودند و با بلد بودن شکل کلی الگوریتم و ویژگی های هر الگوریتم راحت حل میشدند
الان سئوالات زیاد یادم نیست
یک سئوال در مورد پیچیدگی زمانی رو من زدم( O(V+H شما چطور زدید؟
سئوالی که در مورد الگوریتم فلوید بود رو نزدم(که میگفت اگر گرافی دارای یال منفی باشه الگوریتم وجود دور رو پیدا میکنه یا نه؟)

یکی از سئوالات هم در مورد جستجوی گراف به طوریکه دورترین گره را بتونیم حتما پیدا کنیم.من زدم پیمایش DFS همون عمقی
(الان صورت سئوال زیاد یادم نیست)

dfs که غلطه میفته توی لوپ!!! ممکنه به ح.اب نرسه

برعکس اگر BFS باشه میفته توی loop _ بقیه گزینه‌ها هم برای پیدا کردن درخت پوشای کمینه بود نه پیدا کردن دورترین گره

(28 بهمن 1390 05:07 ب.ظ)fatima1537 نوشته شده توسط: [ -> ]سئوالات الگوریتم رو بهتر از بقیه جواب دادم ولی درکل مفهومی بودند و با بلد بودن شکل کلی الگوریتم و ویژگی های هر الگوریتم راحت حل میشدند
الان سئوالات زیاد یادم نیست
یک سئوال در مورد پیچیدگی زمانی رو من زدم( O(V+H شما چطور زدید؟
سئوالی که در مورد الگوریتم فلوید بود رو نزدم(که میگفت اگر گرافی دارای یال منفی باشه الگوریتم وجود دور رو پیدا میکنه یا نه؟)

من اینو زدم
vlog v + e

فلوید هم میشد با یک بار اجرای مجدد دور منفی تشخیص داده میشه. من که اشتباهیزدم

اون دورترین راس می‌شه BFS. نزدیک‌ترین فاصله‌ی راس‌ها رو با BFS می‌شه پیدا کرد. در نتیجه وقتی با BFS کل گراف رو گشتیم، آخرین سطحی که بهش رسیدیم راس‌هاش بیشترین «کمترین فاصله» رو دارن نسبت به راس شروع.

1) بلندترین فاصله: BFS
2) کوتاهترین مسیر با یالهای مثبت: E log V

اره bfs جواب رو میده اما این سریع ترین جواب رو میخواست که bfs کندترینه

(28 بهمن 1390 06:13 ب.ظ)martianboy نوشته شده توسط: [ -> ]اون دورترین راس می‌شه BFS. نزدیک‌ترین فاصله‌ی راس‌ها رو با BFS می‌شه پیدا کرد. در نتیجه وقتی با BFS کل گراف رو گشتیم، آخرین سطحی که بهش رسیدیم راس‌هاش بیشترین «کمترین فاصله» رو دارن نسبت به راس شروع.

جواب این سئوال با 2 بار dfs پیدا میشه
در clrs توضیح داده

(28 بهمن 1390 06:45 ب.ظ)k_111 نوشته شده توسط: [ -> ]جواب این سئوال با ۲ بار dfs پیدا میشه
در clrs توضیح داده

یعنی شما هم با من هم عقیده‌اید که جستجوی عمقی بهترینه؟ توی CLRS هم گفته؟

اون سوال در مورد مرتب سازی RADIX SORT ?
A غلط
B درست

من dfs زدم .

من هر دو را زدم درست bکه مطمین بوم ولی a
d+r*s
خب حالا به جای r
log می ذاریم چون هر بار نصف میشه

---

سوال اول چی زدین ؟؟؟؟؟؟؟؟؟؟؟؟؟/

دوستان همه این سوال‌ها تکراری بودن‌، من چک کردم

سوال فلوید گزینه 1

طولانی ترین مسیر bfs

مرتبه زمانی e log v یا v log e

(28 بهمن 1390 05:22 ب.ظ)fatima1537 نوشته شده توسط: [ -> ]یکی از سئوالات هم در مورد جستجوی گراف به طوریکه دورترین گره را بتونیم حتما پیدا کنیم.من زدم پیمایش DFS همون عمقی
(الان صورت سئوال زیاد یادم نیست)

درسته منم همینو زدم،چون گفته بود گراف بدون وزن BFS که نمیشد،دایکسترا م که واسه دورترین جواب نمیده،گزینه دیگشم که پرت بود.