advertise laitec sharif univercity
دانلود سورس اپلیکیشن اندروید کتاب گرامر انگلیسی

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

10000 تومان
دانلود پروژه وب سایت اشعار با ASP.NET و SQL

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

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

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

38000 تومان
دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

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

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

68000 تومان

الگوریتم جست وجو با هزینه یکسان 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 searchالگوریتم جست وجو با هزینه یکسانالگوریتم جست وجوی هزینه یکسان ucsشبه کد جست وجوی هزینه یکسانشبه کد ucsالگوریتم های جستوجوی کورالگوریتم جست وجو با هزینه یکسان چیست؟الگوریتم جست وجوی uniform-castالگوریتم uniform-cast search لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

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

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