از همه ی دوستان به خاطر شکی که پی اومد عذر خواهی میکنم(دلیل اصلی شک حل سوال توسط یکی از اساتید بزگ هست که گویا سهوا اشتباه حل کرده و البته قبل از حل هم تاکید داشت سوال کمی ابهام)(بعد از بررسی بی وقفه،خدایی بی وقفه) فهمیدم ب
ا اینکه استدلال زیر به قوت خودش باقی هست و قائل به تفاوت در بسط گره ها در حالت درختی و گرافی هست،و علاوه بر اون تعداد گره های تولید شده در هر حالت رو بیشتر یا کمتر وارد صف میکنه،
پاسخ همون ۱۳ هستش
-----------------
داخل پرانتز رو بخونید!!(فرض بر این است حل مساله بودن یک گره در زمان باز کردن فرزندان یک گره بررسی میگردد)
گره ها تا عمق ۰ و ۱ و ۲ بسط داده میشوند،تا اینجا قبول و میشود ۱۳ گره، اما محدودیت دیگری که بر سوال اعمال شده را هم دقت کنید،در پرانتز "آزمون هدف" رو ببینید در کجا قرار داده؟!!و البته به این نکته توجه کنید که چه تفاوت هایی در اعمال آزمون هدف بر روی جستجوی گراف و درخت وجود دارد.
فکر کنم همه مون در بند این سفسطه بازی ها گول خوردیم . . . من پاسخ رو گویا باید تشریح کنم.
منبع ویراست سوم ۲۰۱۰ راسل :
نکته ی ظریفی در باره ی الگوریتم کلی جستجوی گراف وجود دارد و آن این است که پس از تولید هر گره"آزمون هدف" بر روی آن انجام میگیرد نه وقتی برای بسط انتخاب شد.توجه کنید که این الگوریتم از قالب کلی جستجوی گراف، هر مسیر به حالتی را که فعلا در مرز یا مجموعه بازدید شده وجود دارد نادیده میگیرد!!!!!
به آسانی میتوان دید که هر عمق چنین مسیری،حداقل باید برابر با عمق مسیری باشد که قبل پیدا شده است بنابر این جستجوی عرضی همیشه دارای کم عمق ترین مسیر به هر گره ای در مرز است.{ اما بحث بر سر اینه که در سوال مورد نظر گراف داده نشده و درخت به ما داده شده}
برای راهنمایی و اینکه ببینم شما چقدر پیگیرید ارجاع میدهم به صفحات ۱۰۴ و ۱۰۵ کتاب منبع.شما حالا برای جستجوی درختی رو در بیارید.
اینجا جنگ بر سر آزمون هدف توسط رفتار های خاص دو الگوریتم در حالت درختی و گرافی هستش،نه تعداد گره های تولید شده!!
و البته تعداد گره های تولید شده هم باشد باز هم استدلال این کتاب کنکوری خام هست.
و در ادامه،جستجو در یک درخت یکنواخت را در نظر بگیرید که در آن هر حالت دارای b عدد مابعد(پسین) است.ریشه ی این درخت جستجو در سطح اول b عدد مابعد تولید میکند که هر کدام b گره ی دیگر ایجاد میکند و در نتیجه در سطح دوم $b^2$ گره ایجاد میکند و به همین ترتیب . . . اکنون اگر فرض کنید جواب در عمق d قرار دارد در بدتیرن حالت داریم :
$b+b^2+....=O(b^d)\: $
اگر الگوریتم،وقتی "آزمون هدف" را بر روی گره ها اجرا کند که برای بسط انتخاب شدند نه وقتی که تولید شدند.تمام گره های موجود در عمق d قبل از پیدا شدن گره ی هدف بسط داده میشوند و در نتیجه پیچیدگی زمانی برابر است با :
$O(b^{d+1})\: $
و اما پیچیدگی حافظه : برای هر نوع جستجوی گراف که هر گره ی بسط داده شده را در "مجموعه ی بسط یافته ها" ذخیره میکند پیچیدگی فضا همیشه مضرب b از پیچیدگی زمانی است.مخصوصا برای جستجوی عرضی در گراف هر گره ی تولید شده در حافظه باقی میماند و در نتیجه تعداد : $O(b^{d-1})\: $ { به منهای یک توجه شود} گره در مجموعه ی بسط یافته ها و
$O(b^d)\: $ گره در مرز {بسیار دقت شود} قرار دارد پس پیچیدگی فضایی برابر
$O(b^d)\: $
و نشان میدهد اندازه ی مرز تاثیر زیادی دارد.
استفاده از جستجوی درختی موجب صرفه جویی در فضا نمیشود و در فضای حالتی با چندین مسیر زاید استفاده از جستجوی درختی زمان زیادی را مصرف میکند.
و اما در سوال ما از جستجوی درختی حرف میزنیم.در جستجوی درختی با آزمون هدف خاصی که دارد.گره های مرزی یک سطح پایین تر از عمیق ترین سطح گره ی هدف هستند.
======
بحث رو اگر بر سر گره های
بسط داده شده بگذاریم.گزینه ی ۱۳ پاسخ هست
باز هم از دوستان عذر خواهی میکنم
----- اما انصافا لذت بردم از این که توی اعماق هوش مصنوعی رفتم.
از دوست بزرگوارم مسعود و دیگر دوستان به سبب صبرشون تشکر میکنم
، با گوشی تلفنتون برام عکس بگیرید وجدانن.ثواب داره ![[تصویر: 394893_BFS.jpg]](https://img.manesht.ir/394893_BFS.jpg)
