Кіріспе

Эвристикалық жол табу алгоритмі

Итеративті тереңдету A* (IDA*) – бұл графты кезігу және жол іздеу алгоритмі, ол салмақталған графта белгіленген бастапқы түйін мен мақсатты түйіндер жиынтығының кез келген мүшесі арасындағы ең қысқа жолды таба алады. Бұл итеративті тереңдету тереңдігі бірінші іздеудің түрі, ол A* іздеу алгоритмінен мақсатқа жетуге қажетті қалған шығындарды консервативті бағалау үшін эвристикалық функцияны пайдалану идеясын қабылдайды. Тереңдікті бірінші іздеу алгоритмі болғандықтан, оның жадты пайдалануы A*-ға қарағанда төмен, бірақ қарапайым итеративті тереңдету іздеуінен айырмашылығы, ол ең перспективалы түйіндерді зерттеуге бағытталған және осылайша іздеу ағашының барлық жерінде бірдей тереңдікке түспейді. A*-дан айырмашылығы, IDA* динамикалық бағдарламалауды қолданбайды, сондықтан бір түйіндерді көп рет зерттеуге соқтырады. Стандартты итеративті тереңдету тереңдігі бірінші іздеу әр итерация үшін іздеу тереңдігін пайдаланса, IDA* одан гөрі ақпараттық , мұнда – тамырдан түйінге дейінгі жолдың құны, ал – мақсатқа дейінгі жолдың құнына қатысты проблемаға тән эвристикалық бағалауды пайдаланады. Алгоритмді алғаш рет 1985 жылы Ричард Корф сипаттаған.

Сипаттама

Итеративті тереңдету А* былай жұмыс істейді: әрбір итерацияда тереңдік бойынша іздеу жүргізіледі, оның толық құны белгілі бір шектен асқанда тармақ тоқтатылады. Бұл шек бастапқы күйдегі құнның бағалауынан басталады және алгоритмнің әрбір итерациясымен артады. Әрбір итерацияда келесі итерация үшін қолданылатын шекті мән – ағымдағы шектен асып кеткен барлық мәндердің ең төменгі құны болып табылады. IDA* жадтың шектеулі болуы жағдайында тиімді. A* іздеуі жадты жылдам толтыра алатын зерттелмеген түйіндердің үлкен тізімін сақтайды. Ал, IDA* ағымдағы жолдағы түйіндерден басқа ешқандай түйіннің мәліметтерін сақтамайды, сондықтан ол құрастырған шешімнің ұзындығына пропорционал жадты ғана қажет етеді. Оның уақыттық күрделілігі Korf және авторлар тобы тарапынан h эвристикалық құнның бағалауы дұрыс деп есептегенде талданды, яғни барлық n түйіндері және n-нің барлық n' көршілері үшін; олар экспоненциалды көлемдегі проблема бойынша қарапайым іздеуге қарағанда IDA* іздеу тереңдігін азайтатынын (тұрақты фактормен), бірақ тармақтану коэффициентін азайта алмайтынын көрсетті. Рекурсивті ең жақсы іздеу – A* іздеуінің жадты аз қолданатын нұсқасы, ол практикада IDA*-дан жылдам болуы мүмкін, себебі түйіндерді қайта жасауды азайтады. Рубик текшесін шешу – IDA* арқылы шешуге болатын жоспарлау мәселесінің мысалы.