134. Ограничена дълбочина и итеративно задълбочаване

Ограниченото търсене в дълбочина спира разклоняването при зададена дълбочина. Итеративното задълбочаване повтаря това търсене с граници 0, 1, 2 и така нататък.

Раздел в разширената разработка.

Самостоятелна задача

Условие

S има наследници A и B в този ред. A има само наследник C, B има само наследник G. C има само наследник D. G и D нямат наследници. Единствената цел е G. S е на дълбочина 0, всеки преход увеличава дълбочината с 1. При всяка граница започваме от S и обхождаме в дълбочина, като разглеждаме наследниците в дадения ред. Възел точно на границата се проверява за цел, без да се обхождат наследниците му.

  1. Кои възли се проверяват при граница 1?
  2. В какъв ред се проверяват възлите при граница 2 до намиране на целта?
  3. На коя итерация се намира целта, ако първата е с граница 0?
  4. Кои възли се проверяват и при трите граници до успеха?

Отговори за самопроверка

Отговор 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

Изтегли example.py.

В речника Ограничена дълбочина и итеративно задълбочаване.