-۱
subtitle
ارسال: #۱
بررسی سوالات طراحی الگوریتم ۹۱ مهندسی کامپیوتر -گرایش هوش
سئوالات الگوریتم رو بهتر از بقیه جواب دادم ولی درکل مفهومی بودند و با بلد بودن شکل کلی الگوریتم و ویژگی های هر الگوریتم راحت حل میشدند
الان سئوالات زیاد یادم نیست
یک سئوال در مورد پیچیدگی زمانی رو من زدم( O(V+H شما چطور زدید؟
سئوالی که در مورد الگوریتم فلوید بود رو نزدم(که میگفت اگر گرافی دارای یال منفی باشه الگوریتم وجود دور رو پیدا میکنه یا نه؟)
الان سئوالات زیاد یادم نیست
یک سئوال در مورد پیچیدگی زمانی رو من زدم( O(V+H شما چطور زدید؟
سئوالی که در مورد الگوریتم فلوید بود رو نزدم(که میگفت اگر گرافی دارای یال منفی باشه الگوریتم وجود دور رو پیدا میکنه یا نه؟)
۲
ارسال: #۲
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
دوستانی که علاقه وافر به CLRS دارن ، اینکه فلوید میتونه دور منفی رو تشخیص بده یکی از تمرینهای این کتاب هست . تعجب میکنم میگید نیست . در ضمن توی کتابای تست هم این مورد چند بار اومده و من از کتاب پارسه و پوران و سپاهان این بحث رو دنبال کردم . کلام آخر رو به عهده جناب کرمن میسپرم که نشون میده فلوید دور منفی رو تشخیص میده ( متاسفانه همه کتابام رو جمع کردم که بگم چه صفحه ای رو بخونید ، کم کم دارم پیر میشم از دست کنکور! ) :
Here are two ways to detect negative-weight cycles:
۱/ Check the main-diagonal entries of the result matrix for a negative value. There
is a negative weight cycle if and only if d(n)
ii < 0 for some vertex i :
• d(n)
ii is a path weight from i to itself; so if it is negative, there is a path from i
to itself (i.e., a cycle), with negative weight.
• If there is a negative-weight cycle, consider the one with the fewest vertices.
• If it has just one vertex, then some wii < 0, so dii starts out negative, and
since d values are never increased, it is also negative when the algorithm
terminates.
• If it has at least two vertices, let k be the highest-numbered vertex in the
cycle, and let i be some other vertex in the cycle. d(k−۱)
ik and d(k−۱)
ki have
correct shortest-path weights, because they are not based on negativeweight
cycles. (Neither d(k−۱)
ik nor d(k−۱)
ki can include k as an intermediate
vertex, and i and k are on the negative-weight cycle with the fewest
vertices.) Since i k i is a negative-weight cycle, the sum of
those two weights is negative, so d(k)
ii will be set to a negative value.
Since d values are never increased, it is also negative when the algorithm
terminates.
In fact, it sufÞces to check whether d(n−۱)
ii < 0 for some vertex i . Heres why.
A negative-weight cycle containing vertex i either contains vertex n or it does
not. If it does not, then clearly d(n−۱)
ii < 0. If the negative-weight cycle contains
vertex n, then consider d(n−۱)
nn . This value must be negative, since the cycle,
starting and ending at vertex n, does not include vertex n as an intermediate
vertex.
۲/ Alternatively, one could just run the normal FLOYD-WARSHALL algorithm one
extra iteration to see if any of the d values change. If there are negative cycles,
then some shortest-path cost will be cheaper. If there are no such cycles, then
no d values will change because the algorithm gives the correct shortest paths.
۱/ Check the main-diagonal entries of the result matrix for a negative value. There
is a negative weight cycle if and only if d(n)
ii < 0 for some vertex i :
• d(n)
ii is a path weight from i to itself; so if it is negative, there is a path from i
to itself (i.e., a cycle), with negative weight.
• If there is a negative-weight cycle, consider the one with the fewest vertices.
• If it has just one vertex, then some wii < 0, so dii starts out negative, and
since d values are never increased, it is also negative when the algorithm
terminates.
• If it has at least two vertices, let k be the highest-numbered vertex in the
cycle, and let i be some other vertex in the cycle. d(k−۱)
ik and d(k−۱)
ki have
correct shortest-path weights, because they are not based on negativeweight
cycles. (Neither d(k−۱)
ik nor d(k−۱)
ki can include k as an intermediate
vertex, and i and k are on the negative-weight cycle with the fewest
vertices.) Since i k i is a negative-weight cycle, the sum of
those two weights is negative, so d(k)
ii will be set to a negative value.
Since d values are never increased, it is also negative when the algorithm
terminates.
In fact, it sufÞces to check whether d(n−۱)
ii < 0 for some vertex i . Heres why.
A negative-weight cycle containing vertex i either contains vertex n or it does
not. If it does not, then clearly d(n−۱)
ii < 0. If the negative-weight cycle contains
vertex n, then consider d(n−۱)
nn . This value must be negative, since the cycle,
starting and ending at vertex n, does not include vertex n as an intermediate
vertex.
۲/ Alternatively, one could just run the normal FLOYD-WARSHALL algorithm one
extra iteration to see if any of the d values change. If there are negative cycles,
then some shortest-path cost will be cheaper. If there are no such cycles, then
no d values will change because the algorithm gives the correct shortest paths.
ارسال: #۳
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۱۰ اسفند ۱۳۹۰ ۰۸:۲۸ ب.ظ)Masoud05 نوشته شده توسط: دوستانی که علاقه وافر به CLRS دارن ، اینکه فلوید میتونه دور منفی رو تشخیص بده یکی از تمرینهای این کتاب هست . تعجب میکنم میگید نیست . در ضمن توی کتابای تست هم این مورد چند بار اومده و من از کتاب پارسه و پوران و سپاهان این بحث رو دنبال کردم . کلام آخر رو به عهده جناب کرمن میسپرم که نشون میده فلوید دور منفی رو تشخیص میده ( متاسفانه همه کتابام رو جمع کردم که بگم چه صفحه ای رو بخونید ، کم کم دارم پیر میشم از دست کنکور! ) :
.........
بابا بخدا منم می دونم دور منفی رو تشخیص می ده خیلی خوبم می دونم اون سوال سال ۸۴ ۲۰۰۰ بار خوندم ولی صورت سوال گفته فاصله هر راس از خودش صفره این معنیش این نیست که هزینه طوقه صفره بلکه یعنی تمام دور هامون صفره در غیر این صورت سوال غلط بیان شده. و گرنه این سوال ابتدایی بود من ترم ۵ هم یاد داشتم تمام این فرمول های clrs و پوران و اینا رو خوندم خوب می دونم ولی صحبت من یه چیزه دیگه است.
۱
۱
ارسال: #۵
الگوریتم(تخصصی گرایش هوش)
اون دورترین راس میشه BFS. نزدیکترین فاصله‌ی راس‌ها رو با BFS میشه پیدا کرد. در نتیجه وقتی با BFS کل گراف رو گشتیم، آخرین سطحی که بهش رسیدیم راس‌هاش بیشترین «کمترین فاصله» رو دارن نسبت به راس شروع.
ارسال: #۶
RE: الگوریتم(تخصصی گرایش هوش)
(۲۸ بهمن ۱۳۹۰ ۰۶:۱۳ ب.ظ)martianboy نوشته شده توسط: اون دورترین راس میشه BFS. نزدیکترین فاصله‌ی راس‌ها رو با BFS میشه پیدا کرد. در نتیجه وقتی با BFS کل گراف رو گشتیم، آخرین سطحی که بهش رسیدیم راس‌هاش بیشترین «کمترین فاصله» رو دارن نسبت به راس شروع.
جواب این سئوال با ۲ بار dfs پیدا میشه
در clrs توضیح داده
۱
ارسال: #۷
الگوریتم(تخصصی گرایش هوش)
در مورد اون سوال BFS و DFS من که خیلی مطمئن زدم BFS مخصوصا وقتی یال ها وزن ندارن و یعنی تعداد اعمال مهمه!
نمی دونم چطور می گید DFS میشه.
نمی دونم چطور می گید DFS میشه.
۱
۱
ارسال: #۹
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
همه گزینه ها طولانی ترین مسیرو میدن. اما به نظر من سریع ترین الگوریتم ترتیب توپولوژیکی ایه
۱
ارسال: #۱۰
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
عجب بحثی شده این بلند ترین مسیر ! حیف که همه کتابام رو جمع کردم و بسته بندی کردم برای سال دیگه والا یه بحث طولانی با دوستان میکردم . اما بنظرم احتمال bfs بودن زیاده . اما در آخر نظر طراح مهمه نه هیچ کس دیگه 
۱
ارسال: #۱۱
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
سلام به همگی، من فقط میخوام اینو بگم که بعضی از دوستان این سوالو با مساله ی یافتن طولانی ترین مسیر اشتباه گرفتن. در صورتی که سوال کلا یه چیز دیگه ایه! تو صورت سوال گفته :
" دورترین راس از یک راس داده شده ی v ، در یک گراف بدون وزن، راسی است که کوتاهترین فاصله ی آن تا v بیشترین باشد"
یعنی میخوایم دورترین راس از v رو ،" با تعریف بالا "، پیدا کنیم. خوب با یه بار BFS طول "کوتاهترین مسیرها" از v به همه ی راسای دیگه بدست میاد. و اونی که "طول کوتاهترین مسیرش" از همه بیشتره میشه جواب.
DFS و TOPOLOGICAL_SORT هیچ کدوم نمیتونن "کوتاهترین فاصله از یک راس داده شده" رو پیدا کنن .
دایجسترا میتونه پیدا کنه ولی چون گراف بی وزنه باید از BFS استفاده کرد.
" دورترین راس از یک راس داده شده ی v ، در یک گراف بدون وزن، راسی است که کوتاهترین فاصله ی آن تا v بیشترین باشد"
یعنی میخوایم دورترین راس از v رو ،" با تعریف بالا "، پیدا کنیم. خوب با یه بار BFS طول "کوتاهترین مسیرها" از v به همه ی راسای دیگه بدست میاد. و اونی که "طول کوتاهترین مسیرش" از همه بیشتره میشه جواب.
DFS و TOPOLOGICAL_SORT هیچ کدوم نمیتونن "کوتاهترین فاصله از یک راس داده شده" رو پیدا کنن .
دایجسترا میتونه پیدا کنه ولی چون گراف بی وزنه باید از BFS استفاده کرد.
۱
ارسال: #۱۲
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
dfs تو لوپ میفته و این سوال تکراری بود و سوال اول طراحی الگوریتم میشد گزینه یک یعنیn-1
ارسال: #۱۳
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
۱
۰
ارسال: #۱۵
RE: الگوریتم(تخصصی گرایش هوش)
۱) بلندترین فاصله: BFS
۲) کوتاهترین مسیر با یالهای مثبت: E log V
۲) کوتاهترین مسیر با یالهای مثبت: E log V
۰
ارسال: #۱۶
الگوریتم(تخصصی گرایش هوش)
اره bfs جواب رو میده اما این سریع ترین جواب رو میخواست که bfs کندترینه
۰
۰
ارسال: #۱۹
الگوریتم(تخصصی گرایش هوش)
من هر دو را زدم درست bکه مطمین بوم ولی a
d+r*s
خب حالا به جای r
log می ذاریم چون هر بار نصف میشه
سوال اول چی زدین ؟؟؟؟؟؟؟؟؟؟؟؟؟/
d+r*s
خب حالا به جای r
log می ذاریم چون هر بار نصف میشه
سوال اول چی زدین ؟؟؟؟؟؟؟؟؟؟؟؟؟/
۰
ارسال: #۲۰
الگوریتم(تخصصی گرایش هوش)
دوستان همه این سوال‌ها تکراری بودن، من چک کردم
سوال فلوید گزینه ۱
طولانی ترین مسیر bfs
مرتبه زمانی e log v یا v log e
سوال فلوید گزینه ۱
طولانی ترین مسیر bfs
مرتبه زمانی e log v یا v log e
ارسال: #۲۱
RE: الگوریتم(تخصصی گرایش هوش)
۰
ارسال: #۲۲
RE: الگوریتم(تخصصی گرایش هوش)
طبق صحبت های بچه های مانشت و دوستانم بعد از آزمون تا حالا این نتایج بدست آمده( نظر خودم نیست بلکه نظر بچه هاست )
سوالات با توجه عکس بالا هست:
۱۱۰‌: بعضیا میگفتن ۱ و بعضیا ۲
۱۱۱: بین ۱و ۳
۱۱۲: ۱ بنظرم همین درسته
۱۱۳: ۱ و ۲
۱۱۴: ۳ یا ۴ من فکر میکنم ۴ باشه اما مطمئن نیستم
۱۱۵: احتمال داره هر ۲ نادرست باشه اما راجع به این سوال بحث جدی نشده!
سوالات با توجه عکس بالا هست:
۱۱۰‌: بعضیا میگفتن ۱ و بعضیا ۲
۱۱۱: بین ۱و ۳
۱۱۲: ۱ بنظرم همین درسته
۱۱۳: ۱ و ۲
۱۱۴: ۳ یا ۴ من فکر میکنم ۴ باشه اما مطمئن نیستم
۱۱۵: احتمال داره هر ۲ نادرست باشه اما راجع به این سوال بحث جدی نشده!
ارسال: #۲۳
RE: الگوریتم(تخصصی گرایش هوش)
(۲۹ بهمن ۱۳۹۰ ۱۱:۴۱ ق.ظ)Masoud05 نوشته شده توسط: طبق صحبت های بچه های مانشت و دوستانم بعد از آزمون تا حالا این نتایج بدست آمده( نظر خودم نیست بلکه نظر بچه هاست )
سوالات با توجه عکس بالا هست:
۱۱۰‌: بعضیا میگفتن ۱ و بعضیا ۲
۱۱۱: بین ۱و ۳
۱۱۲: ۱ بنظرم همین درسته
۱۱۳: ۱ و ۲
۱۱۴: ۳ یا ۴ من فکر میکنم ۴ باشه اما مطمئن نیستم
۱۱۵: احتمال داره هر ۲ نادرست باشه اما راجع به این سوال بحث جدی نشده!
۱۱۰: بین ۱ و ۴ ولی من حساب کردم ۴
۱۱۱: ۱
۱۱۲: ۱
۱۱۳: -
۱۱۴: ۳ (DFS) شما تو ویکی پدیا هم بری نوشته اینو
۱۱۵: ۱مقدار بحث برانگیزه (:
۰
ارسال: #۲۴
الگوریتم(تخصصی گرایش هوش)
۱۱۰- ۴ (من با محاسبه و رسم درخت به دست آوردم)
۱۱۱- ۳ (مطمئن نیستم)
۱۱۲- بدون جواب
۱۱۳ - ۲ (چون یه آرایه کشیدم و با چند لیست حلقوی تست کردم دیدم مثل مرتب جستجوی دودویی است)
۱۱۴- ۳
۱۱۵- بدون جواب
۱۱۱- ۳ (مطمئن نیستم)
۱۱۲- بدون جواب
۱۱۳ - ۲ (چون یه آرایه کشیدم و با چند لیست حلقوی تست کردم دیدم مثل مرتب جستجوی دودویی است)
۱۱۴- ۳
۱۱۵- بدون جواب
ارسال: #۲۵
RE: الگوریتم(تخصصی گرایش هوش)
(۲۹ بهمن ۱۳۹۰ ۰۵:۲۴ ب.ظ)fatima1537 نوشته شده توسط: ۱۱۰- ۴ (من با محاسبه و رسم درخت به دست آوردم)-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-
۱۱۱- ۳ (مطمئن نیستم)
۱۱۲- بدون جواب
۱۱۳ - ۲ (چون یه آرایه کشیدم و با چند لیست حلقوی تست کردم دیدم مثل مرتب جستجوی دودویی است)
۱۱۴- ۳
۱۱۵- بدون جواب
در مورد سوال ۱۱۱ من مطمئنم ۳ نمیشه.اگه DAG بود سه درست بود ولی اینجا میشه VlogV+E.این بهترین زمان برای الگوریتم دیکسترا(که اینجا همین الگوریتمو می خواد) است.این زمانو با هیپ فیبوناچی بدست میاد.اگه تو تشخیص الگوریتم مورد نیاز اشتباه نکرده باشم مطمئنم که VlogV+E میشه.
در مورد سوال ۱۱۴ من زدم BFS یه چیزی یادم بود از اینکه بهترین الگوریتم برای بدست اوردن دورترین راس از راس شروعرو میده.مطمئن نیستم.تو جزوهام میگردم اگه چیزی پیدا کردم اینجا میذارم
۰
۰
ارسال: #۲۷
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
کی گفته مرتب سازی توپولوژیکی با دوباره DFS به دست میاد؟
من این سوال رو مرتب سازی توپولوژیکی زدم به دلایل زیر
اولا مرتب سازی توپولوژیکی به این ترتیبه که یک بار DFS می رید و سپس بر گره ها رو بر اساس زمان خروج به صورت نزولی مرتب می کنید.
حالا دورترین نقطه رو می شه با این مساله به دست اورد.
دقیقا در فصل ۲۲ کتاب CLRS مثالی رو در خصوص تقدم ارائه می ده تحت عنوان مرتب سازی موضعی یا توپولوژیی که از مرتبه تتای V+E است.
همان مثالی که در پوشیدن لباس کدوم رو اول می پوشیم کدوم رو آخر
اینجا هم دورترین نقاط رو می شه همینجوری به دست اورد
دوستان نظر بدن
من این سوال رو مرتب سازی توپولوژیکی زدم به دلایل زیر
اولا مرتب سازی توپولوژیکی به این ترتیبه که یک بار DFS می رید و سپس بر گره ها رو بر اساس زمان خروج به صورت نزولی مرتب می کنید.
حالا دورترین نقطه رو می شه با این مساله به دست اورد.
دقیقا در فصل ۲۲ کتاب CLRS مثالی رو در خصوص تقدم ارائه می ده تحت عنوان مرتب سازی موضعی یا توپولوژیی که از مرتبه تتای V+E است.
همان مثالی که در پوشیدن لباس کدوم رو اول می پوشیم کدوم رو آخر
اینجا هم دورترین نقاط رو می شه همینجوری به دست اورد
دوستان نظر بدن
ارسال: #۲۸
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
ارسال: #۲۹
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۳۰ بهمن ۱۳۹۰ ۰۲:۲۵ ب.ظ)باد نوشته شده توسط: کی گفته مرتب سازی توپولوژیکی با دوباره DFS به دست میاد؟من نمی دونم چرا این قدر بحث سر این سوال شده!!! من که واقعا به نظر BFS میشه.
من این سوال رو مرتب سازی توپولوژیکی زدم به دلایل زیر
اولا مرتب سازی توپولوژیکی به این ترتیبه که یک بار DFS می رید و سپس بر گره ها رو بر اساس زمان خروج به صورت نزولی مرتب می کنید.
حالا دورترین نقطه رو می شه با این مساله به دست اورد.
دقیقا در فصل ۲۲ کتاب CLRS مثالی رو در خصوص تقدم ارائه می ده تحت عنوان مرتب سازی موضعی یا توپولوژیی که از مرتبه تتای V+E است.
همان مثالی که در پوشیدن لباس کدوم رو اول می پوشیم کدوم رو آخر
اینجا هم دورترین نقاط رو می شه همینجوری به دست اورد
دوستان نظر بدن
اولا مرتب سازی توپولوژکی می تونه همون DFS باشه که فقط آخر تابعش یه چاپ بزارید. (از کتاب مقسمی) یه جورایی معادل هستن.
بعد این که داره میگه گراف بدون وزن. خوب ما از همون راسی می خوایم BFS می زنیم حواب به دست میاد. پیچیدگی پیمایش BFS
DFS هم یکیه. به نظر من BFS میشه. حتی اگه کلید چیز دیگه ای رو بگه. درسته که اون ملاک هست ولی اگرچه و اما! :دی
دست کم الان نظرم این هست! :دی
۰
ارسال: #۳۰
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
۱۱۰- n-1 می شه
۱۱۱- شما با DFS یا BFS می تونید کوتاهترین مسیر رو هم پیدا کنید. |v|+|E|
۱۱۲- وجود یا عدم وجود دور منفی. طبق گفته CLRS
۱۱۳- نزدم
۱۱۴- بحث سر اینه که گراف بدون وزنه-ممکنه ناهمبند/همبند باشه. DFS
۱۱۵- a=نادرست , b=درست
۱۱۱- شما با DFS یا BFS می تونید کوتاهترین مسیر رو هم پیدا کنید. |v|+|E|
۱۱۲- وجود یا عدم وجود دور منفی. طبق گفته CLRS
۱۱۳- نزدم
۱۱۴- بحث سر اینه که گراف بدون وزنه-ممکنه ناهمبند/همبند باشه. DFS
۱۱۵- a=نادرست , b=درست
ارسال: #۳۱
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۳۰ بهمن ۱۳۹۰ ۰۲:۳۸ ب.ظ)fazel-d نوشته شده توسط: ۱۱۰- n-1 می شه
۱۱۱- شما با DFS یا BFS می تونید کوتاهترین مسیر رو هم پیدا کنید. |v|+|E|
۱۱۲- وجود یا عدم وجود دور منفی. طبق گفته CLRS
۱۱۳- نزدم
۱۱۴- بحث سر اینه که گراف بدون وزنه-ممکنه ناهمبند/همبند باشه. DFS
۱۱۵- a=نادرست , b=درست
برای سوال ۱۱۱
دوست عزیز من، کوتاه ترین مسیر از لحاظ تعداد یال با وزن مساوی یا گراف بدون وزن را می توان با BFS بدست آورد در غیر این صورت باید از الگوریتم های مثل دایکسترا استفاده کرد
ارسال: #۳۲
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
۰
ارسال: #۳۳
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
به نظر من:
۱-۱۱۰
۳-۱۱ (تویه clrs کاملا گفته شده اگه یالها بین ۱ تا w باشد میشه e+vlogw یا حتی vw+e در نتیجه چون w=c و ثابته میشه e+v
۱-۱۱۲
۴-۱۱۴
۲-۱۱۵
۱-۱۱۰
۳-۱۱ (تویه clrs کاملا گفته شده اگه یالها بین ۱ تا w باشد میشه e+vlogw یا حتی vw+e در نتیجه چون w=c و ثابته میشه e+v
۱-۱۱۲
۴-۱۱۴
۲-۱۱۵
۰
ارسال: #۳۴
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
در مورد سوال ۱۱۲ فلوید
سوال گفته فرض کنید در هر مرحله فاصله هر گره با خودش صفر می باشد الگوریتم فلوید بعد از n-1 مرحله متوقف میشه پس در مرحله اخر عناصر قطر اصلی صفر می باشد ،نمی توانیم دور منفی تشخیص دهیم پس اگر دور منفی نداشته باشیم ولی یال منفی داشته باشیم درست کار نمی کند پس گزینه ۴ درسته طبق دفترچه A
سوال ۱۱۴
جزوه طراحی تابستان سیدجوادی همین مسئله رو با bfs حل کرده ،تمرین clrs هم هست که تمرینات bfs می باشه
۲۲/۲-۷
The diameter of a tree T = (V, E) is given by
max
u,v∈V
δ(u, v) ;
سوال گفته فرض کنید در هر مرحله فاصله هر گره با خودش صفر می باشد الگوریتم فلوید بعد از n-1 مرحله متوقف میشه پس در مرحله اخر عناصر قطر اصلی صفر می باشد ،نمی توانیم دور منفی تشخیص دهیم پس اگر دور منفی نداشته باشیم ولی یال منفی داشته باشیم درست کار نمی کند پس گزینه ۴ درسته طبق دفترچه A
سوال ۱۱۴
جزوه طراحی تابستان سیدجوادی همین مسئله رو با bfs حل کرده ،تمرین clrs هم هست که تمرینات bfs می باشه
۲۲/۲-۷
The diameter of a tree T = (V, E) is given by
max
u,v∈V
δ(u, v) ;
ارسال: #۳۵
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۳۰ بهمن ۱۳۹۰ ۰۶:۵۷ ب.ظ)tarang نوشته شده توسط: در مورد سوال ۱۱۲ فلوید
سوال گفته فرض کنید در هر مرحله فاصله هر گره با خودش صفر می باشد الگوریتم فلوید بعد از n-1 مرحله متوقف میشه پس در مرحله اخر عناصر قطر اصلی صفر می باشد ،نمی توانیم دور منفی تشخیص دهیم پس اگر دور منفی نداشته باشیم ولی یال منفی داشته باشیم درست کار نمی کند پس گزینه ۴ درسته طبق دفترچه A
سوال ۱۱۴
جزوه طراحی تابستان سیدجوادی همین مسئله رو با bfs حل کرده ،تمرین clrs هم هست که تمرینات bfs می باشه
۲۲/۲-۷
The diameter of a tree T = (V, E) is given by
max
u,v∈V
δ(u, v) ;
۱/ فلوید با یال منفی کار می کنه
۲/ وقتی دور منفی داشته باشیم خوب طبیعتا مساله جوابش منفی بینهایت هست.
۳/ الگوریتم فلوید می تونه با تکرار خودش، دور منفی رو تشخیص بده. یعنی در تکرار بعدی اگه فاصله ها کمتر شده دور منفی داره.
۰
ارسال: #۳۶
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
من خودم فکر میکنم که ۱۱۴ bfs هست اما نظرات دوستان هم حاوی نکاتی هست که نمیشه ازش چشم پوشید . درباره تست ۱۱۲ فکر میکنم۱ صحیح باشه .۱۱۳ هم احتمال زیاد ۲ صحیح هست اما تا حالا ندیدم کسی بتونه دقیق اثبات کنه ( همه اینا طبق دفترچه A ) هست
۱۱۵ فکر میکنم هر دو غلطه اما نمیتونم اثبات کنم.
۱۱۵ فکر میکنم هر دو غلطه اما نمیتونم اثبات کنم.
۰
ارسال: #۳۷
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
For sparse graphs, that is, graphs with far fewer than O( | V | 2) edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a binary heap, pairing heap, or Fibonacci heap as a priority queue to implement extracting minimum efficiently. With a binary heap, the algorithm requires O(( | E | + | V | )log | V | ) time (which is dominated by O( | E | log | V | ), assuming the graph is connected). To avoid O(|V|) look-up in decrease-key step on a vanilla binary heap, it is necessary to maintain a supplementary index mapping each vertex to the heap's index (and keep it up to date as priority queue Q changes), making it take only O(log | V | ) time instead. The Fibonacci heap improves this to O( | E | + | V | log | V | ).
کارا (Efficiency) اشاره شده به Binary Heap و در نهایت O( | E | log | V | )
کارا (Efficiency) اشاره شده به Binary Heap و در نهایت O( | E | log | V | )
۰
ارسال: #۳۸
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
بچه ها من کلید ماهان رو دیدم.طبق دفترچه ی A جوابا اینجور بود:
۱۱۰ رو فقط یادم نیست :دی
۱۱۱ شده ۳
۱۱۲ شده ۱
۱۱۳ شده ۲
۱۱۴ شده ۴
۱۱۵ شده ۲
امیدوارم همه رو درست زده باشید.من که ۳ تا جواب دادم که طبق این کلید درست بودن!
۱۱۰ رو فقط یادم نیست :دی
۱۱۱ شده ۳
۱۱۲ شده ۱
۱۱۳ شده ۲
۱۱۴ شده ۴
۱۱۵ شده ۲
امیدوارم همه رو درست زده باشید.من که ۳ تا جواب دادم که طبق این کلید درست بودن!
ارسال: #۳۹
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۰۳ اسفند ۱۳۹۰ ۰۱:۵۱ ق.ظ)fardin_ss نوشته شده توسط: بچه ها من کلید ماهان رو دیدم.طبق دفترچه ی A جوابا اینجور بود:
۱۱۰ رو فقط یادم نیست :دی
۱۱۱ شده ۳
۱۱۲ شده ۱
۱۱۳ شده ۲
۱۱۴ شده ۴
۱۱۵ شده ۲
امیدوارم همه رو درست زده باشید.من که ۳ تا جواب دادم که طبق این کلید درست بودن!
منم قبول دارم همه رو ، ۱۱۰ هم فکر کنم ۱ درست باشه(ولی مطمئن نیستم) ، درسته که مدرسان غلط زیاد داره اما اونم ۱۱۰ رو یک اعلام کرده. کلا رویه سوالای لگوریتم زیاد بحث نیست به جز سوال۹۸ که واقعا موندم مدرسان چطور به nlogk رسیدن
، چون سخت نبود ، بلکه نا آشنا بود و جوابا مشخص (دیگه مثل سوالای نظریه و سیستم عامل جای بحث و نظر دادن یا توضیح اضافی نیست !)
ارسال: #۴۰
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۰۳ اسفند ۱۳۹۰ ۰۱:۵۱ ق.ظ)fardin_ss نوشته شده توسط: بچه ها من کلید ماهان رو دیدم.طبق دفترچه ی A جوابا اینجور بود:
۱۱۰ رو فقط یادم نیست :دی
۱۱۱ شده ۳
۱۱۲ شده ۱
۱۱۳ شده ۲
۱۱۴ شده ۴
۱۱۵ شده ۲
امیدوارم همه رو درست زده باشید.من که ۳ تا جواب دادم که طبق این کلید درست بودن!
در کتاب Design Analisys and Algorithm، قسمت DFS با شکل و توضیح نوشته که:
هر دو الگوریتم BFSو DFS مرتبه یکسانی برای بدست آوردن Longest Path دارند اما الگوریتم DFS دارای تقریب بهتری نسبت به BFS است
باید اون صفحه رو اسکن کنم براتون تا منظورمو بفهمید (: در ضمن موقعی میشه از جستجوی توپولوژیکال استفاده کرد که گراف DAG باشد
۰
ارسال: #۴۱
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
DFS gives a better approximation of the longest path than BFS
این جمله میگه dfs زمان تخمینی بهتری نسبت به bfs میده شاید الگوریتم دیکسترا هم بتونه دورترین راس رو پیدا کنه ولی چون مسئله گفته کدام مناسب تر و سریعتر است به نظر من dfs گزینه مناسب تری هست
این جمله میگه dfs زمان تخمینی بهتری نسبت به bfs میده شاید الگوریتم دیکسترا هم بتونه دورترین راس رو پیدا کنه ولی چون مسئله گفته کدام مناسب تر و سریعتر است به نظر من dfs گزینه مناسب تری هست
(۰۳ اسفند ۱۳۹۰ ۰۵:۰۰ ب.ظ)payman نوشته شده توسط: DFS و TOPOLOGICAL_SORT هیچ کدوم نمیتونن "کوتاهترین فاصله از یک راس داده شده" رو پیدا کنن .از لحاظ زمانی هم سریعتر هست؟
دایجسترا میتونه پیدا کنه ولی چون گراف بی وزنه باید از BFS استفاده کرد.
۰
ارسال: #۴۲
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
جواب اون سوال که می گین dfs تو لوپ می افته چی میشه ؟؟؟؟؟؟؟؟؟؟؟؟؟؟/
۰
ارسال: #۴۳
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
من که DFS زدم و به جواب خودم مطمئن بودم ولی جواب سنجش قابل باور نبود
الان چند تا متن لاتین هم سرچ کردم و بازهم همین برداشت رو دارم
توی این متون میگه :
BFSزمان بیشتری رو برای رسیدن به آخرین سطح داره ولی DFS سریعتر به هدف میرسه
صورت سئوال میگه : "دور ترین راس گراف بدون وزن" یعنی هیچ عددی روی یالها نیست و بازهم به این معنی هست که دورترین راس یعنی راسی که تعداد یالهای بیشتری رو باید پیمایش کنیم تا به اون برسیم
و درضمن گفته "کدام روش سریعتر و مناسب تر است؟"
خب مسلما باید : اولا در زمان کمتری پیدا بشه ثانیا توی لوپ نیفته ثالثا یالهای بیشتری طی بشه
ولی "سطحی"اول میاد همه نزدیکترین گرهها رو جستجو میکنه بعد یک سطح میاد پایین تر و همینطور الی آخر . که دراین صورت حداکثر زمان صرف میشه . چون باید تمام رئوس رو طی کنه .
من کتاب روهم که خوندم نوشته:" DFS کوتاهترین مسیرهای تک مبدا را محاسبه میکند"
دایکسترا هم که نمیتونه باشه چون مرتبه زمانش زیاده(( o(v^2 )
الان چند تا متن لاتین هم سرچ کردم و بازهم همین برداشت رو دارم
توی این متون میگه :
BFSزمان بیشتری رو برای رسیدن به آخرین سطح داره ولی DFS سریعتر به هدف میرسه
صورت سئوال میگه : "دور ترین راس گراف بدون وزن" یعنی هیچ عددی روی یالها نیست و بازهم به این معنی هست که دورترین راس یعنی راسی که تعداد یالهای بیشتری رو باید پیمایش کنیم تا به اون برسیم
و درضمن گفته "کدام روش سریعتر و مناسب تر است؟"
خب مسلما باید : اولا در زمان کمتری پیدا بشه ثانیا توی لوپ نیفته ثالثا یالهای بیشتری طی بشه
ولی "سطحی"اول میاد همه نزدیکترین گرهها رو جستجو میکنه بعد یک سطح میاد پایین تر و همینطور الی آخر . که دراین صورت حداکثر زمان صرف میشه . چون باید تمام رئوس رو طی کنه .
من کتاب روهم که خوندم نوشته:" DFS کوتاهترین مسیرهای تک مبدا را محاسبه میکند"
دایکسترا هم که نمیتونه باشه چون مرتبه زمانش زیاده(( o(v^2 )
ارسال: #۴۴
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۰۸ اسفند ۱۳۹۰ ۰۶:۱۶ ب.ظ)fatima1537 نوشته شده توسط: من که DFS زدم و به جواب خودم مطمئن بودم ولی جواب سنجش قابل باور نبود
الان چند تا متن لاتین هم سرچ کردم و بازهم همین برداشت رو دارم
توی این متون میگه :
BFSزمان بیشتری رو برای رسیدن به آخرین سطح داره ولی DFS سریعتر به هدف میرسه
صورت سئوال میگه : "دور ترین راس گراف بدون وزن" یعنی هیچ عددی روی یالها نیست و بازهم به این معنی هست که دورترین راس یعنی راسی که تعداد یالهای بیشتری رو باید پیمایش کنیم تا به اون برسیم
و درضمن گفته "کدام روش سریعتر و مناسب تر است؟"
خب مسلما باید : اولا در زمان کمتری پیدا بشه ثانیا توی لوپ نیفته ثالثا یالهای بیشتری طی بشه
ولی "سطحی"اول میاد همه نزدیکترین گرهها رو جستجو میکنه بعد یک سطح میاد پایین تر و همینطور الی آخر . که دراین صورت حداکثر زمان صرف میشه . چون باید تمام رئوس رو طی کنه .
من کتاب روهم که خوندم نوشته:" DFS کوتاهترین مسیرهای تک مبدا را محاسبه میکند"
دایکسترا هم که نمیتونه باشه چون مرتبه زمانش زیاده(( o(v^2 )
باید این نکات رو هم توی اعتراض به کلید آورد .
۰
ارسال: #۴۵
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
سوال ۱۱۲ الگوریتم فلوید
کسی می تونه برام توضیح بده چطور میشه دور منفی رو تشخیص دهیم چون من یک جا خوندم گفته بود اگر یکی از عناصر قطر اصلی منفه بشه انوقت دور منفی داریم با فرض سوال این اتفاق نمیفته
کسی می تونه برام توضیح بده چطور میشه دور منفی رو تشخیص دهیم چون من یک جا خوندم گفته بود اگر یکی از عناصر قطر اصلی منفه بشه انوقت دور منفی داریم با فرض سوال این اتفاق نمیفته
ارسال: #۴۶
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۰۹ اسفند ۱۳۹۰ ۱۱:۲۰ ب.ظ)tarang نوشته شده توسط: سوال ۱۱۲ الگوریتم فلوید
کسی می تونه برام توضیح بده چطور میشه دور منفی رو تشخیص دهیم چون من یک جا خوندم گفته بود اگر یکی از عناصر قطر اصلی منفه بشه انوقت دور منفی داریم با فرض سوال این اتفاق نمیفته
میدونم، شما از کتاب پارسه خوندید . اما این تست تکراری بوده و از دل تست های سال های قبل در اومده . مطمئن باش که دور منفی رو میتونه تشخیص بده
۰
ارسال: #۴۷
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
درسته ، فرضیات صورت سئوال اصلا خوب بیان نشده بود.یا حداقل گزینه های درستی انتخاب نکرده بودند
۰
ارسال: #۴۸
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
کرمن گفته به دو طریق میشه دور منفی را تشخیص دهیم ۱-اگر عناصر قطر اصلی یکیشون منفی بشه که با فرض سوال این اتفاق اصلا اتفاق نمیفته ۲-دوباره الگوریتم را اجرا کنیم اگر مقادیر ماتریس d کمتر شدند دور منفی داریم در مورد روش دوم هم با یک مثال که پیوست کردم این اتفاق نمیفته چون هر چقدر اجرا کنیم ماتریس d مقادیرش ثابته
۰
ارسال: #۵۰
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۱۴ اسفند ۱۳۹۰ ۰۶:۲۴ ب.ظ)abcd1234 نوشته شده توسط: سوالای ۱۱۰ و ۱۱۳ رو کسی میتونه توضیح بده؟
سوال ۱۱۰
سوال راحتی بود که، چون توی گزینه ها [logn-1] و [logn+1] و از این چیزا نداشت و کافی بود ببینی از چه مرتبه ایه
هر بار مساله رو نصف میکنه و بدون هزینه ترکیب میکنه (T(n)=2*T(n/2
توی این جور مسائل درنظر بگیرید اگه اندازه آرایه دو برابر بشه، هزینه ۱ مقایسه بیشتر میشه و این خاصیت شگفت انگیز لگاریتمه
______________________
سوال ۱۱۳
سوال قشنگیه، از نظر ذهنی میتونستید تشخیص بدید همون خاصیت لگاریتم صادقه؛ و با یک مقایسه نصف آرایه حذف میشه
اما توضیح دقیق تر یک الگوریتم پیشنهادی:
می دونیم: برای پیدا کردن کوچکترین عنصر در یک آرایه حلقوی مرتب، باید جایی که آرایه ناگهان خیلی بزرگ میشه رو پیدا کنیم
مثال صورت سوال: [۵۰,۴۰,۳۰,۲۰,۱۰,۸۰,۷۰,۶۰]
عنصر اول رو تو متغیر a میریزیم (این کار هزینه نداره)
عنصر وسط رو چک میکنیم؛ اینجا ۲۰
آرایه از ۵۰ به ۲۰ رسیده و جهش ناگهانی رو نداشته پس حالا نصف اول آرایه رو کنار میذاریم
دقت داشته باشید بعد از این بزرگ شدن ناگهانی، بزرگترین عضو آرایه هست و تمام عناصر بعد از اون جهش هم از همه ی عناصر قبل از جهش بزرگترند، پس اگه اون جهش قبل از عنصر وسط بود، حالا این عنصر وسط بزرگ تر از عنصر اول بود
به محض این که متوجه شدید با هزینه ۱ میشه نصف آرایه رو حذف کرد بزنید logn
۰
ارسال: #۵۱
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
ممنون ازتوضیحاتتون.
سوال ۱۱۰ رو موافقم ولی چرا در نهایت n-1 میشه؟ مگه با این توضیحات lgn نیست؟
اما در مورد سوال ۱۱۳ هنوز نمیتونم قبول کنم. آخه lgn وقتیه که آرایه مرتب باشه، فکر نمیکنم به این راحتی نصف آرایه قابل حذف باشه... مثلا آرایه رو اینطوری در نظر بگیرین : ۸۰-۷۰-۶۰-۵۰-۴۰-۳۰-۲۰-۱۰-۹۰ چطوری با مقایسه ۹۰ و ۴۰ میشه نصف آرایه رو حذف کرد؟
سوال ۱۱۰ رو موافقم ولی چرا در نهایت n-1 میشه؟ مگه با این توضیحات lgn نیست؟
اما در مورد سوال ۱۱۳ هنوز نمیتونم قبول کنم. آخه lgn وقتیه که آرایه مرتب باشه، فکر نمیکنم به این راحتی نصف آرایه قابل حذف باشه... مثلا آرایه رو اینطوری در نظر بگیرین : ۸۰-۷۰-۶۰-۵۰-۴۰-۳۰-۲۰-۱۰-۹۰ چطوری با مقایسه ۹۰ و ۴۰ میشه نصف آرایه رو حذف کرد؟
ارسال: #۵۲
RE: طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
(۱۹ اسفند ۱۳۹۰ ۰۶:۴۱ ب.ظ)abcd1234 نوشته شده توسط: ممنون ازتوضیحاتتون.خواهش میکنم؛ امیدوارم توضیحاتم مفید باشه؛ البته اگه مثل سوال ۱۱۰ غلط نباشه!
سوال ۱۱۰ رو موافقم ولی چرا در نهایت n-1 میشه؟ مگه با این توضیحات lgn نیست؟
اما در مورد سوال ۱۱۳ هنوز نمیتونم قبول کنم. آخه lgn وقتیه که آرایه مرتب باشه، فکر نمیکنم به این راحتی نصف آرایه قابل حذف باشه... مثلا آرایه رو اینطوری در نظر بگیرین : ۸۰-۷۰-۶۰-۵۰-۴۰-۳۰-۲۰-۱۰-۹۰ چطوری با مقایسه ۹۰ و ۴۰ میشه نصف آرایه رو حذف کرد؟
____________
سوال ۱۱۰ رو من کلا اشتباه گرفتم
T(n)=2T(n/2)+1 ==> O(n
من سر جلسه هم اشتباهی گزینه ۴ رو زدم
اما این که چرا n-1 نه n
۱) جواب رابطه بازگشتی T(n)=2T(n/2)+1 با شرط T(2)=1 هست n-1
۲) با مثال برای آرایه ۴ عنصری: [a b c d] میشه ۳ رو بدست آورد
[a b] <>[c d]
[a]<>[b]
[c]<>[d]
______________
سوال ۱۱۳
آرایه ای که مثال زدم نزولی بود
آرایه ای که شما مثال زدید صعودی مرتب هست و ما دنبال جایی هستیم که کوچک شدن ناگهانی وجود دارد
a=90
۴۰ کوچکتر از a درنتیجه از کوچک شدن ناگهانی گذشته ایم و نیمه دوم رو کنار میذاریم
۲۰ کوچکتر از a در نتیجه از کوچک شدن ناگهانی گذشته ایم ...
دقت کن همه ی اعداد قبل از "کوچک شدن ناگهانی"، بزرگترند از همه ی اعداد بعد از "کوچک شدن ناگهانی" و این دلیل درست کار کردن الگوریتم توی همه ی مثال هاست
نظرت چیه؟
۰
ارسال: #۵۳
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
برای سوال سوال ۱۱۰ با یه مثال میشه به جواب n-1 رسید .موفق به ارسال تصویر مثال براتون نشدم( برای ارسال فایل ۱۱کیلو بایتیم به مانشت با پیام حجیم بودن فایل مواجه شدم نمی دونم مشکل از کجاست)
برای سوال ۱۱۳ راه حل من اینه که تو لیست دنبال کوچکترین یا بزرگترین عنصر بگردیم که زمان هر دوشون یکیه و logn شماره خونه عنصر iام =(i+اینکدکس کوچکترین عنصر) که زمان پیدا کردنش = ۱
زمان کل عملیات = logn+1 ===logn
برای سوال ۱۱۳ راه حل من اینه که تو لیست دنبال کوچکترین یا بزرگترین عنصر بگردیم که زمان هر دوشون یکیه و logn شماره خونه عنصر iام =(i+اینکدکس کوچکترین عنصر) که زمان پیدا کردنش = ۱
زمان کل عملیات = logn+1 ===logn
۰
ارسال: #۵۴
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
۰
ارسال: #۵۵
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
بازهم تشکر
سوال ۱۱۰ رو متوجه شدم، مشکلم سوال ۱۱۳ ست. با نظر anyone هم موافق نیستم آخه وقتی شماره خونه عنصر iام رو بدونیم که دیگه نمیشه جستجو!
سوال ۱۱۰ رو متوجه شدم، مشکلم سوال ۱۱۳ ست. با نظر anyone هم موافق نیستم آخه وقتی شماره خونه عنصر iام رو بدونیم که دیگه نمیشه جستجو!
۰
ارسال: #۵۶
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
فرض کنید دنبال سومین کوچکترین عضو می گردیم
در حالت عادی در لیست مرتب :وقتی عنصر اول(کوچکترین عنصر) تو خونه اول باشه پس سومین کوچکترین عنصر هم تو خونه سومه
اما در این حالت (صف حلقوی) نمی دونیم عنصر اول در کجا قرار داره پس باید مکان این عنصر رو پیدا کنیم(با هزینه logn)
با پیدا کردن مکان این عنصر حالا نسبت به محل این عنصر می تونیم محل عضو i ام رو تشخیص بدیم یعنی شماره عنصری که می خوایم رو با محل این عنصر (کوچکترین عنصر)جمع کنیم البته چون صف حلقوی هست باید عدد حاصل بر اندازه کل صف تقسیم بشه.
هزینه جستجو بر هزینه سایر عملیات غالبه پس هزینه کل= logn
در حالت عادی در لیست مرتب :وقتی عنصر اول(کوچکترین عنصر) تو خونه اول باشه پس سومین کوچکترین عنصر هم تو خونه سومه
اما در این حالت (صف حلقوی) نمی دونیم عنصر اول در کجا قرار داره پس باید مکان این عنصر رو پیدا کنیم(با هزینه logn)
با پیدا کردن مکان این عنصر حالا نسبت به محل این عنصر می تونیم محل عضو i ام رو تشخیص بدیم یعنی شماره عنصری که می خوایم رو با محل این عنصر (کوچکترین عنصر)جمع کنیم البته چون صف حلقوی هست باید عدد حاصل بر اندازه کل صف تقسیم بشه.
هزینه جستجو بر هزینه سایر عملیات غالبه پس هزینه کل= logn
-۱
ارسال: #۵۷
الگوریتم(تخصصی گرایش هوش)
یکی از سئوالات هم در مورد جستجوی گراف به طوریکه دورترین گره را بتونیم حتما پیدا کنیم.من زدم پیمایش DFS همون عمقی
(الان صورت سئوال زیاد یادم نیست)
(الان صورت سئوال زیاد یادم نیست)
ارسال: #۵۸
RE: الگوریتم(تخصصی گرایش هوش)
(۲۸ بهمن ۱۳۹۰ ۰۵:۲۲ ب.ظ)fatima1537 نوشته شده توسط: یکی از سئوالات هم در مورد جستجوی گراف به طوریکه دورترین گره را بتونیم حتما پیدا کنیم.من زدم پیمایش DFS همون عمقی
(الان صورت سئوال زیاد یادم نیست)
درسته منم همینو زدم،چون گفته بود گراف بدون وزن BFS که نمیشد،دایکسترا م که واسه دورترین جواب نمیده،گزینه دیگشم که پرت بود.
-۱
ارسال: #۵۹
الگوریتم(تخصصی گرایش هوش)
برعکس اگر BFS باشه میفته توی loop _ بقیه گزینه‌ها هم برای پیدا کردن درخت پوشای کمینه بود نه پیدا کردن دورترین گره
-۱
ارسال: #۶۰
RE: الگوریتم(تخصصی گرایش هوش)
(۲۸ بهمن ۱۳۹۰ ۰۵:۰۷ ب.ظ)fatima1537 نوشته شده توسط: سئوالات الگوریتم رو بهتر از بقیه جواب دادم ولی درکل مفهومی بودند و با بلد بودن شکل کلی الگوریتم و ویژگی های هر الگوریتم راحت حل میشدندمن اینو زدم
الان سئوالات زیاد یادم نیست
یک سئوال در مورد پیچیدگی زمانی رو من زدم( O(V+H شما چطور زدید؟
سئوالی که در مورد الگوریتم فلوید بود رو نزدم(که میگفت اگر گرافی دارای یال منفی باشه الگوریتم وجود دور رو پیدا میکنه یا نه؟)
vlog v + e
فلوید هم میشد با یک بار اجرای مجدد دور منفی تشخیص داده میشه. من که اشتباهیزدم
-۱
ارسال: #۶۱
الگوریتم(تخصصی گرایش هوش)
-۱
-۱
ارسال: #۶۳
طراحی الگوریتم ۹۱ مهندسی کامپیوتر - هوش
سریعترین روش دو بار bfs زدن برای یافتن طولانی ترین است بدون شک .
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close