الگوریتم جست وجو با هزینه یکسان uniform-cast search
الگوریتم جست وجو با هزینه یکسان uniform-cast search
جست وجو با هزینه یکسان یکی از استراتژی های جست وجوی ناآگاهانه است. منظور از ناآگاهانه این است که این استراتژی ها فقط میتوانند پسین ها را تولید کنند و حالت هدف را از حالت غیر هدف تشخیص دهند.
وقتی هزینه ی تمام مراحل یکسان باشد، جست وجوی عرضی بهینه است، زیرا همیشه "کم عمق ترین" گره ی بسط داده نشده را بسط میدهد. با یک تغییر ساده، میتوان الگوریتمی پیدا کرد که با هر "تابع هزینه مرحله" بهینه باشد. به جای بسط کم عمق ترین گره، الگوریتم جست وجو با هزینه یکسان، گره ای مثل n را توسعه میدهد که کمترین هزینه در مسیر، یعنی g(n) را دارد. این کار با ذخیره کردن مرز در صف اولویتی که بر حسب g مرتب شده است انجام میگیرد.
الگوریتم "جست وجو با هزینه یکسان" علاوه بر مرتب سازی صف بر حسب هزینه دو تفاوت دیگر با جست وجوی عرضی دارد:
- آزمون هدف ، وقتی در گره ای اجرا میشود که برای توسعه انتخاب شود، نه وقتی که گره تولید شد.
- وقتی مسیر بهتری به یک گره ی موجود در مرز پیدا شود، یک آزمون هدف دیگر انجام میگیرد.
الگوریتم "جست وجو با هزینه یکسان(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
.gif)
