Ошибка с оптимальностью в алгоритме итеративного углубления глубины поиска

Question

Я реализовал версию Rush Hour (настольная игра-головоломка) в Python как демонстрацию некоторых алгоритмов ИИ.Игра не важна, потому что ИИ относительно независим от своих деталей: я попытался реализовать версию итеративного углубления в глубину поиска в Python следующим образом (обратите внимание, что этот код почти напрямую скопирован из текста ИИ Рассела и Норвиг3-е издание, для тех из вас, кто его знает):

def depth_limited_search(game, limit):
    node = GameNode(game)
    frontier = []
    #frontier = Queue.Queue()
    frontier.append(node)
    #frontier.put(node)
    frontier_hash_set = set()
    frontier_hash_set.add(str(node.state))
    explored = set()
    cutoff = False
    while True:
        if len(frontier) == 0:
        #if frontier.empty():
           break
        node = frontier.pop()
        #node = frontier.get()
        frontier_hash_set.remove(str(node.state))
        explored.add(str(node.state))
        if node.cost > limit:
            cutoff = True
        else:
            for action in node.state.get_actions():
                child = node.result(action)
                if str(child.state) not in frontier_hash_set and str(child.state) not in explored:
                    if child.goal_test():
                        show_solution(child)
                        return child.cost
                    frontier.append(child)
                    #frontier.put(child)
                    frontier_hash_set.add(str(child.state))
    if cutoff:
        return 'Cutoff'
    else:
        return None

def iterative_deepening_search(game):
    depth = 0
    while True:
        result = depth_limited_search(game, depth)
        if result != 'Cutoff':
            return result
        depth += 1

Алгоритм поиска в том виде, в котором он был реализован, действительно возвращает ответ в разумные сроки.Проблема в том, что ответ не оптимален.Моя тестовая доска имеет оптимальный ответ в 8 ходов, однако этот алгоритм возвращает один, используя 10 ходов.Если я заменим строки с закомментированными строками на строки с комментариями, эффективно превращая итеративный поиск с углублением в глубину в итеративный поиск с углублением в ширину, алгоритм ДОЛЖЕН возвращать оптимальные ответы!

Я уже давно смотрю на это, пытаясь понять, как простое изменение порядка обхода может привести к неоптимальности, и я не могу понять это.Любая помощь, указывающая на мою глупую ошибку, будет принята с благодарностью

Answer 1

Я не могу проверить это, но я думаю, что проблема заключается в следующем:

if str(child.state) not in frontier_hash_set and \
   str(child.state) not in explored:

Проблема в том, что ранее в этой итерации DFS child.state мог быть вставлен в границу или наборпосещенные состояния, но с большей стоимостью .

S -> A -> B -> C -> G
 \            /
  \-----> D -/ 

Очевидно, что вы не достигнете цели с пределом <3. Но когда предел = 3, ваша DFS может сначала посетить A, Bи C. Затем, когда он возвращается к S, посещает D и пытается посетить C, он не помещает C в стек, потому что вы посетили его ранее. </p>

Чтобы это исправить, я считаю, что вам нужно "не посещать "состояния, как вы вернетесь.С точки зрения реализации, вероятно, проще всего написать свой алгоритм рекурсивно и передать копии вашего набора исследуемых состояний в функциональном стиле.

Answer 2

Причина, по которой ваш код находит неоптимальное решение, заключается просто в способе работы по поиску по глубине и поиску по порядку.

При поиске по ширине будет пытаться все возможных 8-ходовых решений перед попыткой любых 9-ходовых решений, поэтому при поиске в ширину необходимо найти решение с наименьшим количеством возможных ходов.

В отличие от этого, поиск в глубину сначала попытается найти решения с 9, 10, 11, ... ходами, прежде чем он исчерпает все возможные решения с 8 ходами, и поэтому может привести к неоптимальному результату.

Например, если задано игровое дерево, которое выглядит следующим образом:

          1
     /         \
    2           3
  /   \       /   \
 4     5     6     7
 /\    /\    /\    /\
8  9  A  B  C  D  E  F

Приведенный код будет вызывать goal_test на узлах в следующем порядке: 2, 3, 6, 7, E, F, C, D, 4, 5, A, B, 8, 9. Обратите внимание, что узлы E и F тестируются перед дочерними узлами узла 6, а также перед дочерними узлами узла 2. Это поиск в глубину.

Альтернативная версия вашего кода будет вызывать goal_test в следующем порядке: 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Этояs поиск в первую очередь.

Редактировать: Мой плохой, мой порядок вызовов на goal_test выше верен только для последней итерации в iterative_deepening_search.Фактический порядок звонков на номер goal_test составляет 2, 3, 2, 3, 6, 7, 4, 5, 2, 3, 6, 7, E, F, C, D, 4, 5, A, B,8, 9. Я проверил это, фактически запустив код, поэтому я на 100% уверен, что теперь он правильный.

Вы уверены, что значение child.state уникально для каждого игрового узла?Если нет, алгоритм потерпит неудачу.Например, рассмотрим, что происходит, если узел 4 находится в том же состоянии, что и узел 6. В этом случае ваш код будет вызывать goal_test для узлов в следующем порядке: 2, 3, 2, 3, 6, 7, 5, 2, 3, 6, 7, E, F, C, D, 5, A, B. Обратите внимание, что goal_test это , никогда не вызывается на узлах 4, 8 и 9.

Но если мыпереключитесь на альтернативную версию вашего кода, тогда вызывается goal_test в следующем порядке: 2, 3, 2, 3, 4, 5, 7, 2, 3, 4, 5, 7, 8, 9, A, B,E, F. Теперь goal_test не вызывается на узлах 6, C и D!Я считаю, что это может быть причиной вашей проблемы.