advertise laitec sharif univercity استخراج بیت کوین با کامپیوتر استخراج بیت کوین با کامپیوتر
سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

3000 تومان
دانلود سورس پروژه TSP با الگوریتم مورچگان Ants

دانلود سورس پروژه TSP با الگوریتم مورچگان Ants

4800 تومان
دانلود پروژه وب سایت هتل با HTML و ASP.NET

دانلود پروژه وب سایت هتل با HTML و ASP.NET

4900 تومان
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

45000 تومان
دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

3000 تومان

الگوریتم جست وجوی عرضی breath-first search

جست وجوی عرضی ( جست و جوی سطحی) یکی از استراتژی های جست وجوی ناآگاهانه است که در آن، ابتدا گره ریشه بسط داده میشود، سپس تمام پسین های گره ریشه و سپس پسین های آنها، بسط داده میشوند و الی آخر...
الگوریتم جست وجوی عرضی 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)

 



1
نظرات
  • user avatar زهرا:
    ۱۳:۰۳:۱۷ __ ۱۳۹۴/۰۸/۲۰

    سلام امکانش هست سورس جستجوی عرضی را در سی شارپ در سایت قرار بدیدمرسی

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
breath-first searchالگوریتم جست وجوی عرضی چیست؟الگوریتم bfsشبه کد bfsاستراتژی های جستوجوی ناآگاهانهشبه کد الگوریتم جست وجوی عرضی گرافالگوریتم جست وجوی سطحیجست وجوی اول عرضالگوریتم های جستوجوی ناآگاهانهالگوریتم جست وجوی عرضیشبه کد الگوریتم جستوجوی عرضیآشنایی با الگوریتم جستوجوی عرضیالگوریتم های جستوجوی کورالگوریتم جست وجوی اول عرضشبه کد جست وجوی عرضی لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

کسب درآمد با کامپیوتر
تولید بیت کوین با کامپیوتر

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php