134. Ограничена дълбочина и итеративно задълбочаване
Ограниченото търсене в дълбочина спира разклоняването при зададена дълбочина. Итеративното задълбочаване повтаря това търсене с граници 0, 1, 2 и така нататък.
Раздел в разширената разработка.
Самостоятелна задача
Условие
S има наследници A и B в този ред. A има само наследник C, B има само наследник G. C има само наследник D. G и D нямат наследници. Единствената цел е G. S е на дълбочина 0, всеки преход увеличава дълбочината с 1. При всяка граница започваме от S и обхождаме в дълбочина, като разглеждаме наследниците в дадения ред. Възел точно на границата се проверява за цел, без да се обхождат наследниците му.
- Кои възли се проверяват при граница 1?
- В какъв ред се проверяват възлите при граница 2 до намиране на целта?
- На коя итерация се намира целта, ако първата е с граница 0?
- Кои възли се проверяват и при трите граници до успеха?
Отговори за самопроверка
Отговор 1
S, A, B.
Отговор 2
S, A, C, B, G.
Отговор 3
На третата, с граница 2.
Отговор 4
Само S.
Изпълним пример
Python 3. При всеки опит remaining показва колко прехода са позволени от текущия възел. Смени реда на децата на S и проследи реда на посещенията.
children = {"S": ["A", "B"], "A": ["C"], "B": ["G"]}
def search(node, remaining):
print(node, end=" ")
if node == "G":
return True
if remaining == 0:
return False
for child in children.get(node, []):
if search(child, remaining - 1):
return True
return False
for limit in range(3):
print(limit, end=": ")
found = search("S", limit)
print()
if found:
break