Что такое поиск в ширину
Поиск в ширину (Breadth first search, BFS)
Алгоритм BFS
Стандартная реализация ВFS помещает каждую вершину графа в одну из двух категорий:
Алгоритм работает следующим образом:
Граф может иметь две разные несвязанные части, поэтому, чтобы убедиться, что мы покрываем каждую вершину, мы также можем запустить алгоритм BFS на каждом узле.
Пример BFS
Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере. Мы используем неориентированный граф с 5 вершинами.
Мы начнем с вершины 0, алгоритм BFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.
Затем мы посещаем элемент в начале очереди, то есть 1, и переходим к соседним узлам. Так как 0 уже был посещен, мы посещаем 2.
У вершины 2 есть соседняя не посещенная вершина 4, поэтому мы добавляем ее в конец очереди и посещаем 3, которая находится в начале очереди.
В очереди остается только 4, поскольку единственный соседний узел с 3, то есть 0, уже посещен. Мы посещаем вершину 4.
Поскольку очередь пуста, мы завершили обход в ширину графика.
BFS псевдокод
Код BFS
Код для алгоритма «поиска в ширину» с примером показан ниже. Код был упрощен, поэтому мы можем сосредоточиться на алгоритме, а не на других деталях.
BFS в C
BFS в C++
BFS Java код (Java code)
BFS в Python
Рекомендуем хостинг TIMEWEB
Рекомендуемые статьи по этой тематике
Алгоритм поиска в ширину на графе
Речь пойдет, как вы уже наверное догадались, о графах, а именно о алгоритме обхода графа в ширину.
Чтобы проникнуться в суть графов, попробуйте решить следующую, довольно известную задачу:
Река, огибающая остров, делится на два рукава, через которые переброшены 7 мостов (см. рисунок ниже). Спрашивается, можно ли совершить такую прогулку, чтобы за один раз перейти все эти мосты, не переходя ни через один мост два или более раз? 
Суть алгоритма поиска в ширину в том, что мы обходим связный граф таким образом, что сначала мы рассматриваем родителя, потом по очереди рассматриваем его предков, потом рассматриваем предков его предков и т.д.(см. рисунок ниже)
Порядок обхода вершин графа.
Можно объяснить алгоритм двумя способами:
Первой вершине (родителю всех остальных вершин) приписываем метку 1. Рассматриваем все смежные с ней вершины и приписываем им метку 2. Дальше рассматриваем окружение вершин с меткой 2 и присваиваем метку 3 всем вершинам, кроме самой главной (родителя всех вершин).
Второй способ объяснения (по моему более понятнее, ну по крайней мере писать его легче) подразумевает под собой имитирование «горения» графа. Т.е. мы поджигаем самую первую вершину, дальше огонь перекидывается на смежные с ней вершины, с них на смежные с ними и т.д. Со смыслом я думаю мы разобрались, однако для меня основной проблемой стала реализация алгоритма. (Программист я не очень то начитанный, поэтому не вините меня).
Скажу сразу, что для реализации данного алгоритма нужны знания: циклов, массивов и очередей. С последним у меня как раз возникли проблемы, т.к. такую структуру данных я, до написания этого алгоритма, не встречал.
Ну напишу я пока что примерную реализацию на С++:
Поясню немного.
Данный код совершает обход по связному графу в ширину. Предполагается, что нам известны данные о смежности вершин ( которые хранятся в матрице смежности matrix[] ) Если вершины i и j смежные, то matrix[i][j]=1 Ну вроде бы все. Профессиональные кодеры, пожалуйста, не ругайтесь за такое кривое объяснение и ещё более кривой код (но я частенько нуждаюсь в кривых, но довольно простых кодах).
От обхода в ширину к алгоритму Дейкстры
Вместо введения
Разбирал свои старые, так сказать, «заметки», и наткнулся на эту. У меня же еще нет инвайта на хабре, подумал я, и решил опубликовать. В этой статье я расскажу, как разобраться в алгоритме Дейкстры поиска кратчайших путей из данной вершины в графе. При чем я приду к нему естественным образом от алгоритма обхода графа в ширину.
В комментариях попросили рассказать подробнее о структуре данных, скрывающейся за priority_queue в STL C++. В конце статьи приводится краткий рассказ и ее реализация.
Обход графа в ширину
Первый алгоритм, который хотелось бы описать, и который однозначно нельзя пропустить — это обход графа в ширину. Что же это такое? Давайте немного отойдем от формального описания графов, и представим себе такую картину. Выложим на земле веревки, пропитанные чем-нибудь горючим, одинаковой длины так, чтобы ни одна из них не пересекалась, но некоторые из них касались концами друг с другом. А теперь подожжем один из концов. Как будет вести себя огонь? Он равномерно будет перекидываться по веревкам на соседние пересечения, пока не загорится все. Нетрудно обобщить эту картину и на трехмерное пространство. Именно так в жизни будет выглядеть обход графа в ширину. Теперь опишем более формально. Пусть мы начали обход в ширину из какой-то вершины V. В следующий момент времени мы будем просматривать соседей вершины V (соседом вершины V назовем вершины, имеющий общее ребро с V). И так до тех пор, пока все вершины в графе не будут просмотрены.
Реализация обхода в ширину
Пусть мы находимся в какой-то вершине в процессе обхода в ширину, тогда воспользуемся очередью, в которую будем добавлять всех соседей вершины, исключая те, в которых мы уже побывали.
В этой реализации g — это список смежных вершин, т.е. в g[u] лежит список смежных вершин с u(в качестве списка использован std::vector), used — это массив, который позволяет понять, в каких вершинах мы уже побывали. Здесь обход в ширину не делает ничего, кроме самого обхода в ширину. Казалось бы, зачем? Однако его можно легко модифицировать для того, чтобы искать то, что нам нужно. Например расстояние и путь от какой-либо вершины до всех остальных. Следует заметить, что ребра не имеют веса, т.е. граф не взвешенный. Приведем реализацию поиска расстояний и путей.
Здесь p — это массив предков, т.е. в p[v] лежит предок вершины v, dist[v] — это расстояние от вершины из которой мы начинали обход, до вершины v. Как восстановить путь? Это сделать довольно легко, просто пройдя по массиву предков нужной нам вершины. Например, рекурсивно:
Кратчайшие пути
Все дальнейшие рассуждения будут верны только если веса ребер не отрицательны.
Теперь перейдем к взвешенным графам, т.е. ребра графа имеют вес. Например длина ребра. Или плата за проход по нему. Или время, которое требуется для прохода по нему. Задача — найти кратчайший путь из одной вершины, в какую-нибудь другую. В этой статье я буду отталкиваться от обхода в ширину, не помню, чтобы видел такой подход где-нибудь еще. Возможно я это пропустил. Итак, давайте посмотрим еще раз на реализацию обхода в ширину, а конкретно на условие добавления в очередь. В обходе в ширину мы добавляем в очередь только те вершины, в которых мы еще не были. Теперь же изменим это условие и будем добавлять те вершины, расстояние до которых можно уменьшить. Очевидно, что очередь опустеет тогда и только тогда, когда не останется ни одной вершины, до которой можно уменьшить расстояние. Процесс уменьшения пути из вершины V, назовем релаксацией вершины V.
Следует заметить, что изначально путь до всех вершин равен бесконечности(за бесконечность возьмем какую-нибудь достаточно большую величину, а именно: такую, что ни один путь не будет иметь длины, большей величины бесконечности). Этот алгоритм напрямую следует из обхода в ширину, и именно до него я дошел сам, когда решал первую в жизни задачу на кратчайшие пути в графе. Стоит упомянуть, что такой способ ищет кратчайший пути от вершины, из которой мы начали алгоритм, до всех остальных. Приведу реализацию:
Почему храним в списке смежности именно такие пары? Чуть позже станет понятно, когда мы усовершенствуем этот алгоритм, но, честно говоря, для данной реализации пары можно хранить и наоборот. Можно немного улучшить добавление в очередь. Для этого стоит завести массив bool, в котором будем помечать, находится ли сейчас вершина, которою нужно прорелаксировать, в очереди.
Если присмотреться, то этот алгоритм очень похож на алгоритм Левита, но все-таки это не он, хотя в худшем случае работает за ту же асимптотику. Давайте грубо оценим это. В худшем случае нам придется проводить релаксацию каждый раз, когда мы проходим по какому-либо ребру. Итого O(n * m). Оценка довольно грубая, но на начальном этапе этого вполне хватит. Стоит так же заметить, что это именно худший случай, а на практике даже такая реализация работает довольно быстро. А теперь, самое интересное!… барабанная дробь… Улучшим наш алгоритм до алгоритма Дейксты!
Алгоритм Дейкстры
Теперь дело осталось за малым, понять как эффективно искать вершину с минимальным расстоянием до нее. Для этого воспользуемся очередью с приоритетами (куча, heap). В stl есть класс, который реализует ее и называется priority_queue. Приведу реализацию, которая, опять же, напрямую следует из предыдущего(описанного в этой статье) алгоритма.
Скорее всего не совсем понятно, что здесь происходит. Начнем с объявления очереди с приоритетами. Здесь первый аргумент шаблона — данные, которые хранятся в очереди, а конкретно пары вида (расстояние до вершины, номер вершины), второй аргумент шаблона — это контейнер, в котором будут храниться данные, третий аргумент, компаратор(находится, кстати, в заголовочном файле functional). Почему нам нужен какой-то другой компаратор? Потому что при стандартном объявлении priority_queue >, доставать получится только те вершины, расстояние до которых максимально, а нам-то нужно совсем наоборот. Асимптотика такого решения поставленной задачи O(n * log(n) + m * log(n)).
Действительно, всего у нас n релаксаций, а вершину с минимальной длиной пути до нее, мы ищем за log(n) (именно такая асимптотика у стандартной очереди с приоритетами stl). Так же следует заметить, что у нас может получится так, что мы добавили в очередь одну и ту же вершину, но с разными путями до нее. Например, мы провели релаксацию из вершины A, у которой в соседях вершина C, а потом провели релаксацию из вершины B, у которой так же в соседях вершина C, для ухода от проблем, связанных с этим, будем просто пропускать те вершины, которые мы достали из очереди, но расстояние из очереди до которых не актуально, т.е. больше, чем текущее кратчайшее. Для этого в реализации присутствует строчка if (u.first > dist[u.second]) continue;.
Вместо заключения
Оказалось, что на самом деле очень легко писать Дейкстру за O(n * log(n) + m * log(n))!
Дополнение
В комментариях попросили рассказать, как можно реализовать своими руками priority_queue.
Пусть перед нами стоит следующая задача (как в алгоритме Дейкстры).
Нужно поддерживать структуру данных, которая удовлетворяет следующим требованиям:
1) Добавление не более, чем за O(log(n)) времени.
2) Удаление минимального элемента не более, чем за O(log(n)) времени.
3) Поиск минимума за O(1) времени.
Оказывается, что этим требованиям удовлетворяет структура данных, которую в русско-язычной литературе обычно называют «куча», в англо-язычной «heap» или «priority queue».
Вообще говоря, куча — это дерево. Давайте рассмотрим свойства этого дерева подробнее. Пусть у нас уже построена куча, тогда определим ее следующим образом — для каждой вершины в куче верно, что элемент в этой вершине не больше, чем элементы в ее потомках. Тогда в корне дерева лежит минимальный элемент, что позволяет нам в дальнейшем искать минимум за O(1).
Теперь доопределим нашу кучу так, чтобы и остальные свойства выполнялись. Назовем уровнем вершины в дереве расстояние от корня до нее. Запретим добавлять новый уровень в куче, до тех пор пока не заполнен целиком предыдущий. Более формально: пусть текущая максимальная высота дерева H, тогда запрещено добавлять вершины на высоту H + 1, пока есть возможность добавить ее на высоту H. Действительно, при таких условиях высота кучи всегда не более, чем O(log(n)).
Осталось научиться добавлять и удалять элементы в кучу.
Реализовывать кучу будем на бинарном дереве, в котором будет не более одной вершины с количеством потомков меньшим двух. Дерево будем хранить в массиве, тогда потомки вершины на позиции pos, будут лежать на позициях 2 * pos и 2 * pos + 1, а родитель будет лежать на позиции pos / 2.
Добавлять элемент будем на первое возможное вакантное место на текущем максимальном уровне, затем выполнять операцию, которая называется «просеивание вверх». Это значит, что пока родитель добавленного элемента больше, чем сам элемент, то поменять позиции добавленного элемента и родителя, повторять рекурсивно до корня. Докажем, что при этом не нарушаются свойства кучи. Это просто, так как текущий элемент меньше, чем родитель, то он так же и меньше, чем все потомки родителя.
Удалять минимальный элемент будем следующим образом: сначала поменяем местами корень дерева с последним элементом на максимальном уровне, затем удалим вершину, в которой был этот элемент (теперь там будет минимум). Свойства кучи после этого нарушатся, а чтобы их восстановить нужно выполнить операцию, которая называется «просеивание вниз». Начинаем от корня рекурсивно: для текущего элемента находим из потомков минимальный, меняем местами с текущим элементом, рекурсивно запускаемся для вершины, с которой поменяли текущий элемент. Заметим, что после этой операции, свойства кучи выполняются.
Так как высота дерева O(log(n)), то добавление и удаление будет работать за O(log(n)).
Обход графа: поиск в глубину и поиск в ширину простыми словами на примере JavaScript
Доброго времени суток.
Что такое обход графа?
Простыми словами, обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин. Связи (линии, соединяющие вершины) называются направлениями, путями, гранями или ребрами графа. Вершины графа также именуются узлами.
Двумя основными алгоритмами обхода графа являются поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).
Несмотря на то, что оба алгоритма используются для обхода графа, они имеют некоторые отличия. Начнем с DFS.
Поиск в глубину
DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины (точки, места) в определенном направлении (по определенному пути) до тех пор, пока не достигнем конца пути или пункта назначения (искомой вершины). Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад (к точке разветвления или расхождения путей) и идем по другому маршруту.
Давайте рассмотрим пример. Предположим, что у нас есть ориентированный граф, который выглядит так:
Мы находимся в точке «s» и нам нужно найти вершину «t». Применяя DFS, мы исследуем один из возможных путей, двигаемся по нему до конца и, если не обнаружили t, возвращаемся и исследуем другой путь. Вот как выглядит процесс:
Здесь мы двигаемся по пути (p1) к ближайшей вершине и видим, что это не конец пути. Поэтому мы переходим к следующей вершине.
Мы достигли конца p1, но не нашли t, поэтому возвращаемся в s и двигаемся по второму пути.
Достигнув ближайшей к точке «s» вершины пути «p2» мы видим три возможных направления для дальнейшего движения. Поскольку вершину, венчающую первое направление, мы уже посещали, то двигаемся по второму.
Мы вновь достигли конца пути, но не нашли t, поэтому возвращаемся назад. Следуем по третьему пути и, наконец, достигаем искомой вершины «t».
Так работает DFS. Двигаемся по определенному пути до конца. Если конец пути — это искомая вершина, мы закончили. Если нет, возвращаемся назад и двигаемся по другому пути до тех пор, пока не исследуем все варианты.
Мы следуем этому алгоритму применительно к каждой посещенной вершине.
Необходимость многократного повторения процедуры указывает на необходимость использования рекурсии для реализации алгоритма.
Заметка: этот специальный DFS-алгоритм позволяет проверить, возможно ли добраться из одного места в другое. DFS может использоваться в разных целях. От этих целей зависит то, как будет выглядеть сам алгоритм. Тем не менее, общая концепция выглядит именно так.
Анализ DFS
Давайте проанализируем этот алгоритм. Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное O(V + E).
Краткое объяснение того, что означает V+E:
V — общее количество вершин. E — общее количество граней (ребер).
Может показаться, что правильнее использовать V*E, однако давайте подумаем, что означает V*E.
V*E означает, что применительно к каждой вершине, мы должны исследовать все грани графа безотносительно принадлежности этих граней конкретной вершине.
С другой стороны, V+E означает, что для каждой вершины мы оцениваем лишь примыкающие к ней грани. Возвращаясь к примеру, каждая вершина имеет определенное количество граней и, в худшем случае, мы обойдем все вершины (O(V)) и исследуем все грани (O(E)). Мы имеем V вершин и E граней, поэтому получаем V+E.
Далее, поскольку мы используем рекурсию для обхода каждой вершины, это означает, что используется стек (бесконечная рекурсия приводит к ошибке переполнения стека). Поэтому пространственная сложность составляет O(V).
Теперь рассмотрим BFS.
Поиск в ширину
BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. Это означает следующее:
Вместо следования по пути, BFS подразумевает посещение ближайших к s соседей за одно действие (шаг), затем посещение соседей соседей и так до тех пор, пока не будет обнаружено t.
Чем DFS отличается от BFS? Мне нравится думать, что DFS идет напролом, а BFS не торопится, а изучает все в пределах одного шага.
Далее возникает вопрос: как узнать, каких соседей следует посетить первыми?
Для этого мы можем воспользоваться концепцией «первым вошел, первым вышел» (first-in-first-out, FIFO) из очереди (queue). Мы помещаем в очередь сначала ближайшую к нам вершину, затем ее непосещенных соседей, и продолжаем этот процесс, пока очередь не опустеет или пока мы не найдем искомую вершину.
Анализ BFS
Может показаться, что BFS работает медленнее. Однако если внимательно присмотреться к визуализациям, можно увидеть, что они имеют одинаковое время выполнения.
Очередь предполагает обработку каждой вершины перед достижением пункта назначения. Это означает, что, в худшем случае, BFS исследует все вершины и грани.
Несмотря на то, что BFS может казаться медленнее, на самом деле он быстрее, поскольку при работе с большими графами обнаруживается, что DFS тратит много времени на следование по путям, которые в конечном счете оказываются ложными. BFS часто используется для нахождения кратчайшего пути между двумя вершинами.
Таким образом, время выполнения BFS также составляет O(V + E), а поскольку мы используем очередь, вмещающую все вершины, его пространственная сложность составляет O(V).
Аналогии из реальной жизни
Если приводить аналогии из реальной жизни, то вот как я представляю себе работу DFS и BFS.
Когда я думаю о DFS, то представляю себе мышь в лабиринте в поисках еды. Для того, чтобы попасть к цели мышь вынуждена много раз упираться в тупик, возвращаться и двигаться по другому пути, и так до тех пор, пока она не найдет выход из лабиринта или еду.
Упрощенная версия выглядит так:
В свою очередь, когда я думаю о BFS, то представляю себе круги на воде. Падение камня в воду приводит к распространению возмущения (кругов) во всех направлениях от центра.
Упрощенная версия выглядит так:
Выводы
Оптимизация поиска в ширину: как обработать граф с 10 миллиардами состояний
Пару месяцев назад мне наконец пришлось признать, что я недостаточно умён, чтобы пройти некоторые уровни головоломки Snakebird. Единственным способом вернуть себе часть самоуважения было написание солвера. Так я мог бы притвориться, что создать программу для решения головоломки — это почти то же самое, что и решить её самому. Код получившейся программы на C++ выложен на Github. Основная часть рассматриваемого в статье кода реализована в search.h и compress.h. В этом посте я в основном буду рассказывать об оптимизации поиска в ширину, который бы потребовал 50-100 ГБ памяти, чтобы он уместился в 4 ГБ.
Позже я напишу ещё один пост, в котором будет описана специфика игры. В этом посте вам нужно знать, что мне не удалось найти никаких хороших альтернатив грубому перебору (brute force), потому что ни один из привычных трюков не сработал. В игре множество состояний, потому что есть куча подвижных или толкаемых объектов, при этом важна форма некоторых из них, которая может меняться со временем. Не было никакой пригодной консервативной эвристики для алгоритмов наподобие A*, позволяющих сузить пространство поиска. Граф поиска был ориентированным и заданным неявно, поэтому одновременный поиск в прямом и обратном направлении оказался невозможным. Единственный ход мог изменить состояние множеством несвязанных друг с другом способов, поэтому не могло пригодиться ничего наподобие хеширования Зобриста.
Приблизительные подсчёты показали, что в самой большой головоломке после устранения всех симметричных положений будет порядка 10 миллиардов состояний. Даже после упаковки описания состояний с максимальной плотностью размер состояния составлял 8-10 байт. При 100 ГБ памяти задача оказалась бы тривиальной, но не для моей домашней машины с 16 ГБ памяти. А поскольку Chrome нужно из них 12 ГБ, мой настоящий запас памяти ближе к 4 ГБ. Всё, что будет превышать этот объём, придётся сохранять на диск (старый и ржавый винчестер).
Как уместить 100 ГБ данных в 4 ГБ ОЗУ? Или а) состояния нужно сжать в 1/20 от их исходного, и так уже оптимизированного размера, или б) алгоритм должен иметь возможность эффективного сохранения состояний на диск и обратно, или в) сочетание двух вышеприведённых способов, или г) мне нужно купить больше ОЗУ или арендовать на несколько дней мощную виртуальную машину. Вариант Г я не рассматривал, потому что он слишком скучный. Варианты А и В были исключены после proof of concept с помощью gzip: фрагмент описания состояний размером 50 МБ сжался всего до 35 МБ. Это примерно по 7 байт на состояние, а мой запас памяти рассчитан примерно на 0,4 байта на состояние. То есть оставался вариант Б, даже несмотря на то, что поиск в ширину казался довольно неудобным для хранения на вторичных накопителях.
Содержание
Это довольно длинный пост, поэтому вот краткий обзор последующих разделов:
Поиск в ширину «по учебнику»
Как выглядит поиск в ширину, и почему в нём не стоит использовать диск? До этого небольшого проекта я рассматривал только варианты формулировок «из учебников», например, такие:
В процессе создания программой новых узлов-кандидатов каждый узел проверяется с хеш-таблицей уже посещённых узлов. Если он уже есть в хеш-таблице, то узел игнорируется. В противном случае он добавляется и в очередь, и в хеш-таблицу. Иногда в реализациях информация «visited» заносится в узлы, а не в стороннюю таблицу; но это рискованная оптимизация и она совершенно невозможна, если граф задан неявно.
Почему использование хеш-таблицы проблематично? Потому что хеш-таблицы склонны к созданию совершенно случайного паттерна доступа к памяти. Если они этого не делают, то это плохая хеш-функция, и хеш-таблица скорее всего будет иметь низкую производительности из-за коллизий. Этот случайный паттерн доступа может вызывать проблемы с производительностью, даже если данные умещаются в памяти: доступ к огромной хеш-таблице с большой вероятностью будет вызывать промахи кэша и буфера ассоциативной трансляции (TLB). Но что если значительная часть данных находится на диске, а не в памяти? Последствия будут катастрофическими: что-то порядка 10 мс на одну операцию поиска.
При 10 миллиардах уникальных состояний только для доступа к хеш-таблице нам понадобится около четырёх месяцев ожидания дискового ввода-вывода. Это нам не подходит; задачу совершенно точно нужно преобразовать так, чтобы программа могла обрабатывать большие пакеты данных за один проход.
BFS с сортировкой и слиянием
Если бы мы стремились максимально объединять операции доступа к данным в пакеты, то какой бы была максимально достижимая приблизительность? Поскольку программа не знает, какие узлы обрабатывать в слое глубины N+1 до полной обработки слоя N, кажется очевидным, что нужно выполнять дедупликацию состояний по крайней мере один раз за глубину.
Если мы одновременно работаем с целым слоем, то можно отказаться от хеш-таблиц и описать множество visited и новые состояния как какие-нибудь отсортированные потоки (например, как файловые потоки, массивы, списки). Мы можем тривиально найти новое множество visited с помощью объединения множеств потоков и столь же тривиально найти множество todo с помощью разности множеств.
Две операции со множествами можно объединить, чтобы они работали за один проход с обоими потоками. По сути мы заглядываем в оба потока, обрабатываем меньший элемент, а затем продвигаемся вперёд по потоку, из которого был взят элемент (или по обоим потокам, если элементы в их начале одинаковы). В обоих случаях мы добавляем элемент в новое множество visited. Затем продвигаемся вперёд по потоку новых состояний, а также добавляем элемент в новое множество todo:
Паттерн доступа к данным теперь совершенно линеен и предсказуем, на всём протяжении слияния нет никаких произвольных доступов. Поэтому задержка операций с диском становится нам не важной, и единственное, что остаётся важным — пропускная способность.
Как будет выглядеть теоретическая производительность при упрощённом распределении данных по 100 уровням глубины, в каждом из которых есть по 100 миллионов состояний? Усреднённое состояние будет считываться и записываться 50 раз. Это даёт 10 байт/состояние * 5 миллиардов состояний * 50 = 2,5 ТБ. Мой жёсткий диск предположительно может выполнять чтение и запись со средней скоростью 100 МБ/с, то есть на ввод-вывод в среднем уйдёт (2 * 2,5 ТБ) / (100 МБ/с) =
13 часов. Это на пару порядков меньше, чем предыдущий результат (четыре месяца)!
Стоит также заметить, что эта упрощённая модель не учитывает размер новых сгенерированных состояний. Перед этапом слияния их нужно хранить в памяти для сортировки + дедупликации. Мы рассмотрим это в разделах ниже.
Сжатие
Во введении я сказал, что в первоначальных экспериментах сжатие состояний не выглядело многообещающим, и показатель сжатия равен всего 30%. Но после внесения изменений в алгоритм состояния стали упорядоченными. Их должно быть намного проще сжать.
Чтобы протестировать эту теорию, я использовал zstd с головоломкой из 14,6 миллионов состояний, каждое состояние которой имело размер 8 байт. После сортировки они сжались в среднем до 1,4 байта на состояние. Это походит на серьёзный шаг вперёд. Его недостаточно, чтобы выполнять всю программу в памяти, но он может снизить время ввода-вывода диска всего до пары часов.
Можно ли как-то улучшить результат современного алгоритма сжатия общего назначения, если мы что-то знаем о структуре данных? Можно быть практически уверенными в этом. Хорошим примером этого является формат PNG. Теоретически сжатие — это просто стандартный проход Deflate. Но вместо сжатия сырых данных изображение сначала преобразуется с помощью фильтров PNG. Фильтр PNG по сути является формулой для предсказания значения байта сырых данных на основании значения того же байта в предыдущей строке и/или того же байта предыдущего пикселя. Например, фильтр «up» преобразует каждый байт вычитанием из него при сжатии значения предыдущей строки, и выполняя противоположную операцию при распаковке. Учитывая типы изображений, для которых используется PNG, результат почти всегда будет состоять из нулей или чисел, близких к нулю. Deflate может сжимать такие данные намного лучше, чем сырые данные.
Можно ли применить подобный принцип к записям состояний BFS? Похоже, что это должно быть возможно. Как и в случае с PNG, у нас есть постоянный размер строки, и мы можем ожидать, что соседние строки окажутся очень схожими. Первые пробы с фильтром вычитания/прибавления, за которым выполнялся zstd, привели к улучшению показателя сжатия ещё на 40%: 0,87 байт на состояние. Операции фильтрации тривиальны, поэтому с точки зрения потребления ресурсов ЦП они практически «бесплатны».
Мне не было ясно, можно ли внести ещё какие-то улучшения, или это является практическим пределом. В данных изображений можно логично ожидать, что соседние байты одной строки будут схожи. Но в данных состояний такого нет. Но на самом деле чуть более сложные фильтры всё равно могут улучшить результаты. В конце концов я пришёл к такой системе:
Допустим, у нас есть соседние строки R1 = [1, 2, 3, 4] и R2 = [1, 2, 6, 4]. При выводе R2 мы сравниваем каждый байт с тем же байтом предыдущей строки, и 0 будет обозначать совпадение, а 1 — несовпадение: diff = [0, 0, 1, 0]. Затем мы передаём эту битовую карту, закодированную как VarInt, за которой следуют только байты, не совпавшие с предыдущей строкой. В этом примере мы получим два байта 0b00000100 6. Сам по себе этот фильтр сжимает эталонные данные до 2,2 байт / состояние. Но скомбинировав фильтр + zstd, мы снизили размер данных до 0,42 байт / состояние. Или, если сказать иначе, это составляет 3,36 бит на состояние, что всего немного больше наших примерных вычисленных показателей, необходимых для того, чтобы все данные уместились в ОЗУ.
На практике показатели сжатия улучшаются, потому что отсортированные множества становятся плотнее. Когда поиск достигает точки, где память начинает вызывать проблемы, показатели сжатия могут становиться намного лучше. Самая большая проблема заключается в том, что в конце мы получаем 4,6 миллиардов состояний visited. После сортировки эти состояния занимают 405 МБ и сжимаются по представленной выше схеме. Это даёт нам 0,7 бита на состояние. В конце концов сжатие и распаковка занимают примерно 25% от времени ЦП программы, но это отличный компромисс за снижение потребления памяти в сто раз.
Представленный выше фильтр кажется немного затратным из-за заголовка VarInt в каждой строке. Похоже, что это легко усовершенствовать ценой малых затрат ЦП или небольшого повышения сложности. Я попробовал несколько разных вариантов, транспонирующих данных в порядок по столбцам, или записывающих битовые маски более крупными блоками, и т.д. Эти варианты сами по себе давали гораздо более высокие показатели сжатия, но проявляли себя не так хорошо, когда выходные данные фильтра сжимались zstd. И это не было какой-то ошибкой zstd, результаты с gzip и bzip2 оказались похожими. У меня нет каких-то особо гениальных теорий о том, почему этот конкретный тип кодирования оказался гораздо лучше в сжатии, чем другие варианты.
Ещё одна загадка: показатель сжатия оказался намного лучше, когда данные сортируются little-endian, а не big-endian. Изначально я подумал, что так получается, потому что в сортировке little-endian появляется больше ведущих нулей при битовой маске, закодированной VarInt. Но это отличие сохраняется даже с фильтрами, у которых нет таких зависимостей.
(Есть множество исследований по сжатию отсортированных множеств целых чисел, ведь они являются базовыми строительными блоками поисковых движков. Однако я не нашёл много информации о сжатии отсортированных записей постоянной длины, и не хотел гадать, представляя данные как целочисленные значения с произвольной точностью.)
Ой-ёй, я сжульничал!
Вы могли заметить, что представленные выше реализации BFS в псевдокоде возвращают только булевы значения — решение найдено/не найдено. Это не особо полезно. В большинстве случаев нам необходимо будет создать список точных шагов решения, а не просто сообщить о наличии решения.
Поначалу кажется, что эту проблему решить легко. Вместо сбора множеств состояний нужно собирать связи состояний с родительскими состояниями. Тогда после нахождения решения можно просто вернуться назад по списку родительских решений от конца к началу. Для решения на основе хеш-таблицы это будет выглядеть примерно так:
К сожалению, это уничтожит все преимущества сжатия, полученные в предыдущем разделе; в основе их лежит предположение о том, что соседние строки очень похожи. Когда мы просто смотрим на сами состояния, это справедливо. Но нет никаких причин полагать, что это будет истинно для родительских состояний; по сути, они являются случайными данными. Во-вторых, решение с сортировкой + слиянием должно считывать и записывать все просмотренные состояния на каждой итерации. Для сохранения связки состояния/родительского состояния нам придётся считывать и записывать на диск при каждой итерации все эти плохо сжимаемые данные.
Сортировка + слияние со множественным выводом
В самом конце, при возврате назад по решению, программе нужны будут только связки состояний/родительских состояний, Следовательно, мы можем параллельно хранить две структуры данных. Visited по-прежнему будет оставаться множеством посещённых состояний, как и раньше заново вычисляемым во время слияния. Parents — это по большей мере отсортированный список пар состояния/родительского состояния, которые не переписываются. После каждой операции слияния к parents добавляется пара «состояние + родительское состояние».
Это позволяет нам пользоваться преимуществами обоих подходов с точки зрения времени выполнения и рабочих множеств, но требует больше вторичного пространства хранения. Кроме того, оказывается, что в дальнейшем по другим причинам будет полезной отдельная копия посещённых состояний, сгруппированная по глубине.
Своппинг
В псевдокоде игнорируется и другая деталь: в нём нет явного кода для дискового ввода-вывода, а присутствует только абстрактный интерфейс Stream. Stream может быть файловым потоком или массивом внутри памяти, но мы игнорировали эту подробность реализации. Вместо этого псевдокод занимается созданием паттерна доступа к памяти, позволяющего оптимально использовать диск. В идеальном мире этого было бы достаточно, и остальным могла бы заняться подсистема виртуальной памяти ОС.
Но этого не происходит, по крайней мере, в Linux. В какой-то момент (до того, как рабочее множество данных удалось сжать до размеров памяти) я добился того, чтобы программа выполнялась примерно за 11 часов, а данные сохранялись в основном на диск. Затем я сделал так, чтобы программа использовала анонимные страницы, а не хранимые в файлах, и выделил на том же диске файл подкачки достаточного размера. Однако спустя три дня программа прошла всего четверть пути, и всё равно со временем становилась медленнее. По моим оптимистичным оценкам она должна была закончить работу за 20 дней.
Уточню — это был тот же код и точно тот же паттерн доступа. Единственное, что изменилось — память сохранялась не как явный дисковый файл, а как своп. Почти не требует доказательств тот факт, что своппинг совершенно рушит производительность в Linux, в то время как обычный файловый ввод-вывод этого не делает. Я всегда предполагал, что так происходит из-за того, что программы склонны считать ОЗУ памятью с произвольным доступом. Но здесь не тот случай.
Оказывается, что страницы с сохранением файлов и анонимные страницы обрабатываются подсистемой виртуальной машины по-разному. Они хранятся в отдельных кэшах LRU с разными политиками истечения срока хранения; кроме того, похоже, что они имеют разные свойства упреждающего чтения/загрузки.
Теперь я знаю: своппинг в Linux скорее всего не будет хорошо работать даже в оптимальных условиях. Если части адресного пространства скорее всего будут выгружаться на какое-то время на диск, то лучше сохранять их вручную в файлы, чем доверять свопу. Я осуществил это, реализовав собственный класс векторов, который изначально работает только в памяти, а после превышения определённого порога размера переключается на mmap во временный отдельный файл.
Сжатие новых состояний перед слиянием
В упрощённой модели производительности мы предполагали, что на каждую глубину будет приходиться 100 миллионов новых состояний. Оказалось, что это не очень далеко от реальности (в самой сложной головоломке максимум 150 с лишним миллионов уникальных новых состояний на одном слое глубины). Но измерять нужно не это; рабочее множество до слияния связано не только с уникальными состояниями, но и со всеми состояниями, выведенными для этой итерации. Этот показатель достигает величины в 880 миллионов выходных состояний на слой глубины. Эти 880 миллионов состояний а) нужно обрабатывать при паттерне случайного доступа для сортировки, б) нельзя эффективно сжать из-за отсутствия сортировки, в) нужно хранить вместе с родительским состоянием. Это рабочее множество составляет примерно 16 ГБ.
Очевидное решение: использовать некую внешнюю сортировку. Просто записать все состояния на диск, выполнить внешнюю сортировку, провести дедупликацию, а затем как обычно выполнить слияние. Поначалу я использовал это решение, и хотя оно по большей мере устраняло проблему А, но никак не справлялось с Б и В.
В конечном итоге я воспользовался альтернативным подходом: собрал состояния в массив в памяти. Если массив становится слишком большим (например больше 100 миллионов элементов), то он сортируется, дедуплицируется и сжимается. Это даёт нам пакет отсортированных прогонов состояний, и внутри каждого прогона нет дубликатов, но они возможны между прогонами. Фундаментально код для слияния новых и посещённых состояний остаётся таким же; он по-прежнему основан на постепенном проходе по потокам. Единственное отличие заключается в том, что вместо прохода всего по двум потокам существует отдельный поток для каждого из отсортированных прогонов новых состояний.
Разумеется, показатели сжатия этих прогонов 100 миллионов состояний не так хороши, как у сжатия множества всех посещённых состояний. Но даже при таких показателях оно значительно снижает объём и рабочего множества, и требования к дисковому вводу-выводу. Нужно немного больше ресурсов ЦП для обработки очереди потоков с приоритетом, но всё равно это отличный компромисс.
Экономия пространства на родительских состояниях
На этом этапе подавляющее большинство пространства, занимаемого программой, тратится на хранение родительских состояний, чтобы мы могли после нахождения решения воссоздать его процесс. Скорее всего, их вряд ли можно хорошо сжать, но может быть, существует какой-то компромисс между ЦП и памятью?
Нам нужно связать состояние S’ на глубине D+1 с его родительским состоянием S на глубине D. Если мы сможем проитерировать все возможные родительские состояния S’, то у нас получится проверить, появляется ли какое-нибудь из них на глубине D во множестве visited. (Мы уже создали множество visited, сгруппированное по глубинам как удобный побочный продукт вывода связок состояния/родительского состояния при слиянии). К сожалению, для этой задачи такой подход не сработает; нам попросту слишком трудно сгенерировать все возможные состояния S для заданного S’. Впрочем, для многих других задач поиска такое решение может и сработать.
Если мы можем генерировать переходы между состояниями только вперёд, но не назад, то почему бы тогда не сделать только это? Давайте итеративно обойдём все состояния на глубине D и посмотрим, какие выходные состояния у них получаются. Если какое-то состояние на выходе даёт S’, то мы нашли подходящее S. Проблема этого плана в том, что он увеличивает общее потребление ресурсов процессора программой на 50%. (Не на 100%, потому что в среднем мы найдём S, просмотрев половину состояний на глубине D).
Поэтому мне не нравится не один из предельных случаев, но здесь, по крайней мере, возможен компромисс между ЦП/памятью. Существует ли более приемлемое решение где-то посередине? В конце концов я решил хранить не пару (S’, S), а пару (S’, H(S)), где H — 8-битная хеш-функция. Чтобы найти S для заданного S’, мы снова итеративно обходим все состояния на глубине D. Но прежде чем делать что-то другое, вычислим тот же хеш. Если выходной результат не соответствует H(S), то это не то состояние, которое мы ищем, и мы можем просто его пропустить. Эта оптимизация означает, что затратные повторные вычисления нужно выполнять только для 1/256 состояний, что составляет незначительное повышение нагрузки на ЦП, и в то же время снижает объём памяти для хранения родительских состояний с 8-10 байт до 1 байта.
Что не сработало или может не сработать
В предыдущих разделах мы рассмотрели последовательность высокоуровневых оптимизаций, которые сработали. Я пробовал и другие вещи, которые не сработали, или которые я нашёл в литературе, но решил, что в этом конкретном случае они не подойдут. Вот их неполный список.
На этом этапе я не вычисляю повторно всё множество visited при каждой итерации. Вместо этого оно хранилось как множество отсортированных прогонов, и эти прогоны время от времени ужимались. Преимущество такого подхода заключается в меньшем количестве записей на диск и ресурсов ЦП, затрачиваемых на сжатие. Недостаток — повышенная сложность кода и пониженный показатель сжатия. Изначально я думал, что подобная схема имеет смысл, ведь в моём случае операции записи более затратны, чем считывание. Но в конечном итоге показатель сжатия оказался больше в два раза. Преимущества такого компромисса неочевидны, поэтому в результате я вернулся к более простому виду.
Уже проводились небольшие исследования о выполнении объёмного поиска в ширину для неявно заданных графов во вторичном хранилище, начать изучение этой темы можно с этой статьи 2008 года. Как можно догадаться, идея выполнения дедупликации совместно с сортировкой + слиянием во вторичном хранилище не нова. Удивительно в этом то, что открыта она была только в 1993 году. Довольно поздно! Существуют более поздние предложения по поиску в ширину во вторичном хранилище, которые не требуют этапа сортировки.
Одно из них заключалось в том, чтобы привязать состояния к целым числам, и хранить в памяти битовую карту посещённых состояний. В моём случае это совершенно бесполезно, потому что размеры кодируемых по сравнению с действительно достижимыми пространствами состояний очень отличаются. И я очень сомневаюсь, что существуют интересные задачи, в которых подобный подход сработал бы.
Ещё одна серьёзная альтернатива основывается на временных хеш-таблицах. Посещённые состояния хранятся без сортировки в файле. Сохраняем выходные данные, полученные из глубины D в хеш-таблицу. Затем итеративно обходим посещённые состояния и ищем их в хеш-таблице. Если элемент найден в хеш-таблице, то удаляем его. После итеративного обхода всего файла в нём останутся только недублируемые элементы. Затем их добавляют к файлу и используют для инициализации списка todo для следующей итерации. Если количество выходных данных так велико, что хеш-таблица не помещается в памяти, то и файлы, и хеш-таблицы можно разбить на части, пользуясь одинаковым критерием (например, верхними битами состояния), и обрабатывать каждую часть по отдельности.
Хоть и существуют бенчмарки, показывающие, что подход на основе хешей примерно на 30% быстрее, чем сортировка + слияние, но, похоже, что в них не учитывается сжатие. Я просто не увидел, как отказ от преимуществ сжатия может оправдать себя, поэтому не стал даже экспериментировать с такими подходами.
Ещё одной стоящей внимания областью исследований показалась оптимизация запросов к базе данных. Похоже. что задача дедупликации сильно связана с join баз данных, в котором тоже есть совершенно такая же дилемма «сортировка против хеширования». Очевидно, что некоторые из этих исследований можно перенести и на задачу поиска. Разница может заключаться в том, что выходные данные join баз данных являются временными, в то время как выходные данные дедупликации BFS сохраняются до конца вычислений. Похоже, это меняет баланс компромиссов: теперь он касается не только наиболее эффективной обработки одной итерации, но и создания наиболее оптимального формата выходных данных для следующей итерации.
Заключение
На этом я завершаю изложение того, что я узнал из проекта, который в общем случае применим и к другим задачам поиска грубым перебором. Сочетание этих трюков позволило снизить объём решений самых сложных головоломок игры с 50-100 ГБ до 500 МБ и плавно увеличивать затраты, если задача превышает доступную память и записывается на диск. Кроме того, моё решение на 50% быстрее, чем наивная дедупликация состояний на основе хеш-таблиц даже для головоломок, помещающихся в памяти.
Игру Snakebird можно приобрести в Steam, Google Play и в App Store. Рекомендую её всем, кому интересны очень сложные, но честные головоломки.