جستجوی A* و BFS مسیر ADE رو در پیش می گیرند و رد میشن
ولی به نظر من جستجوی اول عمق هم مسیر ABCE رو در پیش میگیره
من اشتباه می کنم آیا؟
جواب پوران: گزینه ۳
(۲۸ دى ۱۳۹۲ ۱۲:۴۲ ب.ظ)tayebe68 نوشته شده توسط: جستجوی A* و BFS مسیر ADE رو در پیش می گیرند و رد میشن
ولی به نظر من جستجوی اول عمق هم مسیر ABCE رو در پیش میگیره
من اشتباه می کنم آیا؟
جواب پوران: گزینه ۳
بله با اول عمق هم مسیر ABCE پیدا میشه. اما علاوه بر این مسیر ممکنه الگوریتم اول عمق مسیرهای دیگه مثل ADE و یا ADBCE رو برگردونه که اینا مسیرهای بهینه ای نیستند. به همین دلیل گزینه ۴ هم رد میشه
(۲۸ دى ۱۳۹۲ ۰۶:۲۱ ب.ظ)Somayeh_Y نوشته شده توسط: بله با اول عمق هم مسیر ABCE پیدا میشه. اما علاوه بر این مسیر ممکنه الگوریتم اول عمق مسیرهای دیگه مثل ADE و یا ADBCE رو برگردونه که اینا مسیرهای بهینه ای نیستند. به همین دلیل گزینه ۴ هم رد میشه
البته با توجه به شرط آخر مساله (در همه روشها فرض کنید ترتیب تولید فرزندان یک گره به ترتیب حروف الفباست) جستجوی عمقی فقط مسیر ABCE رو پیدا می کنه
ولی تو کنکور باید بین این دو تا بهترین گزینه رو انتخاب کرد که با توجه به توضیحات شما میشه گزینه DFS رو حذف کرد
(۲۹ دى ۱۳۹۲ ۱۰:۵۸ ق.ظ)tayebe68 نوشته شده توسط:(28 دى ۱۳۹۲ ۰۶:۲۱ ب.ظ)Somayeh_Y نوشته شده توسط: بله با اول عمق هم مسیر ABCE پیدا میشه. اما علاوه بر این مسیر ممکنه الگوریتم اول عمق مسیرهای دیگه مثل ADE و یا ADBCE رو برگردونه که اینا مسیرهای بهینه ای نیستند. به همین دلیل گزینه ۴ هم رد میشه
البته با توجه به شرط آخر مساله (در همه روشها فرض کنید ترتیب تولید فرزندان یک گره به ترتیب حروف الفباست) جستجوی عمقی فقط مسیر ABCE رو پیدا می کنه
ولی تو کنکور باید بین این دو تا بهترین گزینه رو انتخاب کرد که با توجه به توضیحات شما میشه گزینه DFS رو حذف کرد
جستجوی عمقی میفته تو لوپ.مدام از A میره به B میره به A و...
چرا اول سطح نشده ABDCE ؟؟؟
(۰۱ بهمن ۱۳۹۲ ۱۲:۴۳ ب.ظ)zeinab نوشته شده توسط: چرا اول سطح نشده ABDCE ؟؟؟
اینی که شما نوشتید مسیری هست که BFS طی می کنه، یعنی باید این گره ها به همین ترتیب پیمایش بشن تا برسیم به نود هدف
ولی مسیری بهینه میشه ADE
(۲۹ دى ۱۳۹۲ ۰۲:۰۴ ب.ظ)Good! نوشته شده توسط: جستجوی عمقی میفته تو لوپ.مدام از A میره به B میره به A و...
درسته، طبق تعریف DFS باید بیفته تو لوپ
چه نکته ی ظریفی ، تا حالا DFS ای که بیفته تو لوپ ندیده بودم!!!!!
(۰۱ بهمن ۱۳۹۲ ۰۱:۱۱ ب.ظ)tayebe68 نوشته شده توسط:اصلا دلیل اینکه dfs کامل نیست همینه که میفته تو لوپ(در جستجوی درختی).واسه همینم راه حل اینگونه مشکلات میشه استفاده از جستجوی گراف.کتاب راهیان ارشد کامل اینا رو توضیح داده(01 بهمن ۱۳۹۲ ۱۲:۴۳ ب.ظ)zeinab نوشته شده توسط: چرا اول سطح نشده ABDCE ؟؟؟
اینی که شما نوشتید مسیری هست که BFS طی می کنه، یعنی باید این گره ها به همین ترتیب پیمایش بشن تا برسیم به نود هدف
ولی مسیری بهینه میشه ADE
(۲۹ دى ۱۳۹۲ ۰۲:۰۴ ب.ظ)Good! نوشته شده توسط: جستجوی عمقی میفته تو لوپ.مدام از A میره به B میره به A و...
درسته، طبق تعریف DFS باید بیفته تو لوپ
چه نکته ی ظریفی ، تا حالا DFS ای که بیفته تو لوپ ندیده بودم!!!!!
(۰۱ بهمن ۱۳۹۲ ۰۱:۱۱ ب.ظ)tayebe68 نوشته شده توسط: [quote='zeinab' pid='239239' dateline='1390292021']
چرا اول سطح نشده ABDCE ؟؟؟
اینی که شما نوشتید مسیری هست که BFS طی می کنه، یعنی باید این گره ها به همین ترتیب پیمایش بشن تا برسیم به نود هدف
ولی مسیری بهینه میشه ADE
ببخشید متوجه نشدم
این مسیر بهینه چجوری بدست اومده؟!!
(۰۱ بهمن ۱۳۹۲ ۰۲:۳۸ ب.ظ)Good! نوشته شده توسط:(29 دى ۱۳۹۲ ۰۲:۰۴ ب.ظ)Good! نوشته شده توسط: جستجوی عمقی میفته تو لوپ.مدام از A میره به B میره به A و...
اصلا دلیل اینکه dfs کامل نیست همینه که میفته تو لوپ(در جستجوی درختی).واسه همینم راه حل اینگونه مشکلات میشه استفاده از جستجوی گراف.کتاب راهیان ارشد کامل اینا رو توضیح داده
اگر قانون پیمایش اینطوری باشه پس پیمایش BFS باید بشه این:
ABDACDAEBDE
و همینطور تا بینهایت ادامه خواهد داشت ؟ ولی باهاش به جواب میرسیم
درسته ؟؟
(۰۲ بهمن ۱۳۹۲ ۰۱:۱۷ ب.ظ)tayebe68 نوشته شده توسط:ABDACDAEC...(01 بهمن ۱۳۹۲ ۰۲:۳۸ ب.ظ)Good! نوشته شده توسط:(29 دى ۱۳۹۲ ۰۲:۰۴ ب.ظ)Good! نوشته شده توسط: جستجوی عمقی میفته تو لوپ.مدام از A میره به B میره به A و...
اصلا دلیل اینکه dfs کامل نیست همینه که میفته تو لوپ(در جستجوی درختی).واسه همینم راه حل اینگونه مشکلات میشه استفاده از جستجوی گراف.کتاب راهیان ارشد کامل اینا رو توضیح داده
اگر قانون پیمایش اینطوری باشه پس پیمایش BFS باید بشه این:
ABDACDAEBDE
و همینطور تا بینهایت ادامه خواهد داشت ؟ ولی باهاش به جواب میرسیم
درسته ؟؟
تا بینهایت که نه وقتی بخواهیم E رو بسط بدیم میفهمیم هدفه و به جواب میرسیم.اگه فاکتور انشعاب بینهایت باشه تا بینهایت ادامه پیدا میکنه
اینا جستجوی درختیه.جستجوی درختی گره های تکراری داره اما جستجوی گراف دیگه گره های تکراری رو بسط نمیده