Небольшой вкус классического ИИ: решение задач поиска

Узнайте, как решать поисковые задачи системным и общим способом

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

Судокус,
скользящие пазлы, также известные как 8-пазлы, 15-пазлы, …,
Ханойская башня (рекурсивные воспоминания лекций, кто-нибудь?),
задача сортировки блинов, которую мы используем в качестве примера позже,
nпроблема ферзей
и многое другое.

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

В этой статье я хочу показать вам

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

СПОЙЛЕР: Найдите код на мой Github.

Проблемы поиска в пространстве состояний

Задачи, которые я теперь также буду называть играми, не так сложны, как шахматы, го или любая продвинутая компьютерная игра. Тем не менее, их интересно изучать, а решение некоторых из них может оказаться уже NP-сложным, т.е., вероятно, полиномиальных алгоритмов для их решения вообще не существует.

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

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

Вы можете выполнить действие, чтобы изменить одно игровое состояние на другое. В судоку заполнение чисел — это единственные действия, которые вы можете предпринять. Вы должны указать пустую ячейку и число, а затем записать число в указанную ячейку, изменив состояние игры.

Существует также целевое состояние, которого мы пытаемся достичь, что позволяет нам выиграть игру. В судоку каждая строка, столбец и блок должны отображать все цифры от 1 до 9 ровно один раз.

Решение проблем с поиском

Хорошо, если вы рассмотрели некоторые из вышеперечисленных задач и головоломок, вы, вероятно, заметили, что все они кажутся совершенно разными. Как мы можем объединить их в единую структуру? Итак, единственный секрет:

Решение проблем поиска сводится к обходу графа.

Так что это значит? Надеюсь, вы слышали о таких алгоритмах, как поиск в глубину (DFS) и поиск в ширину (BFS). Эти алгоритмы позволяют вам систематически проходить по графу, точно так же, как мы хотим систематически решать эти головоломки. Если вы новичок в этом, просто читайте дальше, потому что вы узнаете о них сейчас. Давайте возьмем в качестве примера задачу сортировки блинов, потому что она менее сложна, чем судоку, и вы можете увидеть другую настройку игровых состояний и действий.

Сортировка блинов 🥞

Проблему можно описать так:

У вас есть неупорядоченная стопка изnблинов разного размера. Вы хотите отсортировать эту стопку (самый маленький блин сверху, самый большой снизу) с помощью лопатки, переворачивая части стопки.

См. следующий рисунок в качестве примера одного из возможных действий:

Пронумеруем блины в соответствии с их размером, 1 — самый маленький, а 6 — самый большой. На картинке выше мы находимся в состоянии игры (2, 1, 4, 6, 3, 5), сверху вниз. С помощью действия «Перевернуть в позиции 3» мы можем превратить старое состояние игры в новое (4, 1, 2, 6, 3, 5), т.е. порядок верхних 3 блинов обратный.

Систематическое решение для 4 блинов

Предположим, что мы начинаем в начальном игровом состоянии (4, 2, 1, 3). Опять же, 4 — это самый большой блин, а 1 — самый маленький. Я записываю состояние игры сверху вниз.

Теперь мы берем это состояние и перечисляем все возможные следующие состояния. Мы называем этот шаг расширением текущего состояния.

Обратите внимание, что мы можем отказаться от действия "Перевернуть на 1", потому что оно просто бездействует, т. е. снова приводит к тому же состоянию.

Теперь вы, наверное, знаете упражнение. Мы продолжаем расширять четыре новых узла, пока не найдем наше целевое состояние:

В итоге это могло бы выглядеть так, опуская множество состояний:

Отлично, правда? И самое лучшее, что этот метод не требует ничего особенного в проблеме блинов. Ему нужны состояния и действия, вот и все. Мы также можем поместить поля судоку 9×9 в узлы, шахматные доски (для задачи n ферзей) или что угодно. Важны следующие вещи:

Нам нужен способ распознавать целевое состояние.
Учитывая состояние, нам нужен способ перечислить следующие состояния.

Сейчас мы формализуем этот алгоритм.

Общая реализация на Python

Во-первых, давайте определим базовый класс SearchProblem, чтобы согласовать интерфейс, который должен иметь задача поиска. Этот класс по-прежнему будет иметь недостающую функциональность, это просто шаблон. Мы создадим из него конкретные классы, а затем реализуем недостающую функциональность. Вот так:

class SearchProblem:
    def __init__(self, state):
        self.state = state
        
    def is_solution(self):
        # Implement me!
        pass
    
    def get_next_states(self):
        # Implement me!
        pass
    
    def __hash__(self):
        # Implement me!
        pass
    
    def __repr__(self):
        return str(self.state)
    
    def __eq__(self, other):
        return self.state == other.state

__hash__ , __eq__ и __repr__ (а также __init__) являются примерами так называемых магических функций или методов Дандера. Реализация __hash__ позволяет нам использовать функцию Python hash для объектов этого класса. Введите hash((1, 2, 3)) в качестве примера, чтобы получить хеш-значение кортежа (1, 2, 3).

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

Зачем нам это нужно? Нам нужны оба этих метода, потому что наш алгоритм решения проблем должен помещать объекты задачи поиска в качестве ключей в словарь для эффективной работы, а ключи должны быть хешируемыми , то есть hash(our_object) не должен выдавать ошибку.

Реализация __eq__ позволяет нам сравнивать два разных объекта, т. е. равны они или нет. Обычно мы просто проверяем, равно ли состояние, поэтому я уже дал ему конкретную реализацию.

Реализация __repr__ просто дает хорошее представление объекта класса при его печати. Обычно достаточно просто распечатать состояние.

Отлично, поэтому общую задачу поиска можно инициализировать и присвоить ей (начальное) состояние. Мы также можем проверить, являются ли две задачи одинаковыми, проверив, равны ли их состояния, и мы можем красиво напечатать это. Но самые важные детали еще предстоит уточнить, и они сильно зависят от проблемы.

Вернемся к блинам

Давайте снова обратимся к проблеме сортировки блинов, чтобы дать конкретные реализации is_solution , get_next_states и __hash__ .

Наше соглашение: состояние будет списком, состоящим из целых чисел от 1 доn. Целые числа представляют размеры блинов. Первый элемент в списке — верхний блин. Одним из примеров может быть [4, 2, 1, 3].

class PancakeSortingProblem(SearchProblem):
    def is_solution(self):
        for i in range(len(self.state)-1):
            if self.state[i] > self.state[i+1]:
                return False
        return True
    
    def get_next_states(self):
        for i in range(2, len(self.state)+1):
            upper = self.state[:i]
            lower = self.state[i:]
            next_state = upper[::-1] + lower
            yield PancakeSortingProblem(next_state)
    
    def __hash__(self):
        n = max(self.state) + 1
        return sum([x*n**i for i, x in enumerate(self.state)])

Я думаю, что реализации для is_solution и get_next_states не должны быть слишком сложными для понимания. is_solution на самом деле просто проверяет, отсортирован ли массив. get_next_states принимает состояние (список) и возвращает все следующие состояния, переворачивая верхнюю часть стопки блинов для каждой возможной позиции. Давайте попробуем это:

p = PancakeSortingProblem([4, 2, 1, 3]) # start state = [4, 2, 1, 3]

for next_state in p.get_next_states():
    print(next_state)
# Output (thanks to the __repr__ method!):
# [2, 4, 1, 3]
# [1, 2, 4, 3]
# [3, 1, 2, 4]

Примечание. Я пропустил одно из четырех следующих состояний, потому что действие "Перевернуть в позиции 1" по сути является действием "Ничего не делать". Это только добавляет сложности, поэтому мы его опускаем.

Давайте обратимся к слону в комнате: этот хэш. Что я там делал? Цель состояла в том, чтобы взять состояние и преобразовать его в целое число, хеш-значение.

Как туда попасть? Вычисляя

Это все, что я реализовал. По сути, я рассматриваю состояние [4, 2, 1, 3] как 5-значное (как двоичное, только с основанием 5 вместо 2) число 3124 (4213 в обратном порядке) и преобразую его обратно в десятичную систему. Это приводит к тому, что два разных состояния имеют два разных значения хеш-функции (техническая деталь: если результат меньше 2⁶³), что хорошо с точки зрения производительности. Оставим это.

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

def __hash__(self):
    return 1

но это приводит к более медленным алгоритмам в дальнейшем, поэтому избегайте этого. Отлично, у нас есть рабочий класс задач, так что мы можем заняться решением прямо сейчас!

Определение класса решателя задач поиска

Опишем алгоритм словами.

Мы берем начальное состояние (в виде проблемного объекта) и помещаем его в список с именем frontier.
Мы извлекаем состояние (то есть удаляем его из списка) и проверяем, является ли оно целью. Если нет, мы расширяем его.
Мы добавляем все следующие состояния, которых мы еще не видели, в frontier. Это мешает нам бегать по кругу.
Затем повторяйте шаги 2 и 3, пока не будет найдена цель, т. е. вытолкнуть, проверить, расширить, вытолкнуть, проверить, расширить, …

По сути, мы заполняем список (изначально заполненный начальным состоянием) всеми состояниями, с которыми мы сталкиваемся. Это список состояний, которые необходимо изучить. Всякий раз, когда этот список пуст, больше нечего исследовать. Если мы не нашли цель до тех пор, решения нет.

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

В коде это может выглядеть так:

class SearchProblemSolverDFS:
    def solve(self, start_problem):
        frontier = [start_problem]
        self.backlinks = {start_problem: None}
        self.solution = None

        while frontier and self.solution is None:
            current_state = frontier.pop()

            if current_state.is_solution():
                self.solution = current_state

            for next_state in current_state.get_next_states():
                if next_state not in self.backlinks:
                    self.backlinks[next_state] = current_state
                    frontier.append(next_state)

    def print_solution(self):
        current_state = self.solution
        result = []
        while current_state is not None:
            result.append(current_state)
            current_state = self.backlinks[current_state]
        
        return result[::-1]

Некоторые комментарии к коду:

В методе solve я также представил словарь backlinks. Это имеет две разные цели:

Следите за посещенными состояниями, как вы можете видеть в строке if next_state not in self.backlinks.
Следите за тем, как добраться до каждого состояния, то есть сохраняя предшественников. Начальное состояние не имеет предшественника, поэтому я инициализировал его как {start_problem: None}.

Я также создал метод print_solution, который выводит, как перейти к целевому состоянию из начального состояния.

Круто, попробуем!

Запуск кода

Мы проделали так много работы, но вы только посмотрите, как легко теперь все применить:

four_pancakes = PancakeSortingProblem([4, 2, 1, 3])
solver = SearchProblemSolverDFS()

solver.solve(four_pancakes)
solver.print_solution()

# Output:
# [[4, 2, 1, 3], [3, 1, 2, 4], [2, 1, 3, 4], [1, 2, 3, 4]]

Это соответствует решению, которое мы видели на картинке выше. Хороший! Попробуйте приготовить другие блины, например,

PancakeSortingProblem([4, 2, 1, 3, 5, 7, 6, 8])

Решение оооооооооооооооооооооооооооооооооооооооооооо бы, я объясню вам почему.

Некоторые замечания

Мы реализовали SearchProblemSolver через поиск в глубину (DFS). Он носит такое название, потому что предпочитает глубину и не пытается найти кратчайшее решение. Это происходит потому, что мы использовали структуру данных стек для реализации frontier . Мы всегда вставляем новые состояния в конец списка и извлекаем оттуда элементы (последний пришел – первым вышел или принцип LIFO). Вот почему новые состояния немедленно исследуются. Представьте, что frontier — это список дел, в котором более новые дела имеют более высокий приоритет — последнее, что вы написали в списке, берется за дело первым.

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

Мы можем реализовать границу по-разному, например, как очередь. Используя эту структуру данных, мы можем вставлять новые состояния в конец списка (как и раньше), но извлекать элементы из начала списка (принцип "первым пришел - первым обслужен" или принцип FIFO).

Неэффективный и дешевый способ сделать это — заменить frontier.pop() на frontier.pop(0). Однако это медленная операция (O(n), если в списке n элементов), и использование определенных структур данных для реализации очереди лучше (O(1) тогда). Для ссылок см. здесь.

Один из способов сделать это — использовать deque:

from collections import deque
class SearchProblemSolverBFS:       
    def solve(self, start_problem):
        frontier = deque([start_problem])
        ...
        
        while frontier and self.solution is None:
            current_state = frontier.popleft()
            
            ...
                
    ...

Это простое изменение создает поиск в ширину (BFS), который фокусируется на кратчайших решениях. Давайте попробуем:

eight_pancakes = PancakeSortingProblem([4, 2, 1, 3, 5, 7, 6, 8])
solver = SearchProblemSolverBFS()
solver.solve(eight_pancakes)
solver.print_solution()

# Output:
# [[4, 2, 1, 3, 5, 7, 6, 8],
# [3, 1, 2, 4, 5, 7, 6, 8],
# [2, 1, 3, 4, 5, 7, 6, 8],
# [1, 2, 3, 4, 5, 7, 6, 8],
# [6, 7, 5, 4, 3, 2, 1, 8],
# [7, 6, 5, 4, 3, 2, 1, 8],
# [1, 2, 3, 4, 5, 6, 7, 8]]

Красиво и коротко! Однако недостатком BFS является то, что он использует больше памяти, что может быть довольно неприятно. Существует также гибрид между BFS и DFS, называемый итеративным углубленным поиском в глубину. Это находит кратчайшее решение, не тратя слишком много памяти, но требует больше времени выполнения.

Заключение

В этой статье мы увидели, как систематически решать задачи поиска, такие как судоку, скользящие головоломки или задачу сортировки блинов, используя поиск по графу.

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

как выглядит цель
и каких состояний мы можем достичь из любого заданного состояния.

Одна интересная вещь, о которой мы не говорили, заключается в том, что некоторые действия могут стоить дороже, чем другие. Мы пока не можем оптимально решить эти проблемы, потому что наш решатель BFS только минимизирует абсолютное число шагов, что означает, что мы использовали, например, неявную постоянную стоимость, равную 1.

В случае с блинами разнородные затраты могут означать, что переворачивание стопки блинов в позиции k может стоить k, интуиция подсказывает, что чем больше блинов, тем сложнее перевернуть стопку блинов. мы переворачиваем сразу. Тогда нам может понадобиться решение, которое минимизирует сумму этих затрат. Есть способы получить оптимальное решение и в этом случае, и мы можем рассмотреть это направление в другой статье. Ключевые слова на данный момент: Поиск с единой ценой (он же Dijkstra) и A*.

Теперь вы можете создавать больше классов задач и решать их, не меняя наши классы решения задач. Простой следующей проблемой может быть проблема подгоревших блинов (а почему бы и нет 🔥🥞). Там у блинов есть подгоревшая и не подгоревшая сторона. Они должны быть не только в порядке, но и подгоревшие стороны всех блинов должны быть внизу. Вы можете выразить состояние как что-то вроде [[4, 0], [2, 0], [1, 1], [3, 1]], что означает, что у нас снова есть блины [4, 2, 1, 3] , но подгоревшая сторона блинов 1 и 3 сверху. Для этого вам нужно лишь немного изменить код класса блина.

Получайте удовольствие от решения головоломок!

Надеюсь, что сегодня вы узнали что-то новое, интересное и полезное. Спасибо за прочтение!

И последнее, если вы

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

почему бы не сделать это по этой ссылке? Это бы мне очень помогло! 😊

Чтобы быть прозрачным, цена для вас не меняется, но около половины абонентской платы идет непосредственно мне.

Большое спасибо, если вы поддержите меня!

Если у вас есть вопросы, пишите мне в LinkedIn!