laitec sharif univercity جهان سورس advertise تبلیغات در سورس کد
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

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

45000 تومان
دانلود سورس پروژه پایانی وب سایت بنگاه املاک با php

دانلود سورس پروژه پایانی وب سایت بنگاه املاک با php

18000 تومان
دانلود آپلود سنتر پیشرفته با PHP و Ajax

دانلود آپلود سنتر پیشرفته با PHP و Ajax

3000 تومان
پروژه کامل مدیریت شرکت نرم افزاری با سی شارپ و SQL

پروژه کامل مدیریت شرکت نرم افزاری با سی شارپ و SQL

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

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

3000 تومان

الگوریتم جست وجو با هزینه یکسان uniform-cast search

جست وجو با هزینه یکسان یکی از استراتژی های جست وجوی ناآگاهانه است. این الگوریتم در صورتیکه مسیر بهینه ای برای گره ای پیدا شده باشد، آنرا برای توسعه انتخاب میکند پس بطور کلی الگوریتمی بهینه است
الگوریتم جست وجو با هزینه یکسان uniform-cast search

الگوریتم جست وجو با هزینه یکسان uniform-cast search

جست وجو با هزینه یکسان یکی از استراتژی های جست وجوی ناآگاهانه است. منظور از ناآگاهانه این است که این استراتژی ها فقط میتوانند پسین ها را تولید کنند و حالت هدف را از حالت غیر هدف تشخیص دهند.

وقتی هزینه ی تمام مراحل یکسان باشد، جست وجوی عرضی بهینه است، زیرا همیشه "کم عمق ترین" گره ی بسط داده نشده را بسط میدهد. با یک تغییر ساده، میتوان الگوریتمی پیدا کرد که با هر "تابع هزینه مرحله" بهینه باشد. به جای بسط کم عمق ترین گره، الگوریتم جست وجو با هزینه  یکسان، گره ای مثل n را توسعه میدهد که کمترین هزینه در مسیر، یعنی  g(n) را دارد. این کار با ذخیره کردن مرز در صف اولویتی که بر حسب g مرتب شده است انجام میگیرد.

الگوریتم "جست وجو با هزینه یکسان" علاوه بر مرتب سازی صف بر حسب هزینه دو تفاوت دیگر با جست وجوی عرضی دارد:

  1. آزمون هدف ، وقتی در گره ای اجرا میشود که برای توسعه انتخاب شود، نه وقتی که گره تولید شد.
  2. وقتی مسیر بهتری به یک گره ی موجود در مرز پیدا شود، یک آزمون هدف دیگر انجام میگیرد.

الگوریتم "جست وجو با هزینه یکسان(ucs) " بطور کلی بهینه است: از آنجایی که هر وقت "جست وجو با هزینه یکسان" گره ای مثل n را برای توسعه انتخاب میکند، مسیر بهینه ای به آن گره پیدا شده است. در این روش گره ها را به ترتیب هزینه مسیر بهینه آنها توسعه میدهد. بنابراین تولید گره هدفی که برای توسعه انتخاب شد باید جواب بهینه باشد.

"جست وجو با هزینه یکسان"  به تعداد مراحل موجود در مسیر کاری ندارد، بلکه فقط با هزینه کل سروکار دارد. پس اگر مسیری وجود داشته باشدکه دارای تعداد نامتناهی از فعالیتهایی با هزینه صفر باشد، این الگوریتم در حلقه بی نهایت گیر میکند. خاصیت کامل بودن در صورتی برقرار است که هزینه هر مرحله، از یک مقدار ثابت و کوچک بیشتر باشد.

الگوریتم "جست وجو با هزینه یکسان" به جای عمق ها از هزینه های مسیر استفاده میکند. پس پیچیدگی آن به آسانی بر حسب b وd مشخص نمیشود.اگر C* هزینه جواب بهینه باشد و فرض کنید هزینه هر فعالیت حداقل Ɛ است . آنگاه پیچیدگی زمان و حافظه در بدترین حالت برابر است با O(b^1+c*/Ɛ)  .

وقتی هزینه تمام مراحل یکسان باشد ، جستوجو با هزینه یکنواخت شبیه جستوجوی عرضی است، با این تفاوت که جستوجوی عرضی بلافاصله پس از تولید هدف ، متوقف میشود در حالیکه جست وجو با هزینه یکسان تمام گره های موجود در عمق هدف را بررسی میکند تا گره ای با هزینه کمتر را بیایبد. پس "جست وجو با هزینه یکسان" با توسعه غیر ضروری در عمق d کار بیشتری انجام میدهد.

شبه کد الگوریتم "جست وجو با هزینه یکسان"

function UNIFORM-COST-SEARCH (problem) returns a solution, or failure

       node <-- a node with STATE = problem.INITIAL-STATE , PATH-COST=0       

       frontier <-- a priority queue ordered by PATH-COST , 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                        

                        (frontier <-- INSERT(child, frontier                                 

                  else if child.STATE is in frontier with higher PATH-COST  then                        

                          replace that frontier node with child                                

 



0
نظرات

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



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


advertise
شبه کد ucsالگوریتم جست وجوی uniform-castآشنایی با الگوریتم جست وجو با هزینه یکسانشبه کد جست وجوی هزینه یکسانالگوریتم uniform-cast searchالگوریتم جست وجو با هزینه یکسان چیست؟الگوریتم های جستوجوی کوردانلود رایگان شبه کد الگوریتم جست وجو با هزینه یکسانآموزش پیاده سازی الگوریتم جست وجو با هزینه یکسان ucsشبه کد الگوریتم جست وجو با هزینه یکسانالگوریتم جست وجوی هزینه یکسان ucsuniform-cast searchالگوریتم جست وجو با هزینه یکسانجست وجو با هزینه یکسان لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

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

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