Введение в алгоритмы поиска: в глубину и в ширину.
Алгоритмы могут стать кошмаром, если вы будете изучать их только на экзаменах и технических собеседованиях. Разве не было бы намного проще, если бы вы могли весело провести время, изучая алгоритмы? Эта статья расскажет вам об основных алгоритмах поиска с примерами реализации традиционной настольной игры.
Играть в гоу
Го - это идеальная информационная игра для двух человек. Правила Го просты; однако количество разрешенных игровых позиций астрономическое, что делает настольную игру особенно популярной среди математиков и компьютерных ученых.
Правила игры в го, составленные Джеймсом Дэвисом «Правила и элементы го», показаны ниже.
1. The board is empty at the onset of the game (unless players agree to place a handicap). 2. Black makes the first move, after which White and Black alternate. 3. A move consists of placing one stone of one's own color on an empty intersection on the board. 4. A player may pass their turn at any time. 5. A stone or solidly connected group of stones of one color is captured and removed from the board when all the intersections directly adjacent to it are occupied by the enemy. (Capture of the enemy takes precedence over self-capture.) 6. No stone may be played so as to recreate a former board position. 7. Two consecutive passes end the game. 8. A player's area consists of all the points the player has either occupied or surrounded. 9. The player with more area wins.
В этой статье будет рассмотрено правило №5. Конкретно ответим на запрос:
Как компьютерная программа идентифицирует группу связанных камней?
Захватить дракона
Когда вы выстраиваете камни одного цвета рядом друг с другом по горизонтали или вертикали на доске Го, они образуют группу. Группа с достаточно большим количеством связанных камней также известна как дракон.
Поиск в глубину
Один из способов добиться этого программным путем - адаптировать алгоритм поиска в глубину. Рассмотрим три приведенных ниже примера, чтобы продемонстрировать поиск в глубину ниже:
Первый пример - это когда наш алгоритм находит соседа наверху нашего начального узла. Второй пример показывает порядок, в котором исследуется каждое направление. Третий пример - это суть нашего алгоритма: он исследует соединенные камни в одной ветви, насколько это возможно, прежде чем выполнить возврат и переходит к следующей ветви.
Для более формального определения алгоритма поиска в глубину:
DFS(graph, node, group)
add node to group
for each neighbor in the neighbors of node
if neighbor is not in the group
recursively call DFS(graph, neighbor, group)
Вы можете представить себе доску как граф, а каждый камень как узел. Группа, или дракон, представляет собой серию связанных узлов на графе. Акт поиска дракона - это просто обход графа, чтобы найти все связанные узлы.
Ниже приведен пример алгоритма поиска в глубину в JavaScript и сопутствующий тест с использованием Jest Testing Framework, чтобы продемонстрировать, как взаимодействовать с классами.
Следует отметить одну деталь реализации: в этом примере в качестве базовой структуры данных для хранения группы используется Set, что гарантирует уникальность каждого значения и предотвращает зацикливание кода.
Поиск в ширину
В отличие от исследования одного направления как можно дальше при поиске в глубину, поиск в ширину является альтернативным алгоритмом, который исследует все возможные края текущего узла перед переходом к следующему узлу.
В отличие от поиска в глубину, который обычно связан со структурой данных стека из-за рекурсивной природы алгоритма, псевдокод ниже реализует поиск в ширину итеративно со структурой данных очереди.
BFS(graph, node, group)
let Q be a queue
add node to Q
while Q is not empty
remove the first node from Q and let it be the current node
add current node to group
for each neighbor in the neighbors of current node
if neighbor is not in the group
add neighbor to Q
Полная реализация JavaScript:
Твой ход
Хотя алгоритмы поиска в глубину и в ширину подходят для поимки драконов, вы, к сожалению, будете слишком истощены, чтобы предпринимать какие-либо действия против них, если вам придется обыскивать всю доску каждый раз, когда вы делаете новый ход.
Следите за обновлениями: выйдет следующая статья о Как поймать дракона с совершенно новым алгоритмом и структурой данных.
