الگوریتم جست وجوی تعمیق تکراری iterative deepening search
الگوریتم جست وجوی تعمیق تکراری iterative deepening search
جست وجوی تعمیق تکراری (عمیق کننده تکراری) یا IDS یک استراتژی کلی از استراتژی های جست وجوی ناآگاهانه است و غالبا همراه با جست وجوی عمقی بکار میرود، و بهترین عمق محدود را پیدا میکند. این الگوریتم از مقدار 0 بعنوان عمق محدود شروع میکند و مقدار آن را به تدریج اضافه میکند، تا اینکه هدفی پیدا شود. هدف وقتی پیدا میشود که عمق محدود به d برسد که d عمق مربوط به عمیق ترین گره هدف است.
الگوریتم جست وجوی تعمیق تکراری ،IDS ، فواید جست وجوی عمقی و جست وجوی عرضی را با هم ترکیب میکند.
جست وجوی تعمیق تکراری همانند جست وجوی عمقی، به حافظه متوسطی نیاز دارد، که برابر با O(bd) است. وقتی ضریب انشعاب متناهی باشد، کامل است و وقتی هزینه مسیر، تابعی غیر نزولی از عمق گره باشد، بهینه است. جست وجوی عمیق کننده تکراری ممکن است وقت زیادی را هدر دهد چون حالتها را چندین بار تولید میکند اما این کار هزینه زیادی ندارد.
در IDS گره های موجود در سطح پایین (در عمق d) یک بار تولید میشوند، آنهایی که در یک سطح بالاتر از سطح پایینی قرار دارند، دوبار تولید میشوند و این روند ادامه میابد تا به فرزندان ریشه برسیم که d بار تولید میشوند. پیچیدگی زمان آن O(bᵈ) است که این مقدار از نظر مجانبی شبیه جست وجوی عرضی است.
بطور کلی وقتی فضای جست وجو بزرگ است و عمق جواب معلوم نیست، جست وجوی تعمیق تکراری روش جست وجوی مناسبی است.
شبه کد الگوریتم جست وجوی تعمیق تکراری iterative deepening search :
function ITEATIVE-DEEPING-SEARCH (problem) returns a solution, or
for depth =0 to ∞ do
result <- DEPTH-LIMITED-SEARCH(problem,depth)
if result ≠ cutoff then return result
سلام میخواستم معمای 8رو با ین روش حلش کنم میتونین پروژشو بفرستین به ایمیلم با تشکر فراوان
سلامیه پروژه با زبان C یا مطلب در مورد IDS می خواستم ممنون میشم اگه برام ایمیل کنید خیلی فوری استبا تشکرفراوان
سلام خسته نباشید. ممکنه مسله بازل 8 تایی رو با این روش برام بفرستین.. ممنون
سلام ،پیاده سازی الگوریتم ids به هریک از زبان های برنامه نویسی رو میخواستم
سلام خسته نباشید میتونید برام کدکامل این الگوریتم به زبان پایتون را بزارید ممنون