advertise laitec sharif univercity
دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

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

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

10000 تومان
دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

10000 تومان
پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

68000 تومان
دانلود پروژه فروشنده دوره گرد با الگوریتم ازدحام ذرات PSO در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم ازدحام ذرات PSO در #C

10000 تومان

الگوریتم جست وجوی عرضی 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