Кіріспе
Іздеу стратегиясы
In computer science, iterative deepening search or more specifically iterative deepening depth first search (IDS or IDDFS) is a state space/graph search strategy in which a depth limited version of depth first search is run repeatedly with increasing depth limits until the goal is found. IDDFS is optimal, meaning that it finds the shallowest goal. Iterative deepening visits states multiple times, and it may seem wasteful. However, if IDDFS explores a search tree to depth , most of the total effort is in exploring the states at depth Relative to the number of states at depth , the cost of repeatedly visiting the states above this depth is always small. The main advantage of IDDFS in game tree searching is that the earlier searches tend to improve the commonly used heuristics, such as the killer heuristic and alpha–beta pruning, so that a more accurate estimate of the score of various nodes at the final depth search can occur, and the search completes more quickly since it is done in a better order. For example, alpha–beta pruning is most efficient if it searches the best moves first. The higher the branching factor, the lower the overhead of repeatedly expanded states,
Iterative deepening A* is a best first search that performs iterative deepening based on "f" values similar to the ones computed in the A* algorithm.
Компьютерлік ғылымда, қайталанатын тереңдеу іздеуі немесе дәлірек айтқанда, қайталанатын тереңдеу тереңдік бірінші іздеу (IDS немесе IDDFS) – бұл күй кеңістігі/графтық іздеу стратегиясы, онда мақсатқа қол жеткенге дейін тереңдік шектеулі тереңдік бірінші іздеудің нұсқасы қайта-қайта орындалады. IDDFS оптималды, яғни ең шалқая мақсатты табады. Итеративті тереңдету күйлерді бірнеше рет қарастырады, бұл ысырапқа салынғандықтай көрінуі мүмкін. Дегенмен, егер IDDFS іздеу ағашын белгілі бір тереңдікке дейін зерттесе, жалпы жұмсалған күш-жігердің көп бөлігі осы тереңдіктегі күйлерді зерттеуге жұмсалады. Осы тереңдіктегі күйлер санына қатысты, осы тереңдіктен жоғарыдағы күйлерді қайта-қайта қарастырудың құны әрқашан аз болады. IDDFS-тің ойын ағаштарын іздеудегі басты артықшылығы – бастапқы іздеулер әдетте қолданылатын эвристикаларды жақсартады, мысалы, «өлтіруші» эвристика және альфа-бета кесу, соның салдарынан соңғы тереңдіктегі іздеуде әртүрлі түйіндердің бағасын дәлірек анықтауға болады, ал іздеу жақсы тәртіпте орындалғандықтан тез аяқталады. Мысалы, альфа-бета кесу ең тиімді, егер ол ең жақсы қадамдарды бірінші іздесе. Тармақталу факторы неғұрлым жоғары болса, қайта-қайта кеңейтілген күйлерге келетін шығын соғұрлым төмен болады. Итеративті тереңдету A* – бұл ең жақсы бірінші іздеу, ол A* алгоритмінде есептелгендей "f" мәндеріне негізделген итеративті тереңдетуді жүзеге асырады.
In computer science, iterative deepening search or more specifically iterative deepening depth first search (IDS or IDDFS) is a state space/graph search strategy in which a depth limited version of depth first search is run repeatedly with increasing depth limits until the goal is found. IDDFS is optimal, meaning that it finds the shallowest goal. Iterative deepening visits states multiple times, and it may seem wasteful. However, if IDDFS explores a search tree to depth , most of the total effort is in exploring the states at depth Relative to the number of states at depth , the cost of repeatedly visiting the states above this depth is always small. The main advantage of IDDFS in game tree searching is that the earlier searches tend to improve the commonly used heuristics, such as the killer heuristic and alpha–beta pruning, so that a more accurate estimate of the score of various nodes at the final depth search can occur, and the search completes more quickly since it is done in a better order. For example, alpha–beta pruning is most efficient if it searches the best moves first. The higher the branching factor, the lower the overhead of repeatedly expanded states,
Iterative deepening A* is a best first search that performs iterative deepening based on "f" values similar to the ones computed in the A* algorithm.
Екі бағыттағы IDDFS
IDDFS-тің екі бағытты теңдесі бар, ол екі іздеуді кезекпен орындайды: біреуі бастапқы түйінен басталып, бағытталған қабырғалар бойынша жүреді, ал екіншісі мақсатты түйінен басталып, қарама-қарсы бағыттағы бағытталған қабырғалар бойынша (қабырғаның бастапқы түйінінен қабырғаның соңғы түйініне дейін) жүреді. Іздеу процесі бастапқы түйін мен мақсатты түйіннің бірдей екенін тексереді, егер солай болса, бір ғана бастапқы/мақсатты түйінен тұратын тривиальды жолды қайтарады. Әйтпесе, алға іздеу процесі бастапқы түйіннің (жинақ ) бала түйіндерін кеңейтеді, артқа іздеу процесі мақсатты түйіннің (жинақ ) ата-ана түйіндерін кеңейтеді және олардың қиылысы бар-жоғы тексеріледі. Егер қиылыс болса, ең қысқа жол табылады. Әйтпесе, іздеу тереңдігі артырылып, есептеу қайтадан орындалады. Алгоритмнің бір шектеуі – жұп емес, тақ саны қабырғалардан тұратын ең қысқа жол табылмайды. Мысалы, ең қысқа жол болсын. Тереңдік қабырғалар бойынша екі қадамға жеткенде, алға іздеуден бастап , артқа іздеуден бастап жүреді. Іздеу шекаралары бір-бірінен өтіп кетеді, нәтижесінде жұп саны қабырғалардан тұратын ең оңтайлы емес жол қайтарылады. Бұл төмендегі суреттерде көрсетілген: кеңістіктік жайлылығына келетін болсақ, алгоритм екі іздеу процесінің кездесетін ортаңғы түйіннің бар екенін анықтау үшін алға іздеу процесіндегі ең терең түйіндерді белгілейді. Екі бағытты IDDFS-ті қолданудың қосымша қиындығы – егер бастапқы және мақсатты түйіндер әртүрлі күшті байланысқан компоненттерде болса, мысалы, егер бастапқы түйінен шығатын және мақсатты түйінге кіретін қабырға болмаса, іздеу ешқашан аяқталмайды.
What comes to space complexity, the algorithm colors the deepest nodes in the forward search process in order to detect existence of the middle node where the two search processes meet. Additional difficulty of applying bidirectional IDDFS is that if the source and the target nodes are in different strongly connected components, say, , if there is no arc leaving and entering , the search will never terminate.