Решение задачи о ходе коня¶

Алгоритм, который мы используем для решения задачи о ходе коня, называется поиск в глубину, или DFS (от англ. depth first search - прим. переводчика). В отличие от поиска в ширину, обсуждавшегося в предыдущем разделе и строящего один уровень дерева поиска за раз, этот алгоритм создаёт дерево поиска, исследуя одну из ветвей настолько глубоко, насколько это возможно. В этом разделе мы рассмотрим два алгоритма, реализующих DFS. Первый будет непосредственно решать задачу о ходе коня, явно запрещая посещать исследованный узел больше одного раза. Второй - более общий случай, позволяющий в процессе конструирования дерева посещать узлы несколько раз. Он будет использоваться в следующих разделах при разработке дополнительных алгоритмов для графов.

Исследование графа в глубину - в точности то, что нам необходимо для поиска пути ровно в 63 ребра. Мы увидим, как алгоритм, попадая в тупик (место на графе, откуда больше нет возможных ходов), возвращается вверх по дереву на следующую по глубине вершину, что позволяет сделать допустимый ход.

Функция knightTour принимает четыре параметра: n - текущую глубину дерева, path - список посещённых вершин, u - вершину, которую мы бы хотели исследовать, и limit - количество узлов в графе. Эта функция рекурсивная. Когда она вызывается, то прежде всего проверяет базовое условие. Если путь содержит 64 вершины, мы возвращаем knightTour со статусом True, показывающим успешное завершение поиска маршрута. В противном случае исследование продолжается на уровне ниже, для чего выбирается новая вершина и вызывается knightTour.

DFS тоже использует окрашивание для отслеживания посещённых вершин графа. Непосещённые узлы имеют белый цвет, посещённые - серый. Если все соседи данной вершины уже исследованы, но цель в 64 узла не достигнута, то мы зашли в тупик. Следовательно, необходимо вернуться назад. Откат происходит в том случае, когда knightTour возвращает False. В поиске в ширину для отслеживания вершины, которую нужно посетить следующей, мы использовали очередь. Поскольку поиск в глубину рекурсивен, для помощи с откатом неявно используется стек. Когда вызов knightTour возвращает False (строка 11), мы попрежнему находимся внутри цикла while и рассматриваем следующую вершину из nbrList.

Листинг 3

from pythonds.graphs import Graph, Vertex
def knightTour(n,path,u,limit):
        u.setColor('gray')
        path.append(u)
        if n < limit:
            nbrList = list(u.getConnections())
            i = 0
            done = False
            while i < len(nbrList) and not done:
                if nbrList[i].getColor() == 'white':
                    done = knightTour(n+1, path, nbrList[i], limit)
                i = i + 1
            if not done:  # prepare to backtrack
                path.pop()
                u.setColor('white')
        else:
            done = True
        return done

Давайте рассмотрим простой пример работы knightTour в действии. Для отслеживания шагов поиска вы можете обратиться к приведённым ниже рисункам. Будем полагать, что вызовы метода getConnections в строке 6 происходят в алфавитном порядке. Начнём с knightTour(0,path,A,6).

knightTour начинает работу с узла А (рисунок 3). Он имеет смежные вершины B и D. Поскольку в алфавите B идёт перед D, то DFS выбирает её для дальнейшего исследования, как показано на рисунке 4. Для этого рекурсивно вызывается knightTour. В смежна с C и D, поэтому следующим knightTour выбирает исследование С. Однако, как вы можете видеть из рисунка 5, вершина С - тупик без смежных белых узлов. В этот момент мы меняем цвет С обратно на белый, и вызов knightTour возвращает False. Возврат из рекурсивного вызова эффективно откатывает поиск к вершине В (см. рисунок 6). Следующая вершина в списке исследования - узел D, так что knightTour делает для неё рекурсивный вызов (см. рисунок 7). Отсюда функция может продолжить делать рекурсивные вызовы до тех пор, пока вновь не дойдёт до узла С (см. рисунок 8, рисунок 9 и рисунок 10). Однако, в этот раз проверка n < limit даст отрицательный результат, поэтому мы знаем, что узлы графа закончились. Теперь можно вернуть True, показывая, что маршрут успешно проложен. Когда мы вернём список, path будет иметь значение [A,B,D,E,F,C] - порядок, в котором нужно обойти граф, чтобы посетить каждую его вершину всего один раз.

Рисунок 3: Начинаем с узла A

Рисунок 4: Исследуем B

Рисунок 5: Узел C - тупик

Рисунок 6: Возврат в B

Рисунок 7: Исследуем D

Рисунок 8: Исследуем E

Рисунок 9: Исследуем F

Рисунок 10: Конец

На рисунке 11 показано, как целиком выглядит путь на доске 8х8. Таких маршрутов может быть много; некоторые из них будут симметричными. Добавив несколько изменений, вы можете получить замкнутые маршруты, начинающиеся и заканчивающиеся в одной клетке.

Рисунок 11: Маршрут по доске целиком