Начало работы с теорией графов

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

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

  • Графическое / узловое мышление и подходы к поисковым задачам
  • Реализация графа с объектно-ориентированным программированием
  • Различные представления графов (списки смежности, матрицы смежности)
  • Типы графов и их реализации: ненаправленные графы, невзвешенные графы, циклические графы, циклические графы.
  • Алгоритм Дейкстры, слабые стороны и альтернативы
  • Приложения теории графов
  • Резюме / ключевые моменты

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

Например, рассмотрим следующую задачу поиска и представим ее в виде неориентированного и невзвешенного графа:

У вас есть замок с двумя цифрами, инициализированный на 00. Каждое движение вы можете перемещать одну из четырех двух вверх или вниз (перемещение 0 вверх - 1, перемещение 0 вниз - 9 - колеса круглые). Существуют «мертвые комбинации», в которых замок будет заблокирован навсегда, если комбинация когда-либо будет равна одному из этих значений. Найдите минимальное количество ходов, необходимое для достижения целевой комбинации без блокировки, или если это вообще возможно.

Мертвые комбинации: [10, 90, 12]. Цель: 11.

Сначала мы строим корень или заголовок графа, что необходимо в сценариях, где нам нужно генерировать граф по ходу. Это 00 или корневой случай, из которого будут сгенерированы варианты ветвления.

Четыре соседа узла 00 - это 01, 10, 90 и 09, соответствующие различным комбинациям движения колес вверх и вниз. У нашего графа уже есть пять узлов и четыре ребра.

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

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

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

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

Однако в этой проблеме с замком графы фактически не нужно было реализовывать. Наиболее распространенный метод реализации полного графа - использование двух объектов (классов), Node, основного строительного блока, и Graph, который состоит из Node и предоставляет интерфейс для доступа к информации о графе в целом.

Например, каждый элемент на приведенном ниже графике может быть представлен в коде как собственный Node. Каждый связан друг с другом через свои Neighbors. Если бы мы вызывали что-то вроде NodeA.Neighbors[1].Neighbors[1].Value, мы получили бы 2. Это потому, что второй индекс соседей узла A - это узел C, а второй индекс соседей узла C - это узел B, который имеет значение 2. Этот вид простота подключения позволяет легко перемещаться.

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

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

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

V = [A, B, C, D, E, F]
E = [AB, AC, BC, CF, CE, DF, EA, FB, FD]

В приведенном выше примере V объявляет существующие узлы, а E объявляет ребро от одного узла к другому (AC означает A → C). Поскольку это компактные и простые обозначения, графики часто будут представлены таким образом.

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

adj_l = {A:[B,C], B:[C], C:[F,E], D:[F], E:[A], F:{B,D]}

Графы, как направленные, так и неориентированные, могут содержать циклы. граф циклов - это граф, состоящий только из одного цикла, в котором нет конечных узлов, и можно бесконечно перемещаться по графу. Циклический граф - это граф, состоящий из нескольких цикловых графов, где обходы могут быть бесконечными, но более сложными.

Например, внутри полного циклического графа A → B → C → D → A - это четырехцикловый граф, а E → F → G → E - трехцикловый граф. Более скрыт еще один четырехцикловый граф, B → E → F → G → B.

Определенные типы циклов в циклических графах или другие компоненты в графах, в которых каждый узел соединен друг с другом, известны как компоненты с сильной связью. Например, E → F → G → E является компонентом сильной связности, потому что каждый из узлов {E, F, G} имеет путь к другому, независимо от направления. B → E → F → G → B также является сильно связной компонентой. С другой стороны, A → B → C → D → A нет, потому что нет связи между составляющими элементами B и D.

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

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

Например, кратчайший путь из S → E - это S → D → F → E, для которого требуется всего три обхода ребер. Однако этот маршрут проходит по очень маленькой, многолюдной улице. В качестве альтернативы, S → A → B → C → E занимает четыре ребра, но проходит большую часть расстояния по шоссе, что снижает общую стоимость. Когда к графику добавляются понятия расстояния и стоимости, он становится взвешенным.

Чтобы реализовать это в нашей существующей структуре для структуры графа, мы можем включить для каждого элемента в Neighbors другое число, описывающее стоимость достижения этого соседа. Например, он может храниться в кортежах [(n, c), (n, c)], где n представляет узел, а c представляет стоимость.

Часто графики также будут представлены в форме матрицы, известной как матрица смежности. Он не такой компактный, как список смежности, но может более естественно представлять взвешенные графы. В матрице каждая строка и столбец представляют узел, а ячейка, расположенная в (x, y), представляет край y → x (или наоборот, это вопрос обозначений). Если ребра нет, значение равно 0. Если есть, то значением является стоимость этого ребра.

Матрицы смежности также имеют преимущество легкого поиска затрат, даже с невзвешенными графами, по сравнению со списками смежности и объектно-ориентированным представлением. Обратите внимание, что неориентированные графы будут иметь симметричные матрицы смежности. Поскольку с матрицами также легче манипулировать, многие операции и алгоритмы с графами обычно реализуются на матрицах смежности.

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

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

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

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

Например, рассмотрим эту сетку узлов, где каждое соединение имеет одинаковую стоимость прохождения; Алгоритм Дейкстры (слегка варьирующийся в зависимости от реализации) будет перебирать все световые узлы, прежде чем достигнет конечного узла E. Это похоже на то, как вылить ведро воды в месте расположения узла S и надеяться, что она в конечном итоге достигнет целевого узла.

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

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

Некоторые приложения теории графов в информатике включают:

  • Моделирование сложных сетей, таких как социальные сети, или моделирование болезни, такой как новый коронавирус. Каждый узел может представлять одного человека или группу людей, а края могут представлять вероятность / легкость передачи. В этой модели мы можем попытаться идентифицировать или сформировать круговые замкнутые графы.
  • Организация и прочее иерархическое. Графики не обязательно должны быть зацикленными и цикличными; они также могут выражать иерархию. Например, если вам нужно создать API для локальной библиотеки для доступа к книгам с различным содержанием, вам нужно создать график. Если вы хотите создать карту для своего веб-сайта, вы должны использовать график. Графические базы данных - это типы баз данных, которые специально полагаются на организованные иерархии графа для хранения данных.
  • Любая проблема, связанная с перемещением агента между многими местами или штатами, скорее всего, хорошо представлена ​​в виде графика. Использование графиков может помочь снизить сложность практически любой проблемы программирования.
  • Такой сервис, как Google Maps, который подскажет вам лучший маршрут, учитывая не только расстояние, но и время движения, высоту, дорожные сборы и т. Д. По сути, это поиск лучшего пути на массивном взвешенном графе (представьте узел через каждые несколько футов или около того, и график, охватывающий Землю).
  • Теория графов участвовала в доказательстве теоремы четырех цветов, которая стала первым принятым математическим доказательством, проведенным на компьютере.
  • В обработке естественного языка - подразделение машинного обучения, которое занимается моделированием языка, взвешенные графические представления слов и текста чрезвычайно ценны, потому что они могут дать представление, например, о словах, принадлежащих схожему кластеру ( яблоки, апельсины) или означают похожие вещи на расстоянии.

Ключевые моменты

  • Графы состоят из набора узлов, также называемых вершинами, и ребер или соединений между узлами.
  • Два представления графов включают списки смежности и матрицы смежности. Последний поддерживает более легкое индексирование и манипулирование, но занимает больше места, чем первый.
  • Полные графы могут быть реализованы с использованием Node объектов, которые имеют значение и набор соседей.
  • Направленные графы имеют направление. Взвешенные графы применяют идею расстояния или стоимости к каждому ребру. Циклические графы содержат циклы, по которым можно бесконечно обходить.
  • Алгоритм Дейкстры используется для нахождения кратчайшего расстояния между двумя узлами взвешенного графа. Обычно он эффективен, но несколько наивен, поэтому существует множество других алгоритмов, предназначенных для поиска наилучшего обхода графа.
  • Графы, как в их реализации, так и в парадигме мышления, могут применяться к очень широкому кругу задач информатики и программирования.