الگوریتم جست وجوی عرضی breath-first search
الگوریتم جست وجوی عرضی breath-first search
در ادامه ی مقالات چندین استراتژی (راهبرد) جست وجو را تحت عنوان جست وجوی ناآگاهانه (یا جست وجوی کور) بررسی خواهیم کرد. منظور از ناآگاهانه این است که این استراتژی ها فقط میتوانند پسین ها را تولید کنند و حالت هدف را از حالت غیر هدف تشخیص دهند. تمام استراتژی های جست وجو با توجه به ترتیب بسط گره ها متمایز میشوند. استراتژی هایی که میدانند یک حالت هدف نسبت به حالت هدف دیگر امیدبخش تر است ، جست وجوی آگاهانه یا جست وجوی ابتکاری نامیده میشوند.
الگوریتم جست وجوی عرضی breath-first search
جست وجوی عرضی ( جست و جوی سطحی) استراتژی ساده ای است که در آن، ابتدا گره ریشه بسط داده میشود، سپس تمام پسین های گره ریشه و سپس پسین های آنها، بسط داده میشوند و الی آخر. بطور کلی تمام گره های موجود در یک عمق درخت بسط داده میشوند، و سپس به گره های موجود در سطح بعدی پرداخته خواهد شد.
جست وجوی عمقی، نمونه ای از الگوریتم کلی "جست وجوی گراف" است که در آن کم عمق ترین گره ی بسط نیافته ، برای بسط انتخاب میشود. این کار براحتی توسط صف FIFO برای مرز انجام میشود. بنابراین گره های جدید (که همیشه عمیق تر از والدهای خود هستند)، به آخر صف میروند و گره های قدیمی که نسبت گره های جدید عمق کمتری دارند، زودتر بسط داده میشوند. در الگوریتم کلی جست وجوی گراف ، پس از تولید هر گره، "آزمون هدف" روی آن انجام میشود، نه وقتی که برای بسط انتخاب شد. توجه کنید که این الگوریتم، با پیروی از قالب کلی جست وجوی گراف، هر مسیر به حالتی را که فعلا در مرز یا مجموعه ی بازدید شده وجود دارد، نادیده میگیرد . به آسانی میتوان دید که هر عمق چنین مسیری، حداقل باید برابر با عمق مسیری باشد که قبلا پیدا شده است. بنابراین جست وجوی عرضی همیشه دارای کم عمق ترین مسیر به هر گره ای در مرز است.
اکنون جست وجوی عرضی را با استفاده از چهار معیار کارایی الگوریتم (کامل بودن، بهینگی، پیچیدگی زمانی، پیچیدگی حافظه ) ارزیابی میکنیم:
این الگوریتم کامل است: اگر کم عمق ترین گره هدف، در عمق متناهی d باشد، جست و جوی عرضی ، آن را پس از تولید تمام گره های کم عمق تر ، پیدا خواهد کرد( به شرطی که ضریب انشعاب b متناهی باشد). به محض تولید گره هدف میدانیم که کم عمق ترین گره هدف است، زیرا تمام گره های کم عمق تر باید قبلا تولید شده باشند و در آزمون هدف با شکست مواجه شده باشند.
اکنون کم عمق ترین گره هدف، الزاما گره هدف بهینه نیست. از نظر تکنیکی جستوجو در صورتی بهینه است که "هزینه مسیر" یک تابع غیر نزولی از عمق این گره باشد. متداول ترین سناریو این است که هزینه تمام فعالیت ها یکسان باشد.
این الگوریتم از نظر زمان و فضا (حافظه) چندان مناسب نیست.
جست وجو در یک درخت یکنواخت را در نظر بگیرید که در آن، هر حالت دارای b عدد پسین است. ریشه ی این درخت جست وجو در سطح اول، b گره را تولید میکند که هر کدام b گره ی دیگر ایجاد میکند و در نتیجه ، در سطح دوم b² گره ایجاد میشود و هر کدام از این گره ها b گره دیگر تولید میکنند و در نتیجه در سطح سوم، b³ گره تولید میشود و الی آخر. اگر جواب در عمق d وجود داشته باشد، در بدترین حالت ، جواب ، آخرین گره تولید شده در آن سطح است. پس تعداد کل گره های تولید شده برابر است با: b+b²+b³+…b^d=O(b^d)
اکنون به پیچیدگی حافظه (فضا) میپردازیم:
برای هر نوع جست وجوی گراف ، که هر گره ی بسط داده شده را در "مجموعه بسط یافته ها" ذخیره میکند پیچیدگی فضا همیشه مضرب b از پیچیدگی زمانی است. مخصوصا برای جست وجوی عرضی در گراف، هر گره ی تولید شده حافظه باقی میماند. در نتیجه تعداد O(b^d-1) گره در مجموعه بسط یافته ها" و O(b^d) گره در مرز قرار دارد، و در نتیجه پیچیدگی فضا برابر با O(b^d) است و نشان میدهد که اندازه ی مرز تاثیر زیادی دارد. استفاده از جست و جوی درختی موجب صرفه جویی در فضا نمیشود و در فضای حالتی با چندین مسیر زاید، استفاده از جست وجوی درختی زمان زیادی را مصرف میکند.
در جست وجوی عرضی، نیاز به حافظه مهمتر از زمان اجرای این الگوریتم است. حل مسئله ی مهمی با عمق جست وجوی 12، به مدت 13 روز طول میکشد. ولی این کار نیاز به یک پتابایت حافظه است که هیچ کامپیوتر شخصی این میزان حافظه را ندارد. استراتژی های دیگر به حافظه کمتری نیاز دارند.
همچنین زمان مسئله ی مهمی است. اگر مسئله در عمق 16 دارای جواب باشد، آنگاه با توجه به فرض های ما 350 سال طول میکشد تا جست وجوی عرضی ، همچنین تمام جستوجو های ناآگاهانه، آن جواب را پیدا کنند. بطور کلی مسئله های جست وجو با پیچیدگی های نمایی، نمیتوانند به روش های ناآگاهانه حل شوند، مگر اینکه نمونه های مسئله بسیار کوچک باشند.
شبه کد الگوریتم جست وجوی عرضی گراف
function BREATH-FIRST-SEARCH (problem) returns a solution, or failure
node <-- a node with STATE = problem.INITIAL-STATE , PATH-COST=0
if problem .GOAL-TEST (node.STATE) then return SOLUTION (node)
frontier <-- a FIFO queue with node as the only element
explored <-- an empty set
loop do
if EMPTY ? (frontier) then return failure
node <-- POP (frontier)
add node.STATE to explored
for each action in problem.ACTIONS(node.STATE) do
child <-- CHILD-NODE (problem, node, action)
if child.STATE is not in explored or frontier then
if problem.GOAL-TEST (child.STATE) then return SOLUTION (child)
frontier <-- INSERT (child, frontier)
سلام امکانش هست سورس جستجوی عرضی را در سی شارپ در سایت قرار بدیدمرسی