Графы: всегда на связи!

Graphs: Only Connect!

В этой главе мы исследуем: In this chapter, you will learn:

1. Свойства индексированной приоритетной очереди — и больше новых типов данных изобретать в нашей книге не станем. • The indexed min priority queue data type, which is the final data type included in this book.

2. Граф как набор вершин и соединяющих из рёбер. В ориентированном графе рёбра имеют направления, во взвешенном — числовые веса. • How to model a graph using nodes and edges. In a directed graph, the edges have an orientation. In a weighted graph, edges have an associated numeric value.

3. Обход графа вглубину с помощью стека, хранящего план разведки. • How Depth First Search uses a stack to organize searching in a graph.

4. Обход графа вширину, при котором план разведки хранится в очереди. Если выходной узел достижим из входного, обход вглубину вернёт кратчайшее расстояние между ними. • How Breadth First Search uses a queue to search through a graph. If a path exists between a source node and a target node, Breadth First Search will return the shortest path that exists.

5. Поиск цикла — последовательности дуг, выходящей из некоторой вершины, и входящей в неё же — в ориентированном графе. • How to detect whether a directed graph contains a cycle: a sequence of edges starting from, and ending with, a specific node.

6. Топологическую сортировку ориентированного графа, которая строит линеаризацию его узлов — такую последовательность, в которой одна вершина всегда встречается раньше другой, если между ними есть дуга. • How to use Topological Sort in a directed graph to produce a linear ordering of nodes compatible with all dependencies in the directed graph.

7. Задачу поиска кратчайшего пути из входной вершины взвешенного графа ко всем остальным. • How to determine the shortest accumulated path in a weighted graph from one node to all other nodes.

8. Задачу полного поиска кратчайших путей из каждой вершины взвешенного графа к каждой. • How to determine the shortest accumulated path in a weighted graph between any two nodes.

В графе удобно хранить полезную информацию

Graphs Efficiently Store Useful Information

Каждый рассмотренный нами алгоритм решал некоторую задачу обработки информации: ввод данных, вычисление, вывод результата. Неисчислимое множество практических задач можно решить применением какого-нибудь известного алгоритма, если только удастся формализовать постановку и смоделировать данные. Вот три распространённые задачи, которые мы попробуем решить при помощи графов: I’ve covered algorithms for solving common problems in information systems regarding storing and processing data. These algorithms can solve countless real- world problems if only we could properly model these problems. Here are three such problems that I will solve by using graphs:

• Лабиринт — это комнаты и двери соединяющие произвольную пару комнат. Найти кратчайший путь от входа к выходу. • A maze consists of rooms with doorways leading to other rooms. Find the short‐ est path from an entrance to the exit.

• Проект — это набор заданий, причём некоторые задания можно выполнять только после завершения некоторых других заданий. Составить расписание, в котором описано, как последовательно выполнить все задания и тем самым завершить проект. • A project is defined by a collection of tasks, but some tasks require other tasks to complete before they can begin. Assemble a linear schedule that describes the order in which the tasks can be performed to complete the project.

• Карта — это набор дорог различной длины, соединяющих города. Найти кратчайший суммарный путь между двумя заданными городами. • A map contains a collection of highway segments, including their length in miles. Find the shortest traveling distance between any two locations in the map.

Решения каждой из этих задач можно построить в виде алгоритма на графах. Математики уже сотни лет изучают графы, потому что смоделировать связи между данными зачастую не менее важно, чем формализовать сами данные. Граф описывает данные как набор узлов, соединённых рёбрами. Любую связь между двумя элементами данных u и v можно представить ребром e = (u, v). Самих рёбер может быть сколько угодно. Таким способом моделируются самые разные структуры из обыденной жизни; некоторые из них представлены на иллюстрации 7-1. Химические связи между атомами углерода и водорода в структурной формуле молекулы пропана образуют неориентированный граф. Мобильное приложение может показать, как проехать по Нью-Йорку с учётом одностороннего движения на некоторых улицах — с помощью ориентированного графа. Взвешенный граф подходит для атласа автодорог Новой Англии, в котором отмечены расстояния между столицами штатов. Немного арифметики, и становится понятно, что кратчайший путь из Хартфорда, штат Коннектикут, до Бангора, штат Мэн, — 278 миль. Each of these problems can be modeled effectively using graphs, a fundamental con‐ cept studied by mathematicians for centuries. Modeling the relationships between data is often as important as the data values themselves. A graph models information as nodes connected by edges. Any number of edges, e = (u, v), can exist to represent some relationship between nodes u and v. As you can see in Figure 7-1, graphs can model concepts from a variety of application domains. An undirected graph can model the structural relationship between the carbon and hydrogen atoms in the pro‐ pane molecule. A mobile app can provide driving directions in New York City by rep‐ resenting the orientation of one-way streets as a directed graph. A driver’s road atlas can represent the driving distances between New England state capitals as a weighted graph. With a bit of computation, you can see that the shortest driving distance from Hartford, Connecticut, to Bangor, Maine, is 278 miles.

Граф как структура данных — это набор из N различных узлов, каждый из которых снабжён уникальным идентификатором¹. В граф можно добавить ребро, которое соединяет два различных узла, u и v. Ребро записывается в виде пары (u, v), при этом узлы u и v называются вершинами ребра или смежными узлами. A graph is a data type that contains a collection of N distinct nodes, each with a unique label to identify the node.1 You can add an edge to a graph to connect two dif‐ ferent nodes, u and v, with each other. An edge is represented as (u, v), and u and v are called its endpoints. Each edge (u, v) joins u and v together so u is adjacent to v (and, vice versa, v is adjacent to u). 1 A node is often called a vertex, but for this chapter I use the term node to be consistent with networkx.

Иллюстрация 7-1. Различные данные в виде графов

Граф на иллюстрации 7-2 содержит 12 различных узлов и 12 рёбер. Представим, что узел — это остров, а ребро — мост между двумя островами. С острова B2 можно добраться до острова C2, а с острова C2 — до островов B2 И C3. При этом добраться напрямую с острова B2 до острова B3 нельзя. Сначала надо пройти по мосту между B2 и C2, затем — по мосту между C2 и C3, и только потом — по мосту между C3 и B3. Если поизучать схему островов и мостов, можно подобрать цепочку мостов от любого острова «B» до любого острова «C», а вот с островов «A» на остров «B» не попасть, хотя какие-то мосты есть и между островами «A». The graph in Figure 7-2 has 12 unique nodes and 12 edges. Imagine that each node is an island, and the edges are bridges connecting the islands. A traveler can walk from island B2 to island C2 or from island C2 to island B2; however, there is no way for a traveler to walk directly from island B2 to B3. Instead, the traveler can cross the bridge from island B2 to island C2, then cross the bridge from island C2 to island C3, and finally cross the bridge from island C3 to B3. Based on this representation of the islands and its bridges, the traveler can find a sequence of bridges to travel between any of the “B” and “C” islands, but despite the bridges connecting the “A” islands, there is no way to travel from an “A” island to a “B” island.

Иллюстрация 7-2. Неориентированный граф с 12 вершинами и 12 рёбрами

Если есть граф с узлами и рёбрами, часто бывает нужно построить путь от некоторой начальной вершины (например, узла, соответствующего острову B2) к конечной (узлу, соответствующему острову B3), пользуясь при этом только рёбрами графа. Given a graph containing nodes and edges, a common problem is to compute a path from a source node (such as the node representing island B2) to a target node (such as the node representing the island B3) using only the edges contained in the graph.

Путь — это последовательность рёбер, которая начинается в начальной вершине, а заканчивается в конечной. В простом случае каждое ребро — это путь между вершинами этого ребра, но бывает и так, что ребра между двумя узлами нет, а путь — есть. На иллюстрации 7-2 путь между узлами B2 и B3 — это цепочка рёбер (B2, C2), (C2, C3) и (C3, B3). A path is formed by a sequence of edges starting at a source and terminating at a tar‐ get. Naturally, every edge forms a path between its two endpoint nodes, but what about two nodes that do not have an edge to join them together? In Figure 7-2 there is a path from node B2 to B3 by following the sequence of edges (B2, C2), (C2, C3), and then (C3, B3).

Каждое следующее ребро пути должно начинаться тем узлом, в котором заканчивалось предыдущее, поэтому путь можно представить последовательностью посещаемых узлов, например, [B2, C2, C3, B3]. От B2 к B3 есть путь и подлиннее — [B2, C2, C3, C4, B4, B3]. Если путь начинается и заканчивается одним и тем же услом, например, [C4, C5, B5, B4, C4] — это цикл. Узел v называется достижимым из другого узла, u, если существует путь из u в v. Некоторые узлы графа могут быть недостижимы друг из друга, например, граф на иллюстрации 7-2 не имеет пути из A2 в B2. Такой граф называется несвязным, а если между любыми двумя вершинами есть путь, то это связный граф. In a path, each successive edge must start at the node in which the prior edge termi‐ nated. A path can also be represented by listing the sequence of nodes encountered along the way, such as [B2, C2, C3, B3]. Another longer path from B2 to B3 is [B2, C2, C3, C4, B4, B3]. A cycle is a path that starts and ends at the same node, such as [C4, C5, B5, B4, C4]. A node, v, is reachable from another node, u, if there is a path of edges in the graph from u to v. In some graphs, there may be no path between two nodes—for example, there is no path from A2 to B2 in the graph from Figure 7-2. When this happens, the graph is considered to be disconnected. In a connected graph, it is possible to compute a path between any two of its nodes.

In this chapter, I will present three types of graphs: Мы изучим три типа графов:

Неориентированный граф

Если ребро соединяет вершины u и v, u считается смежной с v, а v — смежной с u. Можно считать такое ребро мостом, проходимым в обе стороны. Undirected graph A graph that contains edges (u, v) that connect two nodes such that u is adjacent to v, and v is adjacent to u. This is like a bridge that can be traveled in either direction.

Ориентированный граф

Каждое ребро (u, v) соединяет вершину u с вершиной v, и это значит, что v — смежная с u, но необязательно наоборот. Получается, что ребро имеет направление от u к v, в котором можно было бы пройти по соответствующему мосту (но не обратно). Directed graph A graph that contains edges (u, v), where each edge has a fixed orientation. When the edge (u, v) is in the graph, v is adjacent to u, but the opposite is not true. This is like a one-way bridge that a traveler can use to walk from island u to island v (but not the other direction).

Взвешенный граф

Ребро, соединяющее вершины u и v имеет дополнительное числовое поле — вес — и записывается как (u, v, вес). Граф при этом может быть ориентированным, а может и не быть. Это поле отражает некоторую измеряемую характеристику связи u и v. Это может быть, например, стоимость проезда или расстояние в милях между городами, которым соответствуют узлы u и `v. Weighted graph A graph that contains edges (u, v, weight), where weight is a numeric value associ‐ ated with the edge (note: the underlying graph can either be directed or undirec‐ ted). This weight represents an aspect about the relationship between u and v; for example, weight could represent the physical distance in miles between the loca‐ tions modeled by the nodes u and v.

Все графы в этой главе — простые, то есть не имеют ни дублирующих (соединяющих одну и ту же пару вершин) рёбер, ни петель — рёбер, в которых начальная и конечная вершины совпадают. Рёбра в графе либо все ненаправленные, либо все направленные, — и либо все с весами, либо все без весов. All graphs in this chapter are simple graphs, which means each edge is unique (i.e., there cannot be multiple edges between the same pair of nodes), and there are no self-loops where an edge connects a node with itself. Either a graph contains all undirected edges or it has all directed edges. Similarly, either a graph has all weighted edges or none of the edges have associated weights.

Для нашил алгоритмов понадобится достаточно сложная структура данных, моделирующая абстракцию графа. Хорошо бы, чтобы с соответствующим объектом-графом можно было делать следующее: For the algorithms in this chapter, you need a graph data type that can provide the following functionalities:

• Получать количество узлов N и количество рёбер E данного графа. • Return the number of nodes, N, and the number of edges, E, in the graph.

• Получать полный набор узлов или вершин. • Generate the collection of nodes and edges.

• Для данного узла получить список рёбер или смежных с ним узлов. • Generate the adjacent nodes or edges for a given node.

• Модифицировать граф, добавляя туда узел или ребро. • Add a node or edge to a graph.

• Удалять из графа узел или ребро (вот это нам не понадобится, но для полноты картины хорошо, чтобы так можно было делать). • Remove a node or edge from a graph—this functionality is not essential for the algorithms presented in this chapter, but I include it for completeness.

Среди стандартных библиотек Python есть модуль, реализующий некоторый алгоритм на графах, но он решает ровно одну прикладную задачу и не обладает почти никакими нужными нам свойствами. Нам понадобится куда более мощная сторонняя библиотека для работы с графами, NetworkX (https://networkx.org). Библиотека разрабатывается открыто и распространяется под свободной лицензией. Нам не придётся изобретать колесо: модуль networkx предоставляет великое множество готовых алгоритмов на графах, а вдобавок с этим модулем прекрасно сочетаются библиотеки для визуализации графов. В примере 7-1 показана программа, в которой строится и используется граф с иллюстрации 7-2, и результаты её вывода. Python has no built-in data structure that provides this functionality. Instead of implementing code from scratch, you need to install the NetworkX (https:// networkx.org) open source library to create and manipulate graphs. Doing so ensures you do not waste time reinventing the wheel, plus it gives you access to an impressive number of graph algorithms already implemented by networkx. In addition, net workx seamlessly integrates with other Python libraries to visualize graphs. The pro‐ gram in Listing 7-1 constructs the graph shown in Figure 7-2.

   1 import networkx as nx
   2 G = nx.Graph()                                          # 1
   3 G.add_node('A2')                                        # 2
   4 G.add_nodes_from(['A3', 'A4', 'A5'])                    # 3
   5 G.add_edge('A2', 'A3')                                  # 4
   6 G.add_edges_from([('A3', 'A4'), ('A4', 'A5')])          # 5
   7 
   8 for i in range(2, 6):
   9   G.add_edge(f"B{i}", f"C{i}")                          # 6
  10   if 2 < i < 5:
  11     G.add_edge(f"B{i}", f"B{i+1}")
  12   if i < 5:
  13     G.add_edge(f"C{i}", f"C{i+1}")
  14 
  15 print(G.number_of_nodes(), 'nodes.')                    # 7
  16 print(G.number_of_edges(), 'edges.')
  17 print('adjacent nodes to C3:', list(G['C3']))           # 8
  18 print('edges adjacent to C3:', list(G.edges('C3')))     # 9

12 nodes.
12 edges.
adjacent nodes to C3: ['C2', 'B3', 'C4']
edges adjacent to C3: [('C3', 'C2'), ('C3', 'B3'), ('C3', 'C4')]

• Пример 7-1. Программа, в которой строится граф с иллюстрации 7-2 Listing 7-1. A program that builds the graph in Figure 7-2

1. Создадим новый граф с помощью nx.Graph(). nx.Graph() constructs a new undirected graph.

2. Узел может хранить любой константный объект Python (кроме None). Хорошая идея — хранить строки. A node can be any hashable Python object except None. Strings are a good choice.

3. Метод .add_nodes_from() добавляет сразу несколько узлов. Add multiple nodes from a list using add_nodes_from().

4. Добавим ребро между узлами u и v с помощью метода .add_edge(u, v). Add an edge between two nodes, u and v, with add_edge(u, v).

5. Добавим несколько рёбер с помощью .add_edges_from(). Add multiple edges from a list using add_edges_from().

6. Если вершина добавляемого ребра в графе пока отсутствует, соответствующий узел заводится автоматически. If an edge is added to a graph before its nodes are, the corresponding nodes are automatically added to the graph.

7. Мы можем узнать количество узлов и рёбер графа. A graph can report its number of nodes and edges.

8. Мы можем получить список смежных с v узлов при помощи просто конструкции G[v]. Find the nodes adjacent to v by using the G[v] lookup capability.

9. Мы можем получить список исходящих из v рёбер при помощи G.edges(v). Find the edges adjacent to v by using the G.edges(v) function.

Если задуматься, в какой последовательности нужно возвращать смежные вершины или рёбра, окажется, что в разных случаях порядок может потребоваться разный. Поэтому в последующих алгоритмах мы вообще не будем рассчитывать на то, что такой порядок существует. You might wonder about the order in which adjacent nodes (or edges) are returned when requested. In the subsequent code, when adjacent edges or nodes are requested, you cannot expect that they will be returned in a specific order.

Обход лабиринта вглубину

Using Depth First Search to Solve a Maze

Как написать программу, которая находит выход из лабиринта с иллюстрации 7-3? Лабиринт размером 3 на 5 состоит из 15 комнат, вход в него — сверху, выход — снизу. Перемещаться по лабиринту можно только вертикально или горизонтально между теми комнатами, которые не разделяет стена. Первым делом надо смоделировать лабиринт с помощью неориентированного графа из 15 узлов, каждый из которых, с меткой (строка, столбец), будет обозначать соответствующую комнату лабиринта. Например, вход в лабиринт — это (0, 2), а выход — (2, 2). Затем в эту модель надо добавить рёбра: если между узлами u и v нет стены, в графе должно быть ребро (u, v). Иллюстрация совмещает лабиринт с получившимся графом, оттого особенно заметно, что комнаты лабиринта в точности соответствуют узлам графа. Given a rectangular maze as shown in Figure 7-3, how would you write a program that solves it? The entrance to this 3 x 5 maze consisting of 15 cells is at the top, and the desired exit is at the bottom. To move through the maze, you can only move hori‐ zontally or vertically between rooms that are not blocked by walls. The first step is to model the maze using an undirected graph consisting of 15 nodes, where each node, labeled (row, column), models a cell in the maze. The source of the maze, for example, is labeled (0, 2), and the target is labeled (2, 2). The second step is to add an edge between two nodes (u, v) if their corresponding cells in the maze do not have a wall between them. The resulting graph is shown overlayed with the maze so you can see the one-to-one correspondence between a cell in the maze and a node in the graph.

Так что найти путь между входным узлом (0, 2) и выходным (2, 2) — это то же самое, что пройти исходный лабиринт. Мы посмотрим, как проходить любой такой лабиринт независимо от размеров. Если самому проходить лабиринт, начинаешь исследовать то один, то другой путь, отбрасывая тупиковые, пока наконец один из путей не окажется от входа к выходу. Это, возможно, неочевидно, но человек имеет перед компьютером важное преимущество: он видит лабиринт как целое, и может принимать решения руководствуясь ощущениями, близко ли к выходу лежит предполагаемый путь. Представим себе, что мы угодили в такой лабиринт²), и можем видеть только комнаты, напрямую связанные с той, в которой стоим. В таком положении подход к решению должен быть совсем другим. Finding a path between the source node (0, 2) and target node (2, 2) is equivalent to finding a solution to the original rectangular maze. I will show you a technique for solving any such maze, regardless of its size. If you try to solve this maze on your own, you will explore different paths, discarding those that lead to “dead ends,” until you eventually find a solution. Though you might not realize it, you have a significant advantage because you can see the whole maze at a glance and can make decisions on which paths to explore based on your own sense of how close you are to the final target. Imagine, instead, that you are stuck inside the maze,2 and you can only see the cells that directly connect to the cell in which you stand—these restrictions com‐ pletely change your approach.

Иллюстрация 7-3. Моделирование прямоугольного лабиринта графом

Нам нужен способ проходить лабиринт, пользуясь соответствующим неориентированным графом, как это сделано на иллюстрации 7-4. Случайное порождение таких графов — задача сама по себе интересная³. Let’s develop a strategy to solve a maze using its corresponding undirected graph, as seen in Figure 7-4. These mazes are randomly generated, which is an interesting exer‐ cise all on its own.3

На входе — это узел (0, 2) — мы видим три смежных узла, к каждому из которых ведёт ребро; можно пойти на восток к (0, 3), но запомнить при этом два других направления, (0, 1) и (1, 2) как возможные альтернативы исследования. Узел (0, 3) также имеет три смежных, но мы помним, откуда пришли, так что не возвращаемся туда, где уже были. Из оставшихся двух выбираем, например, южный, (1, 3), а (0, 4) запоминаем как альтернативный. Вот мы и прошли по маршруту, отмеченному на иллюстрации 7-2 серым, — и упёрлись в тупик. Starting from the source (0, 2), you see three adjacent nodes that are connected by edges; you arbitrarily head east to (0, 3) but remember (0, 1) and (1, 2) as poten‐ tial points to explore. Node (0, 3) has three adjacent nodes, but you remember that you came from (0, 2), and you don’t repeat where you’ve already been, so you arbi‐ trarily head south to (1, 3) but remember (0, 4) as a potential point to explore. You have just followed the highlighted path shown in Figure 7-4 and have reached a dead end.

Узел (1, 3) — это тупик, потому что когда мы туда попадаем, мы не видим ни одного смежного не посещённого нами узла. Что делать теперь? На иллюстрации 7-4 кружками обведены узлы, которые были нам доступны, но мы туда не пошли: возможно, если мы вернёмся к одному из этих ранее отмеченных узлов и продолжим обход с него, нам улыбнётся удача? You know (1, 3) is a dead end because there is no adjacent node you have not already seen. What should you do? In Figure 7-4, I circled those nodes you came across but didn’t explore: perhaps your search will be more fruitful if you backtrack to one of these previous nodes and continue searching from there.

2 Which can happen in real-life corn mazes! Cool Patch Pumpkins in Dixon, California, is the largest corn maze in the world, measuring a total 63 acres. It takes several hours to complete. 3 See the ch07.maze program for details.

Иллюстрация 7-4. Обходили лабиринт и упёрлись в тупик

Как превратить наши соображения в алгоритм? Вот примерный его план: Here is a rough sketch of the activity of a graph-searching algorithm that explores a graph starting from a designated source node:

• Будем отмечать каждый посещённый узел. • Mark each node that you visit.

• Найдём все пока не посещённые узлы, смежные с данным. Выберем любой из таких узлов, а остальные добавим в план разведки. Переместимся в этот узел. • Find the adjacent nodes to your current node that have not yet been marked as visited, and arbitrarily select one of these to explore.

• Если упрёмся в тупик, вернёмся к плану разведки — выберем оттуда последний добавленный (и ещё не посещённый) узел и начнём исследование с него. • Go back to the last unmarked node you remembered when you hit a dead end.

• Продолжаем в том же духе до тех пор, пока не окажется, что мы посетили все достижимые узлы. • Continue exploring until all reachable nodes are marked.

Хотелось бы, чтобы по окончании алгоритма мы могли легко построить путь от входного узла до любого достижимого. Результатом работы алгоритма должна быть структура данных с достаточны для решения этой задачи количеством информации. Обычно создают ассоциативный массив node_from[], в котором в ячейке node_from[v] лежит None, если узел v не достижим из входного узла, или узел u, из которого мы попали в v, когда исследовали лабиринт. Для лабиринта с иллюстрации 7-4 node_from[(1, 3)] будет хранить узел (0, 3). Once the search algorithm completes, it should be possible to reconstruct the path from the source node to any node in the graph. To make this possible, the search algorithm must return a structure that contains enough information to support this capability. A common solution is to return a node_from[] structure, where node_from[v] either is None, if v is not reachable from the source node, or it is u, that is, the prior node discovered before exploring v. In Figure 7-4, node_from[(1, 3)] is the node (0, 3).

Алгоритм по нашему плану нельзя реализовать как простой цикл наподобие поиска значения в списке. Нам придётся ввести новую абстракцию — стек — и использовать соответствующую структуру данных. В стеке мы будем хранить план разведки, то есть узлы, которые ещё предстоит исследовать при обходе графа. This sketch of an algorithm cannot be performed within a simple while loop, like when searching a linked list for a value. Instead, I now show how to use the stack abstract data type to maintain the search state while exploring the graph.

Перед обедом в столовой вы наверняка берёте верхний поднос из стопки подносов. Абстракция «стек» имитирует поведение такой стопки. В стеке предусмотрено два действия: «положить значение на стек», .append(значение)⁴, которая добавляет значение на вершину стека, и «снять значение со стека», .pop(), которая атомарно выполняет двойное действие: удаляет значение с вершины стека и возвращает это значение. Эту абстракцию также называют LIFO, по первым буквам словосочетания «Last In, First Out», то есть «последний добавляемый [элемент на стек] первым снимается [с него]».

If you have ever eaten a meal at a cafeteria, you’ve no doubt grabbed the top tray from a stack of trays. The stack data type represents the behavior of such a stack of trays. A stack has a push(value) operation that adds value to become the newest value at the top of the stack, and pop() removes the value at the top of the stack. Another way to describe this experience is “Last in, first out” (LIFO), which is shorthand for “Last [one] in [the stack is the] first [one taken] out [of the stack].” If you push three values, 1, 2, and 3, onto a stack, they will pop off the stack in order 3, 2, and finally 1.

С этого момента я вынужден снова переписать часть примеров и изменить изложение, потому что автор снова демонстрирует «как не надо делать», изобретая искусственную структуру данных вместо уже имеющейся. -- FrBrGeorge 2023-01-18 14:49:44

Абстракцию стека в Python реализует уже знакомый нам тип list: будучи динамическим массивом он, во-первых, позволяет хранить произвольное количество элементов, а во-вторых, за счёт геометрического масштабирования операции по добавлению элемента в конец массива и удалению его оттуда имеют константную сложность. Using the Node linked list data structure from Listing 6-1, the Stack implementation in Listing 7-2 has a push() operation to prepend a value to the front of a linked list. The pop() method removes and returns the first value in a linked list; as you can see, this provides the behavior for a stack. In Stack, the push() and pop() operations per‐ form in constant time, independent of the total number of values in the stack.

Алгоритм обхода вглубину хранит в стеке план разведки — узлы, которые были доступны, но ещё не исследованы при обходе лабиринта. В примере 7-3 приведена возможная реализация такого алгоритма. Слово «вглубь» в названии происходит от того, что в алгоритме мы пытаемся сперва сделать очередной шаг, как если бы выход был в соседней комнате, а другие смежные узлы оставляем на потом. The Depth First Search algorithm uses a stack to keep track of marked nodes it will explore in the future. Listing 7-3 contains a stack-based implementation for Depth First Search. The search strategy is called depth first because it constantly tries to advance forward, always expecting that the solution is just one step away.

Обход лабиринта начинается во входном узле src, который тут же помечается как посещённый (то есть в marked[src] записывается True) и сразу кладётся на стек как текущее окончание маршрута. Всё время работы цикла while в стеке находятся уже посещённые узлы, которые встретились нам на пути к текущему. В цикле узлы снимаются по одному из стека, после чего все не посещённые доселе смежные с данным узлы кладутся обратно на стек — их ещё предстоит исследовать. It starts at a source node, src, which is marked as having been visited (i.e., setting marked[src] to True) and is then pushed onto the stack for further processing. Each time through the while loop, the stack contains nodes that have already been visited and marked: they are popped from the stack, one at a time, and unmarked adjacent neighbors are marked and added to the stack for further processing.

   1 def dfs_search(G, src):                 # 1
   2   node_from, stack = {}, [src]          # 2
   3   marked = {src: True}                  # 3
   4 
   5   while stack:                          # 4
   6     v = stack.pop()                     # 5
   7     for w in G[v]:
   8       if not w in marked:
   9         node_from[w] = v                # 6
  10         marked[w] = True                # 7
  11         stack.append(w)
  12 
  13   return node_from                      # 8

• Пример 7-3. Обход графа из указанного входного узла src вглубину Listing 7-3. Depth First Search of graph from designated source node, src

1. Обойдём граф G начиная с входного узла src вглубину. Conduct a Depth First Search over graph, G, starting from source node, src.

2. В node_from[w] будет храниться узел, из которого мы попали в w — это история обхода, вплоть до src (которого в ней нет). На вершине стека — единственный узел, входной. The marked dictionary records nodes that have already been visited. Record how search got to each node: node_from[w] is the prior node working backward to src.

3. Во входном узле мы уже побывали, так что он единственный помечен как посещённый. Mark and place src node into Stack to start the search. The top node in the Stack represents the next node to explore.

4. Если стек непуст, значит обход не завершён: есть ещё неисследованные узлы. If the Depth First Search has not yet completed

5. Следующий узел для проверки, v, лежит на вершине стека. , v is the next node to explore.

6. Просмотрим все узлы w, смежные с v, и выберем из них ещё не посещённые. Запомним, что каждый такой w доступен из v. For each unmarked node, w, adjacent to v, remember that to get to w, the search came from v.

7. Отметим w как посещённый (чтобы не исследовать потом повторно) и положим его на стек. Push w onto the top of the stack and mark it so it won’t be visited again.

8. Возвратим историю обхода: для каждого исследованного нами узла v в ней хранится узел, из которого мы попали в этот v, когда начали обход в стартовом узле src. Return the structure of the search that records for each node, v, the prior node from a search initiated at src.

На иллюстрации 7-5 показан обход вглубину с отображение состояния стека на каждом проходе цикла while. Выделенный на вершине стека узел — это комната, которую мы в данный момент исследуем, остальные узлы на стеке — это комнаты, которые мы исследуем в будущем. Что не даёт обходу вглубину бесцельно и бесконечно обшаривать одни и те же соседние комнаты? Каждый узел, который мы кладём на стек, помечается как уже исследованный, а это означает, что вторично на стек мы его никогда не положим. В цикле for (с переменной w) мы ищем ещё не помеченные смежные с v узлы, помечаем их и кладём на стек, чтобы потом исследовать. Figure 7-5 visualizes the execution of Depth First Search, showing the updated state of the stack each time through the while loop. The highlighted node at the top of the stack is the current cell being explored; other nodes in the stack represent nodes that will eventually be processed in the future. You might wonder how Depth First Search avoids getting stuck wandering around aimlessly, forever. Each time a node is pushed onto the stack, it is marked, which means it will never be pushed onto the stack again. The for loop over w will find all unmarked nodes adjacent to v, yet to explore: it will mark each w and push w onto the stack for further exploration.

Иллюстрация 7-5. Обход вглубь найдёт любую комнату, доступную из входной.

Обход сначала упирается в тупик на (1, 3), но немедленно откатывается до (0, 4) и продолжается дальше. Иллюстрация 7-5 показывает момент, когда выход уже найден, но обход продолжается, потому что не узлы, достижимые из входного, помечены, и стек не пуст. The search finds its first dead end, at (1, 3), but quickly recovers, popping off node (0, 4) to resume its search. The search is paused in Figure 7-5 to show the state once the target is found, but the search continues until all nodes in the graph reachable from src are explored and the stack becomes empty.

Стек неизбежно опустеет, потому что, во-первых, количество узлов в графе конечно, а во-вторых, каждый помещаемый в стек узел предварительно помечается как посещённый. Снять пометку с узла невозможно, и значит в конце концов любой доступный из src узел будет помечен и помещён на стек, а затем снят оттуда на очередном шаге цикла while. The stack will ultimately become empty, since (a) there are a finite number of nodes in the graph, and (b) unmarked nodes are first marked before being pushed onto the stack. Since a node can never become “unmarked,” eventually each node that is reachable from src will be pushed exactly once onto stack and subsequently removed within the while loop.

Полученная история обхода вглубь показана на иллюстрации 7-5 в правой части: это содержимое словаря node_from[]. Словарь этот можно назвать деревом, потому что стрелки не образуют циклы. По содержимому этого словаря можно восстановить путь от входа (0, 2) до любого достижимого узла в графе, если идти от конца пути. Например, node_from[(0, 0)] = (1, 0), то есть предпоследний узел на пути к от`(0, 2) к (0, 0) — это (0, 1). The resulting depth-first search tree is shown on the right in Figure 7-5 as contained in the node_from[] structure. This structure can be called a tree because there are no cycles among the arrows. It encodes information that can be used to recover the path from (0, 2) to any reachable node in the graph by working backward. For example, node_from[(0, 0)] = (1, 0), which means the second-to-last node on the path from (0, 2) to (0, 0) was (1, 0).

Вообще-то хранящийся в истории обхода путь от входа к выходу далеко не самый короткий: он состоит из шести переходов. Обход вглубину не обязан выдавать кратчайшие пути, но зато непременно найдёт путь до каждого узла, если до него вообще можно добраться от входа. Функция path_to() в примере 7-4 вычисляет по данному node_from[] путь от входа src к произвольному узлу target в виде последовательности узлов, пользуясь тем, что node_from[v] всегда содержит узел, которые на пути от src до v был предпоследним. The computed six-move solution is not the shortest possible path to the target. Depth First Search offers no guarantee regarding the length of the discovered path, but it will eventually find a path to every reachable node from a designated source node. Given the computed node_from[] structure resulting from a Depth First Search initi‐ ated at src, the path_to() function in Listing 7-4 computes the sequence of nodes from src to any target reachable from src. Each node_from[v] records the prior node encountered in a search from src.

   1 def path_to(node_from, src, target):    # 1
   2   if not target in node_from:
   3     raise ValueError('Unreachable')     # 7
   4 
   5   path, v = [], target                  # 2
   6   while v != src:
   7     path.append(v)                      # 3
   8     v = node_from[v]                    # 4
   9 
  10   path.append(src)                      # 5
  11   path.reverse()                        # 6
  12   return path

• Пример 7-4. Построение пути по истории обхода Listing 7-4. Recovering actual path from node_from[]

1. Для того, чтобы найти путь из src в target (если он есть), достаточно знать историю обхода. node_from structure is needed to recover path from src to any target.

2. Переменная v будет проходить по обратному пути от target до src. To recover the path, set v to target node.

3. Пока v не добралось до src, добавляем v в обратный путь. As long as v is not src, append v to path, a backward list of nodes found on path from src to target.

4. Продолжаем идти назад, теперь v — это предыдущий узел в пути, node_from[v]. Continue backward by setting v to the prior node recorded by node_from[v].

5. Цикл заканчивается, когда мы доходим до src. Сам src для полноты картины надо добавить в path. Once src is encountered, the while loop terminates, so src must be appended to complete the backward path.

6. Переставляем элементы path в обратном порядке, превращая обратный путь в прямой, и возвращаем его⁵. Return the reverse of path to produce the proper ordering from src to target.

7. Сразу проверим, что target достижим из src, то есть содержится в node_from[]. If node_from[] doesn’t contain target, then it is not reachable from src.

Функция path_to() строит обратную последовательность узлов — от target до src — а затем просто обращает её, и получается искомый путь от src до target. Если попытаться построить путь до недостижимого узла, path_to() породит исключение ValueError. The path_to() function computes the sequence of nodes in reverse order from tar get backward until src is encountered; it then simply reverses the order of the dis‐ covered nodes to produce a solution in the proper order. If you try to recover a path to an unreachable node, then path_to() will raise a ValueError.

Обходя лабиринт вглубь, мы всякий раз выбираем одно случайное направление, как бы предполагая, что находимся в шаге от выхода. Зачастую нужен другой, более методичный, способ обхода. Depth First Search repeatedly heads off in arbitrary directions with the expectation that it is just one node away from the destination. Now let’s look at a more methodical search strategy.

Другой способ обхода: вширину

Breadth First Search Offers Different Searching Strategy

Обход лабиринта вширину устроен таким образом, что комнаты нам встречаются в порядке их удалённости от входа. Возьмём тот же лабиринт, что и на иллюстрации 7-3, и надпишем на каждой комнате кратчайшее расстояние от входа. Если нам удастся придумать, как сделать это достаточно эффективно, мы и получим обход вширину, при котором вычисляется кратчайший (состоящий из наименьшего количества рёбер) путь от входного узла до любого достижимого. Например, из иллюстрации 7-6 очевидно, что кратчайший путь от входа к выходу пролегает всего через три узла. Breadth First Search explores nodes in order of their distance from the source. Using the same maze from Figure 7-3, Figure 7-6 identifies each cell in the graph by its shortest distance from the source. As you can see, it finds a path through the maze just three cells long. In fact, Breadth First Search will always find the shortest path in a graph in terms of the number of edges visited.

Иллюстрация 7-6. "Обход вширину определяет кратчайший путь до каждой вершины

Начнём с некоторых идей относительно обхода вширину. Входной узел лабиринта на иллюстрации 7-6 имеет три смежных узла, до которых от него всего один шаг. Любой из этих узлов может оказаться началом кратчайшего пути к выходу, но, конечно, нельзя заранее сказать, какой. Поэтому вместо того, чтобы выбирать одно направление и продвигаться на следующий узел, при обходе вширину мы должны сначала исследовать каждый из уже возможных шагов вперёд — тогда у нас получится множество узлов, до которых в сумме два шага. Выглядит так, как если бы мы обходя граф перестали наспех выбирать первое попавшееся направление, а начали методично обшаривать одно за другим. To provide some intuition behind Breadth First Search, observe in Figure 7-6 that from the source of the maze, there are three nodes that are just one step away—any one of these could lead to the shortest distance solution to the target, but, of course, you can’t know which one. Instead of picking just one of these nodes to explore, Breadth First Search takes each one and advances one step further until it finds those nodes that are two steps away. With this methodical approach, it will not make any rash decisions while exploring the graph.

Продолжая аналогию: обход вглубину — оптимистичен, ибо ожидает выхода за первым же поворотом, а обход вширину предпочитает порядок, и просматривает все узлы, расстояние до которых от входа на один шаг больше. Это даёт ещё четыре узла (на иллюстрации 7-6 помечены двойкой) — они от входа в двух шагах. Если продолжать исследовать узлы таким манером, то после того, как в свою очередь мы рассмотрим все узлы, что в дух шагах от входа, мы найдём четыре узла, до которых от входа три шага. Процесс будет повторяться до тех пор, пока мы не побываем во всех достижимых от входа узлах. Instead of being optimistic like Depth First Search, Breadth First Search explores each of these nodes in order until all nodes that are one step away from the source have been visited; this results in four different nodes (labeled with 2 in Figure 7-6) that are two steps away from the source. In similar fashion, each of these nodes will be explored in order until all nodes that are two steps away from the source have been visited, resulting in four nodes that are three steps away from the source. This process continues until every node in the graph reachable from the source is visited.

Для обхода вширину нам понадобится особая структура данных, которая гарантировала бы нам, что узел, находящийся на расстоянии d + 1 от входа, попадётся нам не ранее всех узлов, находящихся от входа на расстоянии d. Такую структуру данных мы знаем — это очередь, описанная нами в главе 4, ибо в ней поддерживается дисциплина «первым вошёл, первым вышел» (FIFO, First In First Out): узлы, добавленные в очередь сначала, непременно будут рассмотрены первыми. Программа из примера 5-7 практически такая же, что и для обхода вглубину, за исключением того, что используется очередь, и в очереди хранится пространство активного поиска, то есть набор узлов, которые в данный момент необходимо исследовать. Breadth First Search needs a structure to keep track of the nodes because it has to make sure that a node with distance d + 1 is not explored before all nodes with dis‐ tance d are visited. The queue data type covered in Chapter 4 will process nodes in this order, because it enforces a “first in, first out” (FIFO) policy for adding and removing values. The code in Listing 7-5 is nearly identical to the code for Depth First Search, with the exception that a queue stores the active search space, that is, the nodes actively being explored.

   1 def bfs_search(G, src):         # 1
   2   marked = {src: True}          # 2
   3   node_from = {}                # 3
   4 
   5   q = Queue()
   6   q.enqueue(src)                # 4
   7 
   8   while not q.is_empty():       # 5
   9     v = q.dequeue()
  10     for w in G[v]:
  11       if not w in marked:
  12         node_from[w] = v        # 6
  13         marked[w] = True        # 7
  14         q.enqueue(w)
  15 
  16   return node_from              # 8

• Пример 7-5. Обход графа вширину от заданного узла Listing 7-5. Breadth First Search of graph from designated source node

1. Функция обхода графа G вширину начиная с входного узел src. Conduct a Breadth First Search over graph, G, starting from source node, src.

2. В словаре marked мы храним уже исследованные узлы — вход уже там. The marked dictionary records nodes that have already been visited.

3. В словаре node_from будет храниться история обхода: для каждого узла w в node_from[w] содержится узел, из которого мы попали в w при обходе, т. е. очередной узел по дороге обратно к src/. Record how search got to each node: node_from[w] is the prior node working backward to src.

4. Добавим входной узел в очередь разведки. В начале очереди будет всегда находиться узел, который нам нужно проверить следующим. Mark and place src node into Queue to start the search. The first node in the Queue represents the next node to explore.

5. Если наш обход вширину не завершён, снимем из очереди очередной исследуемый узел, v. If the Breadth First Search has not yet completed, v is the next node to explore.

6. Перебираем все смежные с v и притом не помеченные узлы w. Запоминаем, что путь до них лежит через v. For each unmarked node, w, adjacent to v, remember that to get to w, the search came from v.

7. Ставим w в конец очереди (плана разведки) и помечаем его, чтобы не исследовать повторно. Place w as last node to explore at the end of the queue, and mark it so it isn’t vis‐ ited multiple times.

8. Возвращаем историю обхода, в которой для каждого узла v хранится узел, из которого мы попали в v, когда начинали обход из src. Return the structure of the search that records for each node, v, the prior node from a search initiated at src.

История обхода вширину содержит узлы в порядке их удаления от входа, поэтому любой воссозданный по этой истории путь до любого достижимого узла окажется кратчайшим⁶. Воссоздать путь из src до любого достижимого оттуда узла можно с помощью всё той же функции path_to(). На иллюстрации 7-7 хорошо видно, как методично исследуется граф при обходе вширину. Because Breadth First Search explores nodes in increasing order of their distance from the source, the resulting path to any reachable node in the graph will be a short‐ est path.4 You can use the same path_to() function to recover the path from src to any node in the graph reachable from src. As visualized in Figure 7-7, Breadth First Search methodically explores the graph.

Мы используем очередь для хранения плана разведки в порядке удаления от входа, и узлы на иллюстрации помечены разными оттенками в зависимости от расстояния до входного узла. Если мы упираемся в тупик, новых узлов в очередь не добавляется. Заметим, что выходной узел (2, 2) мы добавляем в очередь внутри цикла for, но иллюстрация сделана в момент, когда этот узел снимается из очереди во внешнем цикле while. К этому времени все узлы, расстояние до которых меньше двух шагов, мы уже просмотрели, а самый последний узел в очереди уже в трёх шагах от входа. The queue maintains the search space in order of distance from the source; the nodes are shaded in the queue based on their distance from the source. Whenever a dead end is encountered, no new nodes are enqueued. Note that the target node (2, 2) is added to the queue within the for loop, but the visualization shows the moment when it is dequeued by the outer while loop. All nodes fewer than 2 steps away from the source have been processed, and the very last node in the queue is 3 steps away from the source.

Из чистой любознательности давайте рассмотрим ещё один способ найти путь от входа к выходу, при котором мы учитываем, как далеко от выхода находимся. И обход вглубину, и обход вширину — это слепой поиск: план обхода в них строится исходя только из информации об узлах, смежных с данным. Если подключить к поиску выхода какой-никакой искусственный интеллект, мы получим немало новых, более эффективных алгоритмов решения нашей задачи —­но для этого надо снабдить их дополнительной информацией о предмете исследования. Just for fun, I’ll show a third approach for solving rectangular mazes that takes into account how far away a node is from the target. Both Depth First Search and Breadth First Search are blind searches: that is, they complete their search with only local information about adjacent nodes. The field of artificial intelligence has developed numerous path-finding algorithms that can more effectively complete a search when provided with information about the application domain.

4 There may be multiple paths of the same length, but Breadth First Search will discover one of these paths for which none can be shorter.

Иллюстрация 7-7. Обход вширину даёт кратчайший путь

При направленном обходе мы будем просматривать узлы в порядке их приближения к входу. Чтобы определить «приближение», надо понять, как измерять расстояние до узла. Нам подойдёт т. н. расстояние городских кварталов⁷, иначе называемое манхэттенским расстоянием или прямоугольной метрикой. Если мы посчитаем, сколько в сумме рядов и столбцов разделяют два узла, мы и получим манхэттенское расстояние. Например, узел (2, 0) в левом нижнем углу нашего лабиринта окажется по этой метрике в четырёх шагах от узла (0, 2), потому что и про вертикали он отстоит на две колонки, и по горизонтали — на два столбца. A Guided Search explores nodes in order of their shortest physical distance from the target; to do this, I need to determine how far a node is from the target. Let’s define the Manhattan distance between two cells in a maze as the sum of the number of rows and columns separating the two nodes.5 For example, node (2, 0) in the lower-left- hand corner of the sample maze is four steps away from node (0, 2), because it is both two rows away and two columns away.

Из трёх узлов, смежных с (0, 2) в направленном обходе мы должны сначала исследовать (1, 2), потому что он всего в шаге от выхода, (2, 2), а два других узла — оба от выхода в трёх шагах (согласно прямоугольной метрике). Получается, что для этого алгоритма узлы должны храниться так, чтобы всякий раз можно было получить узел, ближайший к выходу. Given the three adjacent nodes to the source node (0, 2) in the sample maze, Gui‐ ded Search would first explore (1, 2) because it is only one step away from the target of (2, 2); the other two adjacent nodes are both three steps away using the Manhat‐ tan distance. For this idea to work, the nodes being explored need to be stored using a data structure that allows you to retrieve the node closest to the target.

5 So called because in a city with a grid street layout, you can’t move diagonally, only up, down, left, and right.

Проще всего применить тут приоритетную очередь с порядком возрастания — или уже реализованную нами в четвёртой главе приоритетную очередь с порядком убывания, но в качестве приоритета использовать отрицательное число, равное по модулю манхеттэнскому расстоянию от узла до выхода. Таким образом получится, что два узла — u на расстоянии десяти шагов от выхода и v на расстоянии пяти — будут помещены в приоритетную очередь как (u, -10) и (v, -5), и следовательно приоритет узла v, который ближе к выходу, окажется больше. Пример 7-6 похож на аналогичные функции для обхода вглубину и обхода вширину, но план разведки — узлы, которые нужно исследовать — будет храниться в приоритетной очереди. One common trick is to use a max priority queue, as presented in Chapter 4, by defining the priority of a node to be the negative of the Manhattan distance from node to target. Consider two nodes, where node u is ten steps away from the target, and node v is five steps away. If these nodes are stored in a max priority queue with (u, –10) and (v, –5), then the node with larger priority is v, which is the one closer to the target. The structure of Listing 7-6 is identical to the Breadth First and Depth First Search code, but it uses a priority queue to store the active search space of nodes to explore.

   1 def guided_search(G, src, target):              # 1
   2   from ch04.heap import PQ
   3   marked, node_from = {src: True}, {}           # 2
   4 
   5   pq = PQ(G.number_of_nodes())                  # 3
   6   pq.enqueue(src, -distance_to(src, target))    # 4
   7 
   8   while not pq.is_empty():                      # 5
   9     v = pq.dequeue()
  10     for w in G.neighbors(v):
  11       if not w in marked:
  12         node_from[w] = v                        # 6
  13         marked[w] = True
  14         pq.enqueue(w, -distance_to(w, target))  # 7
  15 
  16   return node_from                              # 8
  17 
  18 def distance_to(from_cell, to_cell):
  19   return abs(from_cell[0] - to_cell[0]) + abs(from_cell[1] - to_cell[1])

• Пример 7-6. Направленный обход, порядок которого обусловлен манхеттенским расстоянием от выхода Listing 7-6. A Guided Search using Manhattan distance to control search

1. Функция обхода графа G начиная с входного узел src по направлению к заранее известному выходу. Conduct a Guided Search over graph, G, starting from source node, src, knowing the target node to locate.

2. В словаре marked будем хранить уже просмотренные узлы. Вход уже там. Историю обхода — в словаре node_from (напомним, что в node_from[w] хранится узел, который был предыдущим на пути от входа в w). The marked dictionary records nodes that have already been visited. Record how search got to each node: node_from[w] is the prior node working backward to src.

3. Используем приоритетную очередь на базе кучи из четвёртой главы: размер очереди надо задать заранее. Очереди, способной разместить все узлы графа, явно достаточно. Using the heap-based priority queue, you must pre-allocate sufficient space to include, potentially, all nodes in the graph.

4. Поместим вход, src, в приоритетную очередь — с него и начнётся исследование. Приоритет — отрицательное число, по модулю равное расстоянию до выхода, target. Mark and place src node into max priority queue to start the search using as its priority the negative of its distance to target.

5. До тех пор, пока очередь не пуста, обход не закончен. В начале очереди — всегда ближайший к выходу помеченный узел, им и продолжим исследование. If the Guided Search has not yet completed, the node closest to target is the next node to explore.

6. Запоминаем в истории обхода, что до каждого непомеченного узла w, смежного с v, мы дошли из v. For each unmarked node, w, adjacent to v, remember that to get to w, the search came from v.

7. Ставим w в приоритетную очередь. Он займёт там подобающее место с приоритетом, равным отрицательному манхеттэнскому расстоянию до входа; пометим этот узел. Place w into its appropriate location in the priority queue, using the negative of the Manhattan distance as priority, and mark it so it isn’t visited multiple times.

8. Возвратим историю обхода, в которой для каждого узла v хранится предыдущий (при обходе, началом из узла src). Return the structure of the search that records for each node, v, the prior node from a search initiated at src.

Толику искусственного интеллекта направленному обходу придаёт функция distance_to(), которая вычисляет манхэттенское расстояние между двумя узлами. The intelligence guiding the search is the distance_to() function, which computes the Manhattan distance between two nodes.

Не факт, что направленный обход выдаст кратчайший путь к выходу, к тому же предполагается, что выход единственный, и мы заранее знаем, где он. В частности, путь может оказаться длиннее, чем то, что выдаёт обход вширину, потому что там гарантируется, что он будет кратчайшим, причём не только к выходу, но и к каждому достижимому узлу в графе. Зато можно надеяться, что направленный обход реже будет заглядывать в те части лабиринта, где искать выход нет смысла — как минимум, в случайных лабиринтах⁸. На иллюстрации 7-8 можно сравнить изображённые рядом планы обхода одного и того же лабиринта всеми тремя нашими способами. There is no guarantee that Guided Search will find the shortest path, plus it presumes in advance a single target to guide its search. In particular, it cannot outperform Breadth First Search, which is guaranteed to locate the shortest path not just to the target but to every node in the graph reachable from the source: in doing so, however, Breadth First Search might explore much more of the graph. The hope is that Guided Search reduces unnecessary searches on random maze graphs. Figure 7-8 presents a side-by-side comparison of these three search algorithms on the same maze.

Иллюстрация 7-8. Сравнение обхода лабиринта вглубину, вширину и по направлению в выходу

Вероятно, что в поиске выхода из лабиринта больше всего узлов мы исследуем при обходе вширину: слишком уж последователен этот алгоритм. Обход вглубину вряд ли выдаст кратчайший путь: для этого каждый выбранное при обходе направление должно оказаться верным. Нет гарантии, что направленный обход выдаст кратчайший путь от входа к выходу, но в случайном лабиринте с иллюстрации 7-8 направление на выход помогло существенно сократить неуспешные попытки поиска. Breadth First Search will likely explore the most nodes because of its methodical nature. For Depth First Search to discover the shortest path, it must repeatedly choose the right direction to pursue, which is unlikely. There is no guarantee that Guided Search will compute the shortest path between source and target, but as shown in Figure 7-8, it reduces side explorations because it can aim toward the target.

Все наши алгоритмы обхода использовали словарь marked, узлы из которого не надо исследовать, и в результате в любой из N узлов графа мы заглядываем не больше раза. Тогда можно предположить, что сложность любого из них — O(N), но чтобы это доказать, надо оценить производительность различных действий внутри цикла. Операции push() и pop() над стеком имеют константную сложность. Осталось только понять, как работает цикл for w in G[v], в котором перебираются все смежные с v узлы. Тут всё несколько сложнее: необходимо знать, как именно хранятся рёбра в графе. Есть два способа хранить рёбра (оба показаны на иллюстрации 7-9): матрица смежности и список смежности. These search algorithms use a marked dictionary to ensure each of the N nodes is vis‐ ited only once. This observation suggests that the runtime performance of each algo‐ rithm is O(N), but to confirm this you must validate the performance of the individual operations. With a Stack, its operations are performed in constant time— push(), pop(), and is_empty(). The only remaining concern is the efficiency of the for w in G[v] loop, which returns the adjacent nodes to v. To classify the perfor‐ mance of this for loop, you need to know how the graph stores edges. There are two options, visualized in Figure 7-9, for the maze from Figure 7-3: an adjacency matrix and an adjacency list.

Матрица смежности

Двумерный массив M размером N × N, хранящий N² булевских значений. Все узлы нумеруются, то есть каждому узлу u ставится в соответствие число u_idx в диапазоне от 0 до N. Если существует ребро из u в v, значение M[u_idx][v_idx] — истинно. На иллюстрации значение True (истина) обозначено закрашенной клеткой. С помощью матрицы смежности мы можем найти все узлы, смежные с данным, за N шагов, так как для этого необходимо проверить одну полную строку матрицы. Соответственно, независимо от действительного количества смежных узлов для каждого узла лабиринта сложность такого действия будет O(N). Поскольку сам цикл while проходит N итераций, а внутренний цикл сам по себе имеет сложность O(N), выходит, что наше исходное предположение неверно, и сложность всего алгоритма — квадратичная, O(N²).

Adjacency matrix An adjacency matrix creates a two-dimensional N × N matrix, M, with N2 Boolean entries. Each node, u, is assigned an integer index, uidx, from 0 to N – 1. If M[uidx] [vidx] is True, then there is an edge from u to v. These edges are shown as a sha‐ ded box, where u is the row label and v is the column label. With an adjacency matrix, retrieving all adjacent nodes for a node, u, requires O(N) runtime perfor‐ mance to check each entry in M for u, regardless of how many adjacent nodes to u actually exist. Since the while loop executes N times, and now the inner for loop requires O(N) performance to check N entries in M, this means that the search algorithm is classified as O(N2).

Список смежности

Ассоциативный массив, ключом которого выступает узел графа, а хранится в нём список узлов, смежных с соответствующим узлом. МЫ помним, что поиск в словаре по ключу имеет константную сложность, а поиск в списке — линейную, так что время выборки всех вершин, смежных с данной, будет прямо пропорционально степени вершины, то есть количеству исходящих из неё рёбер. Порядок перечисления рёбер не определён, он зависит о порядка их добавления в граф. На иллюстрации 7-9 для каждого узла представлен список рёбер, при этом у некоторых узлов смежных мало, а у некоторых — больше.

Adjacency list An adjacency list uses a symbol table that associates for each node, u, a linked list of adjacent nodes. Retrieving all adjacent nodes for a node, u, requires runtime performance directly proportional to d, where d is the degree of node u, or the number of adjacent nodes to u. There is no predetermined ordering for these adjacent nodes, since that is based on how the edges were added to the graph. These linked lists are visualized for each node, u, in Figure 7-9. With an adja‐ cency list, some nodes have few adjacent nodes, while others have a large number of adjacent nodes.

Иллюстрация 7-9. Как выглядят матрица смежности и список смежности

Я слегка исправил картинку — убрал оттуда представление связного списка -- FrBrGeorge 2023-01-24 17:23:08

В примере 7-7 приведена часть программы, из которой понятно: если граф представлен с помощью списка смежности, быстродействие обхода вглубину зависит от общего количества рёбер в графе. Можно легко подсчитать, и сколько узлов обрабатывается в программе, и сколько рёбер. The code fragment in Listing 7-7 shows that the runtime performance of Depth First Search is based on E, the number of edges in the graph, when an adjacency list is used for representation. Instead of counting the number of nodes being processed, count the number of edges being processed.

   1 while stack:
   2   v = stack.pop()
   3   for w in G[v]:
   4     if not w in marked:
   5       marked[w] = True
   6       stack.append(w)
   7       ...

• Пример 7-7. Часть программы, иллюстрирующая зависимость быстродействия от количества рёбер Listing 7-7. Code fragment showing performance based on the number of edges

Мы помним, что каждый узел v добавляется на стек не более раза. Это значит, что оператор if выполняется для каждого смежного с v узла. Возьмём простейший граф из двух узлов, u и v, и одного ребра (u, v) — уже на нём if выполнится дважды: сначала при поиске вершин, смежных с u, а затем — при поиске вершин, смежных с v. В общем, на ненаправленных графах этот if будет выполняться 2·E раз, где E — это общее число рёбер в графе. You have already seen that each node, v, can be inserted into the stack only once. This means the if statement will execute once for every adjacent node to v. If you consider a graph with just two nodes, u and v, with a single edge (u, v), then the if statement will execute twice, once when processing the adjacent nodes to u and once when pro‐ cessing the adjacent nodes to v. So for an undirected graph, the number of times that the if statement executes is 2 × E, where E is the number of edges in the graph.

Если учесть все действия — вызовы .append() / .pop(), которых может быть не более N и 2·E раз выполненный оператор if, можно смело утверждать, что быстродействие алгоритмов, использующих список смежности, равно O(N + E), где N — это число узлов, а E — число рёбер графа. Утверждение верно и для обхода вширину, в котором используется не стек, а очередь, но производительность оказывается такой же. Put all this together—up to N push() and pop() invocations and 2 × E invocations of the if statement—and you can declare that the runtime performance of these search algorithms when using adjacency lists is O(N + E), where N is the number of nodes and E is the number of edges. The same is true for Breadth First Search, which uses a queue instead of a stack but exhibits the same runtime performance.

В каком-то смысле все наши оценки совпадают: в самом деле, неориентированный граф с N узлами может содержать не более E = N · (N - 1) / 2 рёбер⁹. Так что независимо от того, используется ли для хранения графа матрица смежности или список смежности, обход графа с достаточно большим количеством рёбер потребует порядка N · (N - 1) / 2 действий в наихудшем случае, то есть сложность окажется O(N²). In some ways, these results are actually compatible; specifically, in an undirected graph with N nodes, E is less than or equal to N × (N – 1)/2 edges.6 Regardless of whether the graph is stored using an adjacency matrix or an adjacency list, searching over graphs with a high number of edges will be proportional to N × (N – 1)/2, or O(N2), so in the worst case it will be O(N2).

А вот направленный обход для хранения узлов использует приоритетную очередь с порядком — расстоянием до выхода. Операции enqueue() и dequeue() в наихудшем случае имеют сложность O(log N). Сами методы вызываются N раз, и каждое ребро просматривается дважды, так что быстродействие направленного обхода в худшем случае оказывается O(N log N + E). Guided Search, however, relies on a priority queue to maintain the nodes closest to the designated target node. The enqueue() and dequeue() operations are O(log N) in the worst case. Since these methods are called N times, and each edge is visited twice, the worst case performance for Guided Search is O(N log N + E).

Ориентированные графы

Directed Graphs

Графы можно использовать для представления данных в задачах, где связь между узлами — односторонняя (обычно обозначается стрелкой). Дуга — ориентированное ребро — (u, v) соединяет u с v, и это значит, что вершина v смежна с u, но и только: дуга не делает вершину u смежной с v. В ориентированном ребре (u, v) вершина u называется, естественно, началом дуги, а v — её концом. В графе на иллюстрации 7-10 есть дуга (B3, C3), но нет дуги (C3, B3). Graphs can also model problems where the relationship between two nodes is direc‐ tional, typically represented as an edge with an arrow. A directed edge (u, v) only declares that v is adjacent to u: this edge does not make u adjacent to v. In this edge, u is the tail, while v is the head—this is easy to remember because the arrow head is adjacent to v. The graph in Figure 7-10 contains the edge (B3, C3) but not (C3, B3).

Иллюстрация 7-10. Пример ориентированного графа с 12 узлами и 14 рёбрами

Ориентированный граф (или орграф) — можно обходить как вглубину, так и вширину, единственное отличие — в том, что дуга (u, v) означает, что вершина v смежна с u, а для того, чтобы u была смежна с v, нужно, чтобы в графе была также и дуга (v, u). Многие алгоритмы на оргафах можно упростить, если реализовать их рекурсивно, как в примере 7-8. Можно видеть, что эта программа заимствует основные компоненты из нерекурсивной реализации. The Depth First and Breadth First searches are still relevant for directed graphs: the only difference is that with the edge (u, v), v is adjacent to u, but the opposite is only true if the graph contains a separate edge (v, u). With directed graphs, many algo‐ rithms are simplified when using recursion, as shown in Listing 7-8. This code includes many familiar elements from the nonrecursive implementation.

6 The triangle numbers make yet another appearance!

   1 def dfs_search(G, src):         # 1
   2   marked, node_from = {}, {}    # 2
   3 
   4   def dfs(v):                   # 3
   5     marked[v] = True            # 4
   6     for w in G[v]:
   7       if not w in marked:
   8         node_from[w] = v        # 5
   9         dfs(w)                  # 6
  10 
  11   dfs(src)                      # 7
  12   return node_from              # 8

• Пример 7-8. Рекурсивная реализация обхода графа вглубину Listing 7-8. Recursive implementation of Depth First Search on a directed graph

1. Функция обхода графа G вглубь начиная со входного узла src. Conduct a Depth First Search over graph G starting from source node, src.

2. Словарь marked хранит уже посещённые узлы, словарь node_from — историю обхода графа функцией dfs(): в node_from[w] содержится предыдущей узел в пути от src до w. The marked dictionary records nodes that have already been visited. Record how dfs() found each node: node_from[w] is the prior node working backward to src.

3. Рекурсивная функция, при каждом вызове которой обход продолжается с непомеченного узла v. Recursive method to continue search from an unmarked node, v.

4. Пометим узел v как посещённый. Be sure to mark that v has been visited.

5. Для каждого непомеченного смежного с v узла w запоминаем, что дойти до него можно было от v. For each unmarked node, w, adjacent to v, remember that to get to w, the search came from v.

6. Рекурсивный вызов: продолжим исследование с непомеченного узла w, а после возврата из вызова выберем очередной узел w в цикле for. In the recursive case, continue search in direction of unmarked node, w. When recursive call ends, continue with for loop over w.

7. Стартовый рекурсивный вызов dfs() с параметром — входным узлом src. Invoke the initial recursive call on source node, src.

8. Возвращаем историю обхода, в которой для каждого узла v записано, каким был предыдущий узел на пути от src до v. Return the structure of the search that records for each node, v, the prior node from a search initiated at src.

Обратите внимание на то, что в рекурсивном алгоритме нет выделенного стека, в котором хранится план разведки. В действительности такой стек задан неявно — это последовательность контекстов рекурсивных вызовов функции dfs(), в каждом из которых есть локальные переменные u и v, а также список G[v]. A recursive algorithm remembers its partial progress using the recursive call stack, so there is no need for a Stack data type.

Каждый контекст dfs(v) в стеке рекурсивных вызовов содержит собственную локальную переменную v, которая является частью активного пространства поиска. Основание рекурсии в dfs(v) наступает, когда у узла v больше нет непомеченных смежных узлов w, при этом ничего не происходит, и контекст после возврата уничтожается. Для каждого непомеченного смежного узла w происходит рекурсивный вызов dfs(w). После возврата из рекурсивного вызова цикл for продолжается: возможно, есть ещё непомеченные смежные с v узлы, которые надо будет исследовать с помощью dfs(). For every dfs(v) in the recursive call stack (where v is different with each invoca‐ tion), node v is part of the active search space. In the base case of dfs(v), node v has no unmarked adjacent nodes, so it performs no work. In the recursive case, for each unmarked adjacent node, w, a recursive dfs(w) invocation is launched. When it returns, the for loop over w continues, trying to find additional unmarked nodes adjacent to v to explore with dfs().

Мы в нашей книге уже отмечали, что глубина рекурсии в Python ограничена 1000 вызовами, так что с помощью алгоритмов, в которых использование рекурсии не оправдано, мы можем обрабатывать только небольшие объёмы данных. Например, в прямоугольный лабиринт размером 50 × 50 состоит из 2500 узлов, и наш обход вглубь явно превысит ограничение на глубину рекурсии. Если заменить стек рекурсивных вызовов настоящим стеком, в котором хранится то же, что было в локальных переменных рекурсивной функции (в нашем случае — пространство активного поиска), проблема исчезнет. Увы, текст программы при этом становится более сложным и менее читаемым, так что в этой главе мы будем использовать «неоправданный» рекурсивный вариант.

Исходный текст функции, которая обходит граф вглубь с использованием стека вместо рекурсии можно найти в файле ch07/search.py репозитория¹⁰.

С помощью орграфов можно моделировать объекты из самых разных предметных областей, и для этих объектов решать бесчисленное множество задач. На иллюстрации 7-11 представлена электронная таблица, ячейки которой однозначно определяются названием столбца аи номером строки. В ячейке B3 записана единица, то есть B3 равно 1. Слева таблица изображена так, как её видит пользователь, а затем в виде чисел, ссылок на другие ячейки или формул, которые в действительности записаны в ячейках. Формула в ячейке может использовать константы или содержимое других ячеек, которое, в свою очередь, тоже может вычисляться по формуле. Формат представления формул — инфиксный, такие формулы мы видели в главе 6. Например, в ячейке A4 записана формула «=(A3 + 1)». В ячейке A3 записано «=(A2 + 1)», что равно 1, потому что A2 равно 0 — а значит, A4 равно 2. В репозитории к этой книге есть программа, реализующая отношения в этой таблице. Directed graphs can model application domains that have different problems to solve. Figure 7-11 depicts a small spreadsheet business application containing cells uniquely identified by a column and a row; cell B3 contains the constant 1, and this means the value of B3 is 1. The left image in Figure 7-11 shows the view presented to the user; the middle image shows the actual contents of each cell, including formulas. A cell can contain formulas that refer to other constants, and possibly the values computed from other formulas. These formulas are represented using infix expressions, which you learned in Chapter 6. For example, cell A4 contains the formula “= (A3 + 1)”. Now, A3 contains the formula “= (A2 + 1)”, which can be computed as 1 (since A2 contains the value 0), which means that A4 is computed to be 2. The code for this sample spreadsheet application is contained in the repository.

Иллюстрация 7-11. Пример электронной таблицы, соответствующей ориентированному графу

7 Find the stack-based Depth First Search in ch07.search in the code repository.

В первой строке электронная таблица содержит заголовки столбцов — N, FibN и Sn. Во всех остальных строках в столбце A содержится первые семь целых неотрицательных чисел N, в столбце B — первые семь чисел Фибоначчи¹¹. В каждой строке столбца C записана частичная сумма первых N чисел Фибоначчи (например, в C7 хранится 12, что равно 0+1+1+2+3+5). В правой части иллюстрации 7-11 изображён орграф, отражающий зависимость ячеек друг от друга. Например, дуга между A2 и A3 означает, что для вычисления A3 надо знать значение A2, то есть, во-первых, если изменится A2, то изменится и A3, и, во-вторых, перед тем, как вычислять A3, необходимо сначала вычислить A2. This spreadsheet computes increasing values for N in column A, while column B contains the first seven Fibonacci numbers.8 Column C contains the running total of the first N Fibonacci numbers (for example, the 12 in cell C7 represents the sum of 0 + 1 + 1 + 2 + 3 + 5). The right image in Figure 7-11 represents the directed graph that captures the relationships between the cells. For example, there is an edge from A2 to A3, reflecting that the value for A3 must change when A2 changes; another way to phrase this relationship is that the value for A2 must be known before the value for A3 can be computed.

Ячейки электронной таблицы не могут содержать взаимных ссылок: например, если в ячейке C2 написано =B2, то с ячейке B2 не должно быть =C2 — значение таких ячеек вычислить нельзя, это считается ошибкой. В орграфах подобная ситуация называется контуром. Контур — это последовательность дуг, которая начинается и заканчивается в некотором узле u. Любая система, работающая с электронными таблицами, должна проверить, что в ней нет контуров — а значит, ячейки без взаимных ссылок можно вычитать без ошибок. Вернёмся к иллюстрации 7-11. Обрабатывать ячейки, в которых записаны числа, не нужно. К моменту вычисления A4 значение A3 должно быть уже известно (а к моменту вычисления A5 нужно знать, соответственно, значения обеих ячеек). Зависимость между ячейками в столбцах B и C — посложнее, а значит и порядок их вычисления определить не так легко, не говоря уже о том, чтобы обнаружить в них контур. In a spreadsheet, if cell C2 contains the formula “= B2” and cell B2 contains the for‐ mula “= C2”, these cells refer to each other, resulting in a circular reference, which is an error. Using the terminology of directed graphs, this situation would be a cycle, that is, a sequence of directed edges that starts at a node, n, and returns to n. Every spreadsheet program checks for cycles to make sure that its cells can be properly computed without error. Returning to Figure 7-11, the cells containing constants do not require any computations. The value for A3 needs to be computed before the value for A4 (which is subsequently needed when computing A5). The relationship between the B and C cells is more complicated, making it harder to know the order in which these cells should be computed, let alone whether a cycle even exists.

Для аккуратной работы приложению-электронной таблице нужно завести орграф, в котором будут отражены зависимости ячеек друг от друга. Если пользователь заменяет в какой-то ячейке формулу числом, приложение должно удалить соответствующие дуги из графа. Если число на формулу — добавить новые дуги, моделирующий зависимость текущей ячейки от упомянутых в формуле. Если формулу на формулу — часть дуг надо удалить, часть добавить. Например, в таблице на иллюстрации 7-11 можно ошибочно создать контур, если в ячейку B2 вписать формулу =C5. Это приведёт к добавлению в орграф новой дуги C5 → B2, что породит несколько контуров; вот один из них: [B2, B4, B5, C5, B2]. To operate safely, a spreadsheet application can maintain a directed graph of refer‐ ences between its cells to record dependencies between the cells. Whenever the user changes the contents of a cell, the spreadsheet must remove edges from this graph if the cell had formerly contained a formula. If the changed cell introduces a new for‐ mula, then the spreadsheet adds edges to capture the new dependencies in the for‐ mula. For example, given the spreadsheet from Figure 7-11, the user could mistakenly create a cycle by changing the contents of cell B2 to be the formula “= C5”. With this change, a new edge, C5 → B2, would be added to the directed graph, leading to sev‐ eral cycles; here is one: [B2, B4, B5, C5, B2].

Найти контур в орграфе поможет обход вглубь. Идея в том, чтобы аварийно останавливать обход, когда в пространстве активного поиска (плане разведки) внезапно оказывается помеченный узел — потому что это и есть признак контура. Когда dfs(v) возвращает историю обхода, мы можем быть уверены, что все достижимые из v узлы помечены, а v не присутствует в пространстве активного поиска. Given a directed graph, Depth First Search can determine whether a cycle exists in the directed graph. The intuition is that when Depth First Search finds a marked node that is still part of the active search space, a cycle exists. When dfs(v) returns, you are assured that all nodes that are reachable from v have been marked, and v is no longer part of the active search space.

8 Recall from Chapter 5 that these are the numbers 0, 1, 1, 2, 3, 5, and 8, computed by adding two successive terms.

Обходя орграф вглубь, мы можем наткнуться на помеченный узел, даже если это граф из трёх узлов и контуров в нём нет. Если запустить dfs() с узла a, то обход вглубь встретит сначала b, а затем c, зайдя в тупик. Откатившись обратно к a, мы обратимся к следующему смежному узлу, c, а он уже помечен, хотя контуров в графе нет.

Поиск контура в графе — алгоритм, который, в отличие от других алгоритмов в этой главе, не начинает исследование с какого-то конкретного входного узла, потому что должен найти контур в любом месте графа. Как показано в примере 7-9, для этого придётся исследовать многие (возможно, все) узлы графа. Словарь marked теперь хранит состояние узла: если marked[v] равно 1, узел помечен и присутствует в пространстве активного поиска (плане разведки), а если 2 — помечен, но в плане разведки его уже нет. При рекурсивном обходе вглубь пространством активного поиска (планом разведки) является стек контекстов вызовов, доступа к которому у нас нет. Поэтому информацию о том, есть ли данное v в одном из таких контекстов мы будем хранить в словаре marked: если marked[v] равно 1, узел помечен и присутствует в плане разведки, а если 2 — помечен, но в плане разведки его уже нет. This Cycle Detection algorithm differs from the other algorithms in this chapter because there is no initial dedicated source node from which the exploration starts. The question is whether a cycle exists anywhere in the graph, so the algorithm, described in Listing 7-9, has to investigate potentially every node in the graph.

   1 def has_cycle(DG):
   2       marked = {}
   3 
   4       def dfs(v):                               # 1
   5           marked[v] = 1                         # 2
   6           for w in DG[v]:
   7               state = marked.get(w, 0)          # 3
   8               if state == 1:                    # 4
   9                   return True
  10               if state == 0 and dfs(w):         # 5
  11                   return True
  12           marked[v] = 2                         # 6
  13           return False
  14 
  15       for v in DG.nodes():                      # 7
  16           if v not in marked and dfs(v):        # 8
  17               return True
  18       return False

• Пример 7-9. Определение контура в орграфе путём обхода вглубину Listing 7-9. Detecting cycles in a directed graph using Depth First Search

1. Функция dfs(v) обходит граф DG вглубину, начиная с узла v. Conduct a Depth First Search over graph, DG, starting from v.

2. Узел v помечен как посещённый и добавлен в план разведки (значение 1 в словаре marked). in_stack records nodes that are in the recursive call stack. Mark that v is now part of a recursive call. The marked dictionary records nodes that have already been visited.

3. Состояние каждого узла w, смежного с данным v: 0 — не помечен, 1 — помечен и есть в плане разведки, 2 — помечен и уже разведан. Помечаем v и For each unmarked node, w, adjacent to v, initiate recursive dfs() on w,

4. Если смежный узел w помечен и и при этом есть в плане разведки, то это по определению контур, можно сразу возвращать True. and if True is returned, a cycle is detected, so it returns True as well.

5. Если смежный узел w ещё не помечен, рекурсивно вызываем dfs(w), и если там нашёлся контур, возвращает True. If a node, w, is marked as visited, it could still be in our call stack—if it is, then a cycle has been detected.

6. Если контура пока не найдено, изменяем состояние узла v на «помечен, в плане разведки уже не присутствует» (значение 2). Equally important, when the dfs() recursive call ends, set in_stack[v] to False since v is no longer on the call stack.

7. Обход вглубину нужно проделать из каждого узла в нашем орграфе — мало ли, где найдётся контур. Investigate each unmarked node in the directed graph.

8. Достаточно искать не из каждого узла, а только из каждого ещё не помеченного. Если dfs(v) на таком узле v выдаст True — значит, найден контур, и надо возвращать True. If invoking dfs(v) on a node, v, detects a cycle, return True immediately.

С каждым рекурсивным вызовом dfs() граф исследуется всё больше до тех пор, пока всё узлы не окажутся помеченными — даже если они не являются вершинами дуг. As dfs() recursive calls execute, more of the graph is explored until eventually each node is marked—even those with no edges.

Определить состав самого контура тоже несложно — этому посвящено одно из тренировочных упражнений в конце главы, в котором требуется дописать has_cycle() таким образом, чтобы оно составляло и возвращало первый найденный в орграфе контур. На иллюстрации 7-12 показан рекурсивный вызов dfs(). Каждый исследуемый узел сначала помечается единицей — в знак того, что он определён как посещённый, и при этом находится в пространстве активного поиска, — а на выходе из рекурсивного вызова этот узел помечается двойкой, это признак посещённого узла, которого уже нет в плане разведки. Пометки — это содержимое словаря marked, но на иллюстрации соответствующая пометка для наглядности проставлена прямо на узле и выделена фоном. История на иллюстрации заканчивается тем, что в процессе обхода обнаруживается контур [a, b, d, a]: мы просматриваем узлы, смежные с d, и среди них оказывается узел a, помеченный двойкой — а это значит, что он присутствует в плане разведки. Иными словами, двигаясь из узла a по дугам, мы снова попали в a, что в точности соответствует определению контура. Мы уже определили контур, и возвращаем True, однако некоторые узлы всё ещё помечены двойкой, то есть остаются в (уже не актуальном) плане разведки — потому что рекурсивный вызов не доработал до конца. If you want to also compute the actual cycle, try the challenge exercise at the end of this chapter that modifies has_cycle() to compute and return the first detected cycle in a directed graph. Figure 7-12 visualizes the recursive execution of dfs(). Each dis‐ covered node is eventually marked, but only nodes in the active search space—those nodes where in_stack[] is True—are highlighted as the recursion proceeds and unwinds. The image shows the moment in the recursion when the cycle [a, b, d, a] is detected. When exploring the adjacent nodes to d, the marked node, a, is encoun‐ tered, but this doesn’t immediately mean that a cycle exists. The algorithm must check whether in_stack[a] is True to confirm that a cycle exists. The final recursive invocation of dfs(d) has not yet ended, which is why in_stack[d] is still True. To summarize, when the recursive dfs() function encoun‐ ters a node, n, that has already been marked and in_stack[n] is True, a cycle has been found.

Иллюстрация 7-12. Как найти контур, обходя орграф вглубину

Я переделал эту иллюстрацию, потому что переписал пример, стиль которого был чересчур неряшливым -- FrBrGeorge 2023-02-01 14:25:30

Предположим, контуров в электронной таблице нет. Теперь важно определить порядок, в котором нужно вычислять зависящие друг от друга ячейки. В старой таблице с иллюстрации 7-11 ячейки с константами (например, A1), вообще не надо вычислять, и они на порядок не влияют. Ячейка B4 содержит формулу, в которой явно упомянуты B2 и B3, так что их надо посчитать раньше, чем B4. Вот один из возможный вариантов линеаризации зависимостей в таблице: Assuming that a spreadsheet contains no circular references, in what order should its cells be computed? Returning to the spreadsheet example in Figure 7-11, the cells that contain constants (such as A1) are not involved in any computation, so they do not matter. The cell B4 contains a formula that directly depends on both B2 and B3, so these two cells must be computed before B4. One linear ordering that works is:

B2, C2, B3, C3, B4, C4, B5, C5, A2, A3, A4, A5

Такой порядок может быть результатом работы функции topological_sort(), приведённой в примере 7-10. Топологическая сортировка похожа на только что рассмотренный нами алгоритм поиска контуров — в нём тоже используется рекурсивная природа обхода вглубину. Всякий раз перед выходом dfs(v) из рекурсивного вызова, когда все достижимые из v узлы помечены, то есть dfs() уже обошла все узлы, «лежащие за v», можно добавить этот v в историю обхода, как узел, все зависимости которого уже удовлетворены. Вычислять ячейки электронной таблицы следует с конца этой истории. The preceding ordering is one possible result from topological_sort(), shown in Listing 7-10. The structure of this algorithm is identical to the Cycle Detection algo‐ rithm described earlier. It relies on a recursive Depth First Search to explore the graph. When dfs(v) is about to return from its recursive invocation, all nodes that are reachable from v have been marked. This means that dfs() has already visited all “downstream” nodes that are dependent on v, so it adds v to the growing list of nodes (in reverse order) whose dependencies have been processed.

   1 def topological_sort(DG):
   2   marked, postorder = {}, []    # 1
   3 
   4   def dfs(v):                   # 2
   5     marked[v] = True            # 3
   6     for w in DG[v]:
   7       if not w in marked:
   8         dfs(w)                  # 4
   9     postorder.append(v)         # 5
  10 
  11   for v in DG.nodes():
  12     if not v in marked:         # 6
  13       dfs(v)
  14 
  15   return reversed(postorder)    # 7

• Пример 7-10. Топологическая сортировка ориентированного графа Listing 7-10. Topological sort over the directed graph

1. В списке postorder хранится история обхода — линеаризация узлов графа в обратном порядке. Use a list to store (in reverse order) a linear ordering of nodes to be processed.

2. Функция dfs(v) выполняет обход графа DG вглубину, начиная с узла v. Conduct a Depth First Search over DG starting from v.

3. В словаре marked отмечается, что узел уже посещён. The marked dictionary records nodes that have already been visited.

4. Вызовем dfs(w) для всех непомеченных смежных с v узлов w. For each unmarked node, w, adjacent to v, recursively explore dfs(w).

5. В этом месте алгоритма функция dfs(v) уже исследовала все узлы, которые (рекурсивно) зависят от v — самое время добавить v в историю обода. When dfs(v) gets to this key step, it has fully explored all nodes that (recur‐ sively) depend on v, so append v to postorder.

6. Запустим dfs(v) для каждого ещё не помеченного узла v из графа DG. Заметим, что dfs() сам помечает вершины, так что каждый новый вызов обрабатывает отдельное подмножество узлов DG. Ensure that all unmarked nodes are visited. Note that each time dfs(v) is invoked, a different subset of graph DG is explored.

7. История обхода содержит линеаризацию в обратном порядке, так что обратим её и вернём. Because the list holds the linear ordering in reverse order, return its reverse.

В этой функции практически всё повторяет поиск контура, кроме того, что вместо явного хранения плана разведки в ней ведётся история обхода. Исследуя эту функцию уже известным нам методом, мы увидим, что каждый узел исследуется с помощью dfs() только раз, а внутренний оператор if выполняется по разу для каждой дуги графа. Добавление в список имеет константную сложность (см. таблицу 6-1), что даёт нам линейную оценку производительности топологической сортировки O(N + E), где N — это количество узлов в графе, а E — количество дуг. This code is nearly identical to the Cycle Detection algorithm, except it maintains the postorder structure instead of in_stack[]. Using a similar runtime analysis, you can see that each node has one chance to be explored with dfs(), and the inner if state‐ ment is executed once for every directed edge in the graph. Since appending to a list has constant time performance (see Table 6-1), this guarantees that the runtime per‐ formance of Topological Sort is O(N + E), where N is the number of nodes and E is the number of edges.

Иллюстрация 7-13. Как работает топологическая сортировка путем обхода вглубину

На иллюстрации 7-13 видно, что как только очередной вызов dfs() из примера 7-10 заканчивается, в списке postorder содержатся все узлы, зависимости которых уже удовлетворены; эти узлы мы перечислили в виде квадратов с пунктирными границами. Под конец работы функции topological_sort() этот список — в обратном порядке — возвращается функцией. После того, как приложение загрузило электронную таблицу, оно должно пересчитать содержимое ячеек — и порядок подсчёта может указать топологическая сортировка. When each dfs() completes its execution in Listing 7-10, as shown visually in Figure 7-13, postorder contains the ordered list of nodes whose dependencies are satisfied; these are shown in dashed boxes. This list is reversed and returned at the end of topological_sort(). When the spreadsheet application loads a spreadsheet document, it can recompute the cells in the order determined by Topological Sort.

Взвешенные графы

Graphs with Edge Weights

В некоторых предметных областях возникают задачи, решить которые можно с помощью графов, каждое ребро которых снабжено числовым значением — весом ребра. Веса можно приписывать и рёбрам обычного графа, и дугам орграфа. Для простоты договоримся, что вес — это положительное число. Some application domains modeled using graphs have a numeric value associated with each edge, typically called the weight of an edge. These edge weights can appear in undirected or directed graphs. For now, assume that all edge weights are positive values greater than 0.

Стэнфордская Большая Коллекция Сетевых Данных (https://oreil.ly/hXqcg) содержит множество наборов данных, например, о связях в социальных сетях. В библиотеке TSPLIB (https://oreil.ly/MdMWm) собраны наборы данных для т. н. «задачи коммивояжёра» (traveling salesman problem, TSP). Программисты десятилетиями изучают методы решения этой задачи, так что примеров накопилось немало. Большая коллекция графов есть на сайте «Карты Путешествий» (https://oreil.ly/qWYsr). Отдельную благодарность хотелось бы выразить Джеймсу Тереско за любезно предоставленную таблицу дорог штата Массачусетс (https://oreil.ly/wlEy2).

По таблице дорожных участков штата Массачусетс можно сконструировать граф, в котором каждый узел — это путевая точка (остановка), однозначно определяемая координатами: парой чисел, широтой и долготой. Например, в таблице есть остановка на пересечении шоссе I-90 и I-93 в район Бостона.

Широта этой точки (угол на север из центра Земли от экватора) равна 42.34642, а долгота (угол на запад от Гринвичского меридиана) равна –71.060308. Ребро меду двумя узлами — это участок дороги, а вес ребра — это длина пути между остановками в милях. Если соединить все остановки дорогами, получится схема, представленная на иллюстрации 7-14. From the data set of highway fragments in Massachusetts, let’s create a graph where each node in the graph represents a waypoint from the data set, represented by a (lati‐ tude, longitude) pair of values. For example, one waypoint is the intersection of high‐ ways I-90 and I-93 in Boston. It is identified by a latitude value of 42.34642 (which means it is north of the equator) and a longitude value of –71.060308 (which means it is west of Greenwich, England). An edge between two nodes represents a highway fragment: the weight of the edge is the length of the highway fragment in miles. Dif‐ ferent roads connect these waypoints together, leading to the highway infrastructure shown in Figure 7-14.

Иллюстрация 7-14. Схема дорожной сети штата Массачусетс

Как теперь определить кратчайшее — в милях — расстояние от самой западной остановки (на границе со штатом Нью-Йорк) до крайнего востока штата — остановки на Тресковом Мысе? Попробуем обход вширину. Результат показан на иллюстрации серой полужирной линией, его длина — 236.5 миль. Пусть состоит из 99 рёбер, проходит через ту самую остановку на перекрёстке I-90/I-93 в Бостоне, и это самый короткий путь от старта до финиша — если считать количество остановок (или рёбер графа). А вот будет ли этот кратчайшим, если измерять пройденное расстояние? Похоже, что нет. To determine the shortest route (in terms of total mileage) from the westernmost highway in Massachusetts (on the New York Border) to the easternmost highway (on Cape Cod), start with Breadth First Search to compute a 236.5-mile path (highlighted in Figure 7-14). This 99-edge path passes through the identified waypoint on highway I-90/I-93 in Boston and is the shortest path (from the source to the target) in terms of the total number of edges. But is it the shortest total path in accumulated mileage when considering edge weights? It turns out the answer is no.

Мы знаем, что обход вглубину не находит кратчайшего пути: на иллюстрации 7-15 мы видим найденный с его помощью извилистый путь, он имеет длину аж в 485.2 мили и содержит 267 рёбер. Направленный обход (на иллюстрации не показан¹²) сделал неправильный выбор где-то в самом начале пути и нашёл путь из 141 ребра длиной в 245.2 мили. А вот выделенный чёрным на иллюстрации 7-14 кратчайший путь, в котором 210 рёбер, но длина которого всего 210.1 мили, был найден с помощью алгоритма Дейкстры — им-то мы сейчас и займёмся. We know Depth First Search offers no guarantee on path length: Figure 7-15 contains the wandering 485.2-mile journey with 267 edges produced by Depth First Search. A Guided Search algorithm makes a poor decision early in its journey (not shown here) to compute a 245.2-mile path with 141 edges. The other visualized path in Figure 7-14, which steadily progresses in a southeasterly direction, contains 128 edges and requires only 210.1 miles; Dijkstra’s algorithm shows how to compute this solution.

Иллюстрация 7-15. Очень длинный путь, найденный при обходе вглубину

Алгоритм Дейкстры

Dijkstra’s Algorithm

Эдсгер Вибе Дейкстра — нидерландский учёный, один из создателей академического базиса компьютерной науки и отменный программист, автор уникальных несколько алгоритмов, столь же впечатляющих, сколь и изящных, носят его имя. Алгоритм поиска кратчайшего суммарного пути от заданного узла ко всем достижимым узлам во взвешенном графе так и называется — алгоритм Дейкстры, а класс задач, им решаемых — «нахождение кратчайшего пути из заданной точки». Несколько позже мы рассмотрим пример, в котором по заданному графу (или орграфу) с неотрицательными весами рёбер¹³, алгоритм Дейкстры заполняет два словаря: dist_to[], где хранится кратчайшее суммарное расстояние от входного узла до данного, и edge_to[], содержащий историю обхода. Edsger Dijkstra (pronounced DIKE-stra), a scientist from the Netherlands, was one of the intellectual founders of the discipline of computer science, and his algorithms are as elegant as they are insightful. Dijkstra developed an algorithm that computes the shortest path of accumulated edge weights from a designated source node to all reachable nodes in a weighted graph. This problem is known as the “single-source shortest path” problem. Given an undirected (or directed) graph, G, with non- negative weights associated with each edge,9 Dijkstra’s algorithm computes dist_to[] and edge_to[] structures, where dist_to[v] is the length of the shortest accumula‐ ted path from the source node to v, and edge_to[] is used to recover the actual path.

На иллюстрации 7-16 приведён простейший взвешенный орграф. Вес дуги (a, b) равен 6, дуги (a, c) — 10, а (b, c) — 2. Поэтому кратчайшим путём от a до c оказывается не прямой, длиной 10, а окольный — из двух дуг суммарной длины 8. A sample weighted, directed graph is shown in Figure 7-16. The edge (a, b) has a weight of 6. There is an edge from a to c with weight of 10, but a path from a to b (with weight of 6) to c (with weight of 2) has an accumulated total of 8, which represents a shorter path. The shortest path from a to c contains two edges and a total weight of 8. 9 This allows for some edge weights to be zero. If any edge weight is negative, you will need the Bellman–Ford algorithm (presented later in this chapter).

Не в каждом графе, особенно ориентированном, можно построить путь между двумя любыми узлами. Кратчайшее расстояние от b до c равно, а вот кратчайшее расстояние от c до b — бесконечность, потому что вдоль имеющихся дуг путь от c до b проложить нельзя. When the graph is directed, it may be impossible to construct a path between two nodes. The shortest distance from b to c is 2, but the shortest distance from b to a is infinity because there is no way to construct a path using the existing edges.

Иллюстрация 7-16. Суммарная длина кратчайшего пути из a в c — 8

Для работы с графом алгоритму Дейкстры нужна особая структура данных — индексированная приоритетная очередь с порядком возрастания. Индексированная приоритетная очередь — это некоторое расширение функций приоритетной очереди, которую мы изучали в главе 4. В обеих структурах каждому хранимому значению ставится в соответствие приоритет. И там, и там для хранения используется массив из N элементов — в нашем случае это количество узлов в графе. В отличие от очереди с порядком убывания, которую мы рассмотрели в четвёртой главе, метод .dequeue() снимает из начала очереди элемент с наименьшим приоритетом.

Далее в этом разделе идёт постоянная путаница в стиле: «наивысший приоритет, то есть наименьшее числовое значение приоритета», зачем автор сделал так — не знаю, бороться с этим времени уже нет. -- FrBrGeorge 2023-02-03 15:15:40

Dijkstra’s algorithm requires an abstract data type known as the indexed min priority queue, designed specifically to work with graph algorithms. The indexed min priority queue extends the priority queue data type introduced in Chapter 4. An indexed min priority queue associates a priority with each value. The min priority queue is con‐ structed with an initial storage based on N, where N is the number of nodes in the graph being processed. The dequeue() operation removes the value whose priority is smallest numerically, in contrast to the max priority queue discussed in Chapter 4.

Самое важное дополнение индексированной очереди — это метод .decrease_priority(значение, приоритет). Он понижает текущий приоритет значения до более низкого приоритета. В результате соответствующий элемент продвигается ближе к началу очереди, обгоняя другие элементы с бо́льшими значениями приоритета. Для обычной приоритетной очереди, которую мы изучали ранее, такая операция была бы довольно неэффективной потому что для поиска конкретного значения (которому надо понизить приоритет) пришлось бы просматривать всю очередь, затратив на это O(N) действий. The most important operation is decrease_priority(value, lower_priority) that efficiently reduces the priority of value to a lower priority. In effect, decrease_prior ity() can adjust the priority of an existing value so that it could move ahead of other values in the priority queue. The priority queue implementations described earlier are unable to provide an efficient decrease_priority() function, since they would have to search the entire priority queue in O(N) to locate the value whose priority changes.

Обычно в индексированной приоритетной очереди в качестве значений используются целые числа от 0 до N - 1. Приоритеты при этом хранятся в обычном массиве, а доступ к ним происходит просто по значению-индексу. Но в Python мы можем использовать словарь — тогда значения могут быть любыми константами.

Как видно из примера 7-11, класс IndexedMinPQ устроен и работает почти так же, как приоритетная очередь на основе кучи, которую мы исследовали в четвёртой главе. Вместо того, чтобы хранить объекты типа Entry, мы заведём два списка: .values[n] будет хранить значения элементов, а .priorities[n] — их приоритеты. Методы .swim() и .sink() такие же, как в очереди на основе кучи (подробнее см. в примерах 4-2 и 4-3), так что мы их не приводим. Главное отличие — словарь .location, который хранит информацию, обратную списку values: в .location[v] находится индекс значения элемента v в списке .values (и его приоритета в списке .priorities)¹⁴. Дополнительная информация помогает нам не искать значение по всей очереди, а получать его индекс за константное (с учётом возможного масштабирования) время O(1) (о том, как при этом используется хеширование, мы говорили в главе 3). As shown in Listing 7-11, the structure and functionality of IndexedMinPQ is nearly the same as the heap-based max priority queue presented in Chapter 4. Instead of storing Entry objects, IndexedMinPQ stores two lists: values[n] stores the value for the nth item in the heap, while priorities[n] stores its associated priority. The swim() and sink() methods are identical to the heap-based priority implementation (shown in Listing 4-2 and Listing 4-3), so they are omitted. The primary change is a location dictionary that stores the index position in these lists for each value in IndexedMinPQ. This extra information allows you to determine the location in the heap for any value in amortized constant O(1) time, using the results of hashing (dis‐ cussed in Chapter 3).

Метод .swap() нужно доработать, потому что помимо обмена местами двух элементов очереди, нужно также менять местами соответствующие значения в списке priorities и обновлять содержимое словаря location, чтобы в IndexedMinPQ сохранялась способность быстрого поиска любого значения. The changes to swap() ensure that whenever two items in the heap are swapped, their respective entries in location are updated. This way IndexedMinPQ can efficiently locate any value in the priority queue.

   1 class IndexedMinPQ:
   2   def less(self, i, j):
   3     return self.priorities[i] > self.priorities[j]                      # 1
   4 
   5   def swap(self, i, j):
   6     self.values[i], self.values[j] = self.values[j], self.values[i]     # 2
   7     self.priorities[i], self.priorities[j] = self.priorities[j], self.priorities[i]
   8 
   9     self.location[self.values[i]] = i                                   # 3
  10     self.location[self.values[j]] = j
  11 
  12   def __init__(self, size):
  13     self.N          = 0
  14     self.size       = size
  15     self.values     = [None] * (size+1)                                 # 4
  16     self.priorities = [None] * (size+1)
  17     self.location   = {}                                                # 5
  18 
  19   def __contains__(self, v):                                            # 6
  20     return v in self.location
  21 
  22   def enqueue(self, v, p):
  23     self.N += 1
  24     self.values[self.N], self.priorities[self.N] = v, p                 # 7
  25     self.location[v] = self.N                                           # 8
  26     self.swim(self.N)

• Пример 7-11. Основные свойства индексированной приоритетной очереди Listing 7-11. Structure of an indexed min priority queue

1. Поскольку мы строим очередь с порядком возрастания, более высокий приоритет (и положение ближе к началу очереди) будет у элемента j с меньшим числовым значением приоритета, чем у элемента i. Because this is a min priority queue, item i is of lower priority than item j if its priority is a larger numeric value.

2. В методе .swap() поменяем местами значения и приоритеты двух элементов, i-го и j-го. swap() switches the values and priorities for items i and j.

3. Там же в методе .swap() обновим соответствующие значения в словаре сохранённых индексов location. swap() updates the respective locations for items i and j.

4. Для каждого из N элементов в массиве values будет под соответствующим индексом лежать значение, а в массиве priorities — приоритет. values stores the value of the nth item; priorities stores the priorities of the nth item.

5. В словаре location хранятся индексы элементов очереди в массивах values и priorities. location is a dictionary that returns the index position into values and priori ties for each value that is enqueued.

6. В отличие от обыкновенной приоритетной очереди, индексированная позволяет проверить, есть ли в ней элемент v за (в среднем) константное время O(1) путём поиска в словаре location. Unlike a traditional priority queue, an indexed min priority queue can inspect location to determine in amortized O(1) time whether a value is being stored in the priority queue.

7. Ещё одно небольшое исправление — в методе .enqueue(). Чтобы добавить пару (v, p) в очередь, v записывается в values[N], а p — в priorities[N], где N — индекс очередной свободной ячейки. To enqueue a (v, p) entry, place v in values[N] and p in priorities[N], which is next available bucket.

8. Также в методе .enqueue() нужно запомнить индекс v, и только после этого выполнить .swim(), который восстановит порядок очереди, если тот нарушился. enqueue() must also associate this new index location with v before invoking swim() to guarantee the heap-ordered property.

Как это и полагается в куче, метод .enqueue() сначала добавляет значение v и его приоритет p в конец массивов, соответственно, values[] и priorities[]. Кроме того, в IndexedMinPQ заявлен быстрый поиск элемента, и в словарь location нужно записать, что значение v лежит под индексом N (напомним, что в куче для простоты вычислений массивы индексируются с единицы). Затем вызывается метод .swim(), который восстанавливает возможно утраченный порядок IndexedMinPQ. As you should expect with a heap, enqueue() first stores the value, v, and its associ‐ ated priority, p, at the end of the values[] and priorities[] lists, respectively. To fulfill its obligation to IndexedMinPQ, it also records that value v is stored in index location N (recall that a heap uses 1-based indexing to make the code easier to under‐ stand). It invokes swim() to ensure the heap-ordered property for IndexedMinPQ.

Итак, словарь location нужен для быстрого поиска индекса любого хранящегося в очереди значения. Метод .decrease_priority(), представленный в примере 7-12, переставляет данное значение ближе к началу очереди IndexedMinPQ путём замены приоритета. Единственное требование: новый приоритет может быть только меньше исходного (как мы помним, это означает более высокий приоритет), после чего элемент «всплывает» на своё место. Through its location[] array, IndexedMinPQ can find the location in the heap for any value that it stores. The decrease_priority() method shown in Listing 7-12 can move any value in the IndexedMinPQ closer to the front of the priority queue. The only restriction is that you can only decrease the numeric value of the priority—which makes it potentially more important—and swim the item up into its proper location.

   1 def decrease_priority(self, v, lower_priority):
   2   idx = self.location[v]                        # 1
   3   if lower_priority >= self.priorities[idx]:    # 2
   4      raise RuntimeError('Wrong priority')
   5 
   6   self.priorities[idx] = lower_priority         # 3
   7   self.swim(idx)                                # 4

• Пример 7-12. Уменьшение приоритета для некоторого значения из IndexedMinPQ/* Listing 7-12. Decreasing priority for a value in IndexedMinPQ */

1. Найдём индекс элемента v в хранилище Find the location, idx, in the heap where v is found.

2. Если lower_priority в действительности не меньше текущего приоритета priorities[idx], сгенерируем исключение RuntimeError. If lower_priority is actually not lower than the existing priority in priori ties[idx], raise a RuntimeError.

3. Уменьшим приоритет v. Change the priority for value v to be the lower priority.

4. При необходимости восстановим порядок в очереди, позволив элементу «всплыть» на своё место. Reestablish heap-ordered property if necessary by swimming this value up.

Метод .dequeue() удаляет значение с наименьшим (то есть наивысшим) приоритетом из начала очереди. Реализация этого метода в IndexedMinPQ несколько сложнее уже виденной нами, потому что дополнительно надо обновлять словарь location — как показано в примере 7-13. dequeue() removes the value with smallest priority value (which means it is the most important). The IndexedMinPQ implementation is more complicated, because it has to properly maintain the location dictionary, as shown in Listing 7-13.

   1 def dequeue(self):
   2   min_value = self.values[1]                            # 1
   3 
   4   self.values[1] = self.values[self.N]                  # 2
   5   self.priorities[1] = self.priorities[self.N]
   6   self.location[self.values[1]] = 1
   7 
   8   self.values[self.N] = self.priorities[self.N] = None  # 3
   9   del self.location[min_value]                          # 4
  10 
  11   self.N -= 1                                           # 5
  12   self.sink(1)
  13   return min_value                                      # 6

• Пример 7-13. Удаление элемента с наивысшим приоритетом из IndexedMinPQ Listing 7-13. Removing highest-priority value in IndexedMinPQ

1. Запомним min_value — значение с наивысшим приоритетом. Remember min_value, the value with highest priority.

2. Перенесём последнее в хранилище значение (с индексом N) в начало хранилища (с индексом 1) и соответственно обновим location, хранящий индексы в соответствии со значениями. Move the item at location N to the top-level location 1 and ensure that location records the new index position for this value.

3. Заметём следы существования удалённого min_value в хранилище. Remove all trace of the former min_value being removed.

4. Удалим также и индекс min_value в словаре location. Remove min_value entry from location dictionary.

5. Уменьшим на единицу количество элементов в очереди, а затем вызовем .sink(1), дабы восстановить порядок. Reduce number of entries before invoking sink(1) to reestablish heap-ordered property.

6. Вернём значение, приоритет которого был наивысшим (у этого значения была наименьшая величина приоритета). Return the value associated with entry of highest priority (which is the one with smallest magnitude).

В структуре данных IndexedMinPQ постоянно поддерживается следующее свойство: если значение v есть а приоритетной очереди, то location[v] содержит индекс idx соответствующего элемента в хранилище, то есть values[idx] — это v, а priorities[idx] — его приоритет, p. The IndexedMinPQ data structure ensures the invariant that if v is a value stored by the priority queue, then location[v] points to an index location, idx, such that val ues[idx] is v and priorities[idx] is p, where p is the priority for v.

Индексированная приоритетная очередь используется в алгоритме Дейкстры для вычисления длины наименьшего пути от заданного входного узла src до любого узла орграфа. В процессе обхода составляется словарь dist_to[v], в котором хранится минимальное вычисленное на данный момент расстояние от src до любого узла v в графе. Если узел недостижим из src, в словаре хранится некоторое актуально бесконечное значение. По мере продвижения обхода мы ищем такие пары u и v, дуга между которыми имеет вес wt, что dist_to[u] + wt < dist_to[v] — иными словами, расстояние от src до v больше, чем суммарное расстояние от src до u, а оттуда — до v по дуге (u, v). Dijkstra’s algorithm uses an IndexedMinPQ to compute the length of a shortest path from a designated src node to any node in a graph. The algorithm maintains a dictio‐ nary, dist_to[v], to record the length of the shortest known computed path from src to each v in the graph: this value may be infinite for nodes not reachable from src. As the algorithm explores the graph, it looks for two nodes, u and v, connected by an edge with weight of wt such that dist_to[u] + wt < dist_to[v]: in other words, the distance from src to v is shorter if you follow the path from src to u and then cross to v along the edge (u, v).

Последовательный просмотр узлов в поисках таких укорачивающих расстояние дуг делает алгоритм Дейкстры похожим на обход вширину, где порядок вершим в очереди просмотра зависит от количества шагов до входа. Результаты уже проделанного поиска хранятся в dist_to[v], а остальные узлы добавляются в индексированную очередь сообразно с приоритетом, который равен текущему удалению узла от src. Вначале известно только что dist_to[src] — это 0 (потому что src и есть вход), а остальные расстояния бесконечны. В очереди IndexedMinPQ в этом время находятся все узлы, и у всех у них приоритет бесконечен, кроме нулевого приоритета входного узла src. Dijkstra’s algorithm shows how to find these special edges methodically, similar to the way Breadth First Search uses a queue to explore nodes based on their distance from src (in terms of number of edges). dist_to[v] summarizes the results of the active search, and IndexedMinPQ organizes the remaining nodes to be explored by priority, which is defined as the accumulated length of the shortest path for each node from src. When the algorithm starts, dist_to[src] is 0 because that node is the source, and all other distances are infinity. All nodes are then enqueued in the IndexedMinPQ with priority equal to 0 (for the source node, src) or infinity for other nodes.

Необходимости помечать узлы как посещённые в алгоритме Дейкстры нет, потому что в приоритетной очереди всегда находятся только неисследованные узлы. В процессе обхода из очереди поочерёдно удаляются по одному узлу, расстояние до которого от входа наименьшее. Dijkstra’s algorithm does not need to mark nodes as having been visited, since the min priority queue contains only those active nodes to be explored. One by one, the algorithm removes from the min priority queue the node whose total accumulated distance is the smallest.

   1 from math import inf
   2 
   3 def dijkstra_sp(G, src):
   4   N = G.number_of_nodes()
   5 
   6   dist_to = {v:inf for v in G.nodes()}          # 1
   7   dist_to[src] = 0
   8 
   9   impq = IndexedMinPQ(N)                        # 2
  10   for v, dist in dist_to.items():
  11     impq.enqueue(v, dist)
  12 
  13   def relax(e):
  14     n, v, weight = e[0], e[1], e[2][WEIGHT]     # 5
  15     if dist_to[n] + weight < dist_to[v]:        # 6
  16       dist_to[v] = dist_to[n] + weight          # 7
  17       edge_to[v] = e                            # 8
  18       impq.decrease_priority(v, dist_to[v])     # 9
  19 
  20   edge_to = {}                                  # 3
  21   while not impq.is_empty():
  22     n = impq.dequeue()                          # 4
  23     for e in G.edges(n, data=True):
  24       relax(e)
  25 
  26   return (dist_to, edge_to)

• Пример 7-14. Алгоритм Дейкстры находит кратчайшие расстояния до всех узлов графа из заданного узла Listing 7-14. Dijkstra’s algorithm to solve single-source shortest path problem

1. В словаре dist_to расстояние до каждого узла равно inf¹⁵, а расстояние до src — нулю. Initialize dist_to dictionary to infinity for all nodes except src, which is 0.

2. Поставим все узлы в очередь impq с соответствующими приоритетами. Enqueue all N nodes into impq to prepare for while loop.

3. Каждый элемент edge_to[v] будет хранить дугу, которая привела кратчайшим путём к v. edge_to[v] records the edge terminating at v found during the search.

4. Возьмём из очереди узел n, путь до которого от src кратчайший. Просмотрим все исходящие из него дуги e вида (n, v, weight) (чтобы получить дуги с весами, надо передать методу networkx.Graph.edges() дополнительный параметр data=True). Для каждого v проверим, не короче ли путь до него через n нынешнего кратчайшего пути. Find node, n, that has shortest computed path from src. Explore its edges (n, v, weight) to see if a new shortest path to v has been found. networkx requires data = True to retrieve edge weights.

5. Дуга — это последовательность вида узел n, узел v, данные data, где (n, v) — это собственно дуга, а её вес — одна из составляющих объекта data. Extract n, v, and weight from the edge (n, v).

6. Если путь от src до v оказался длиннее, чем суммарный путь от src до n и далее от n до v, значит, мы нашли новый кратчайший путь. If distance to n added to edge weight to v is smaller than best path so far to v, then a shorter path has been found.

7. Обновим информацию о кратчайшем пути до v. Update the shortest known distance to v.

8. Запишем дугу e (от n до v) в edge_to[v]: именно она привела нас в v кратчайшим путём. Record the edge (n, v) that brought Dijkstra’s algorithm to v along the new short‐ est path.

9. Самый важный момент: уменьшим значение приоритета в impq до длины нового кратчайшего пути. При этом в цикле while будем продолжать выбирать узел с наименьшим вычисленным расстоянием от src. Most importantly, reduce priority in impq to new shortest distance so while loop will be able to retrieve node with shortest computed path.

На иллюстрации 7-17 показаны первые три шага цикла while из примера 7-14. Каждый узел n хранится в IndexedMinPQ с приоритетом, равным наименьшему вычисленному расстоянию dist_to[n] (оно показано в небольшой пунктирной рамке рядом с каждым узлом). На очередном проходе while мы удаляем узел n из impq и проверяем, нет ли более короткого пути из src в некоторый узел v через n. Назовём этот процесс сокращением контура. Поскольку кратчайшее расстояние служит приоритетом IndexedMinPQ, мы можем быть уверены, что в алгоритме Дейкстры путь до каждого снятого из начала очереди impq элемента действительно кратчайший. Figure 7-17 presents the first three iterations through the while loop in Listing 7-14. IndexedMinPQ stores each node, n, using as priority the smallest computed distance, dist_to[n], which is shown in a small dashed box attached to each node. With each pass through the while loop, a node, n, is removed from impq to check whether its edges lead to a new shortest path from src to some node, v, by traveling from src to n and then from n to v. This process is called relaxing an edge. The IndexedMinPQ prioritizes which nodes are explored first—in this way, Dijkstra’s algorithm guaran‐ tees that the shortest path for each node dequeued from impq is correct.

Что следует учитывать при оценке быстродействия алгоритма Дейкстры? The runtime performance of Dijkstra’s algorithm is based on several factors:

Время постановки в очередь всех узлов

Вначале в очередь добавляются все N узлов: src с приоритетом 0 и N - 1 оставшийся узел с бесконечным приоритетом. При добавлении узлов с бесконечным приоритетом .swim() не делает ничего, потому что условие порядка и так выполнено, и единственный раз при добавлении src узел с приоритетом 0 «всплывает» в начало очереди не более, чем за логарифмическое время. Быстродействие этого шага, следовательно, O(N).

The cost of enqueuing all N nodes The first node enqueued is src with priority of 0. All remaining N – 1 nodes are enqueued with infinite priority; since infinity is greater than or equal to every value already in impq, swim() does nothing, resulting in O(N) performance.

Время выборки всех узлов из очереди

В процессе обхода элементы снимаются из начала очереди по одному. Мы помним, что impq — это двоичная куча, и сложность операции .dequeue() в ней логарифмическая (O(log N)), стало быть, сложность снятия всех N элементов можно оценить как O(N log N).

The cost of retrieving N nodes from impq Dijkstra’s algorithm dequeues each node from impq. Since impq is stored as a binary heap, dequeue() is O(log N), which means the total time to remove all nodes is O(N log N) in the worst case.

Время перебора всех дуг графа

Быстродействие перебора всех рёбер графа зависит от того, как они в нём смоделированы. Если с помощью матрицы смежности, на полный перебор потребуется порядка O(N²) действий. Если с помощью списка смежности — то порядка O(N + E).

The cost of accessing all edges in G The structure of the graph determines the runtime performance of retrieving all edges in the for e in G.edges() loop. If the graph stores edges using an adja‐ cency matrix, accessing all edges requires O(N2) performance. If the graph stores edges using an adjacency list, retrieving all edges requires just O(E + N).

Время сокращения контуров

Функция relax() вызывается для каждой дуги графа. Если при этом вычисленная длина кратчайшего пути уменьшилась, в вызове relax() может встретиться вызов .decrease_priority(). Этот метод в свою очередь вызывает метод двоичной кучи .swim(), сложность которого O(log N). Следовательно, общее время, затраченное на вызов relax() для каждой дуги будет O(E log N), где E — количество дуг в графе.

The cost of relaxing all E edges The relax() function is called on all edges in the graph. Each one has a chance to reduce the shortest computed path length to some node, so there can be as many as E invocations of decrease_priority(). This function relies on the swim() binary heap function, whose runtime performance is O(log N). The accumulated time will have a runtime performance of O(E log N).

Если хранить дуги в списке смежности, алгоритм Дейкстры имеет сложность порядка O((E + N) log N), а если в матрице смежности — порядка O(N²). С ростом графа использование матрицы смежности довольно быстро становится неэффективным. If the graph stores edges using an adjacency list, Dijkstra’s algorithm has an O((E + N) log N) classification. If the graph uses an adjacency matrix instead, the perfor‐ mance is O(N2). For large graphs the matrix representation is simply inefficient.

В процессе обхода алгоритмом Дейкстры создаются два словаря: dist_to[v], в котором записан суммарный вес — кратчайший вычисленный путь от src до каждого v, и edge_to[v], в котором хранится последняя на кратчайшем пути из src в v дуга (u, v). Из edge_to сравнительно несложно восстановить полный путь от src до произвольного v. Механизм восстановления очень похож на тот, что мы видели в примере 7-4, но edge_to[], как это показано вы примере 7-15, нужно проходить от конца к началу. Dijkstra’s algorithm computes two structures: dist_to[v] contains the length of the shortest path by accumulated edge weights from src to v, while edge_to[v] contains the last edge (u, v) on the actual shortest path from src to v. The full path from src to each v can be recovered, much like Listing 7-4, except this time following the edge_to[] structure backward, as shown in Listing 7-15.

   1 def edges_path_to(edge_to, src, target):        # 1
   2   if not target in edge_to:
   3     raise ValueError('Unreachable')             # 7
   4 
   5   path = []
   6   v = target                                    # 2
   7   while v != src:
   8     path.append(v)                              # 3
   9     v = edge_to[v][0]                           # 4
  10 
  11   path.append(src)                              # 5
  12   path.reverse()                                # 6
  13   return path

• Пример 7-15. Восстановление пути из edge_to[] Listing 7-15. Recovering actual path from edge_to[]

1. Восстановим путь от src до произвольного target с помощью edge_to. edge_to[] structure is needed to recover path from src to any target.

2. Начнём с конца пути, target. To recover the full path, start at target.

3. Пока мы не добрались до входного узла src, добавим v в список path, в котором в обратном порядке, начиная с target, строится путь от src до target. As long as v is not src, append v to path, a backward list of nodes found on path from src to target.

4. Нулевой элемент дуги (u, v), хранящейся в edge_to[v], — это u, предыдущий узел на пути. Подставим его на место v. Set v to become u, the prior node in the edge (u, v) from edge_to[v].

5. Мы вышли из цикла while, когда добрались до src, так что его надо добавить в путь отдельно. Once src is encountered, the while loop terminates, so src must be appended to complete the backward path.

6. Переставляем элементы path в обратном порядке — теперь там содержится путь от src до target. Reverse the list so all nodes appear in proper order from src to target.

7. Если узел target отсутствует в edge_to[], значит, из src он не достижим. If target is not in edge_to[], it is not reachable from src.

Алгоритм Дейкстры работает только с неотрицательными весами. Вес может быть отрицательным, например, если граф моделирует финансовые транзакции, которые предусматривают и платежи, и возврат денег. С отрицательным весом дуги алгоритм Дейкстры, как мы видим на иллюстрации 7-18, может и не справиться. Dijkstra’s algorithm will work as long as all edge weights are nonnegative. A graph might have a negative edge, for example, because it represents the refund of a finan‐ cial transaction. If an edge has a negative edge weight, it could break Dijkstra’s algo‐ rithm (as shown in Figure 7-18).

Иллюстрация 7-18. Неудачно присвоенный отрицательный вес дуги нарушает работу алгоритма Дейкстры

На иллюстрации 7-18 мы видим, как алгоритм Дейкстры обрабатывает три узла из impq. Остаётся узел b. Кратчайший путь от a до d уже вычислен, и на третьем шаге мы снимаем d из impq. Поэтому когда на следующем шаге (которого на иллюстрации уже нет), мы снимем b из impq и сократим дугу (b, d), обновить внезапно образовавшееся кратчайшее расстояние до d уже не догадаемся: этого узла нет в плане разведки. Очевидно, проблема с отрицательными весами — в том, что уже пройденный путь может уменьшиться после добавления в него ещё одной дуги, но алгоритм Дейкстры не умеет «возвращаться» и пересматривать уже вычисленные кратчайшие пути. In Figure 7-18, Dijkstra’s algorithm processes three nodes from impq until just b is left. As you can see in the last row, Dijkstra’s algorithm has computed its current shortest path from a to d. In its final pass through its while loop (not shown in the figure), Dijkstra’s algorithm will remove node b from impq and relax the edge (b, d). Unfortunately, this edge suddenly reveals a shorter path to d. However, Dijkstra’s algorithm has already removed node d from impq, finalizing its shortest path compu‐ tation. Dijkstra’s algorithm cannot “go back” and adjust the shortest path, so it fails.

Алгоритм Дейкстры может не отследить дугу с отрицательным весом, потому что мы предполагаем, что при добавлении очередной дуги в некоторый путь его длина не уменьшается. Алгориртм Беллмана-Форда лишён этого недостатка, он может находить кратчайшие пути из входного узла в графе до произвольного, даже если веса рёбер имеют разные знаки. Но есть и исключение: если в графе присутствует отрицательный контур (то есть контур, суммарный вес которого отрицателен) любой путь, включающий вершину этого контура, можно сделать меньше, чем любое наперёд взятое число — достаточно пройтись по нему несколько раз! На иллюстрации 7-19 показаны два графа, в каждом из которых по две положительные и две отрицательные дуги. В том, что слева, нет отрицательного контура: начнём обход с a, и сперва пройдём единственную дугу (a, b) с весом 1. Если потом пройтись один раз по контуру b → d → c → b (суммарный вес которого 1), общая длина a → b → d → c → b будет равна 2, так что кратчайшая дистанция от a останется равной 1. А вот в графе справа присутствует отрицательный контур b → d → c → b, суммарная длина которого равна -2. Таки образом, мы можем сделать путь от a до b равным любому нечётному отрицательному числу, просто пройдясь по этому контуру соответствующее число раз. Например, вес пути a → b → d → c → b → d → c  → b равен -3. Dijkstra’s algorithm can fail with negative edge weights since it assumes that extend‐ ing an existing path with a new edge will only maintain or increase the total distance from the source. The Bellman–Ford algorithm computes the shortest total distance from src to any other node in the graph, even with negative edge weights, with one exception: if a negative cycle exists in the graph, then the concept of a shortest path does not apply. The graph on the left side of Figure 7-19 has two negative edges, but no negative cycle. Using the edge (a, b), the shortest distance from a to b is 1. If you travel over the longer path a → b → d → c → b, the total accumulated edge weight distance is 2, so the shortest path between a and b remains 1. In the graph on the right, however, there is a negative cycle between nodes b, d, and c; that is, if you travel the edges clockwise in order from b → d → c → b, the total accumulated edge weight is –2. In this graph, the shortest distance between a and b has no meaning: you can construct a path to make this distance any odd negative number by cycling through the b → d → c → b loop a number of times. The accumulated edge weights for a → b → d → c → b → d → c → b is –3, for example.

Иллюстрация 7-19. Два графа с отрицательным весом дуг, только один из которых содержит отрицательный контур

Алгоритм Беллмана-Форда находит кратчайшее расстояние от входного узла до любого другого, применяя совсем другой подход, в котором годятся и отрицательные веса дуг. Реализация этого алгоритма приведена в примере 7-16, многое в ней взято из алгоритма Дейкстры. К счастью нам не надо сначала проверять граф на наличие отрицательных контуров (как это приходилось делать перед топологической сортировкой: в процессе обхода графа алгоритмом Беллмана-Форда отрицательный контур определится сам — в этом случае порождается исключение. The Bellman–Ford implementation provides a completely different approach to solv‐ ing the same single-source shortest path problem. It works even when there are edges with a negative weight. Listing 7-16 shows the Bellman–Ford implementation, which contains many familiar elements from Dijkstra’s algorithm. The good news is that you do not have to search for a negative cycle in the graph as you had to do with Topological Sort shown earlier in the chapter. As Bellman–Ford executes, it can detect when a negative cycle exists and raises a runtime exception in response.

   1 from math import inf
   2 
   3 def bellman_ford(G, src):
   4   dist_to = {v: inf for v in G.nodes()}               # 1
   5   dist_to[src] = 0
   6   edge_to = {}                                        # 2
   7 
   8   def relax(e):
   9     u, v, weight = e[0], e[1], e[2][WEIGHT]
  10     if dist_to[u] + weight < dist_to[v]:              # 5
  11       dist_to[v] = dist_to[u] + weight                # 6
  12       edge_to[v] = e                                  # 7
  13       return True                                     $ 8
  14     return False
  15 
  16   for i in range(G.number_of_nodes()):                # 3
  17     for e in G.edges(data=True):                      # 4
  18       if relax(e):
  19         if i == G.number_of_nodes() – 1:              # 5
  20           raise RuntimeError('Negative Cycle exists in graph.')
  21 
  22   return (dist_to, edge_to)

• Пример 7-16. Реализация алгоритма Беллмана-Форда Listing 7-16. Bellman–Ford algorithm implementation

1. В словаре dist_to будет храниться текущий кратчайший путь. Поначалу там бесконечность для всех узлов, а для src — ноль. Initialize dist_to dictionary to infinity for all nodes except src, which is 0.

2. В edge_to[v] хранится дуга, по которой поиск привёл нас в v. edge_to[v] records the edge terminating at v found during the search.

3. Цикл на N проходов (по количеству узлов графа) Make N passes over the graph.

4. Цикл по всем дугам графа (u, v). Используем ту же функцию relax(), что и в алгоритме Дейкстры — сокращаем вес пути от src до v, если суммарный вес аналогичного пути через u оказывается меньше. For every edge e = (u, v) in the graph, use the same relax() concept as Dijk‐ stra’s algorithm; see if e improves on an existing shortest path from src to v by going through u.

5. Если путь до u и вес дуги в сумме меньше текущего значения кратчайшего пути до v, мы нашли более короткий путь до v. If distance to u added to edge weight to v is smaller than best path so far to v, then a shorter path has been found.

6. Запишем это значение на место старого. Update the shortest known distance to v.

7. Запомним дугу, которая привела нас в v кратчайшим путём. Record the edge (u, v) that brought algorithm to v along the new shortest path.

8. Если relax() вернул True, мы нашли более короткий путь до v. If relax() returns True, then a new shortest path was found to v.

9. В алгоритме Беллмана-Форда мы N раз перебираем все E дуг. Если на последнем проходе выясняется, что какая-то дуга e всё ещё укорачивает какой-то путь, значит, мы нашли отрицательный контур. Bellman–Ford makes N passes over all E edges. If in the final pass, an edge, e, is found that still reduces the shortest distance from src to some v, there must be a negative cycle in the graph.

Почему этот алгоритм работает? Просто потому, что в графе их N узлов в самом длинном пути не может быть больше N - 1 узла. Так что если в цикле for переменная i прошла N - 1 итерацию, попытавшись сократить все дуги графа, то даже если единственный путь состоял из всех дуг одновременно, мы и его уже проверили. Значит, больше не должно остаться дуг, позволяющих сократить уже отмеренное расстояние. Поэтому мы продлили цикл ещё на один проход: если и на N-ом шаге можно сократить какую-то дугу, значит, происходит это посредством отрицательного контура. Why does this algorithm work? Observe that in a graph with N nodes, the longest possible path that can exist in the graph has no more than N – 1 edges. After the for loop over i has made N – 1 iterations attempting to relax any edge in the graph, it must have processed this potentially longest path in the graph: there should no longer be any edge left that relaxes the shortest total distance. For this reason, the for loop iterates N times. If on the final pass, the algorithm is able to relax an edge, then the graph must contain a negative cycle.

Полный поиск кратчайших путей

All-Pairs Shortest Path

Пока что обход графа в алгоритмах из этой главы начинался из заранее заданного узла. Полный поиск кратчайших путей должен выдать информацию о наименьшем суммарном весе дуг на пути из любого узла в графе до любого. В неориентированном графе кратчайшее расстояние от любого узла u до любого другого v совпадает с кратчайшим расстоянием от v до u. В графе любого типа какой-то узел v может быть не достижим из какого-то узла u, в этом случае расстояние считается бесконечным. В орграфе кратчайшие пути от u до v и от v до u могут не совпадать, или u может быть не достижим из v, даже если v достижим из u. The search algorithms presented in this chapter start their search from a designated source node. As its name suggests, the all-pairs shortest path problem asks to compute the shortest possible path of accumulated edge weights between any two nodes, u and v, in the graph. In an undirected graph, the shortest path from u to v is the same as the shortest path from v to u. In both undirected and directed graphs, node v may not be reachable from u, in which case the shortest path distance would be infinity. In a directed graph, u may be reachable from v even if v is not be reachable from u.

Идея подсчитать все возможные кратчайшие расстояния от произвольного u до произвольного v кажется запредельно трудоёмкой. В самом деле, даже в простейшем графе с иллюстрации 7-20 на поиск кратчайшего расстояния между одними только d и c нужно порядочно времени, сколько же его уйдёт для исследования всех пар узлов! Между d и c есть дуга с весом 7, но путь d → b → a → c оказывается короче: его вес равен 6. The search must return information to be able to recover the actual shortest paths between any u and v, but this seems incredibly challenging. For the small directed graph in Figure 7-20, it takes time to determine the shortest path between d and c, let alone all possible pairs of nodes. While there is an edge from d to c with weight 7, there is a path d → b → a → c whose total accumulated distance is 6, which is shorter.

Иллюстрация 7-20. Граф, на котором мы будем вычислять кратчайшие пути

Прежде, чем мы углубимся в изучение алгоритма, который решает эту задачу, стоит заранее договориться, что он будет возвращать в качестве результата. Воспользуемся структурой данных из алгоритма Дейкстры и его предшественников и слегка доработаем её. Всякий раз, когда в предыдущих алгоритмах шла речь о пути из заданного узла src к произвольному v, мы использовали словарь с индексом v. Теперь же, поскольку речь зайдёт о пути от произвольного u к произвольному v, индексом словаря станет пара — кортеж (u, v). Before delving into the details of an algorithm that solves this problem, consider what the algorithm needs to return as its result. It is similar to what you have seen for Dijk‐ stra’s algorithm and the earlier search algorithms:

Снова пришлось немного подправить не вполне Python-овский стиль автора. -- FrBrGeorge 2023-02-09 19:56:38

1. В словаре dist_to[u, v] будем хранить вычисленный кратчайший путь между двумя узлами, u и v. Пока путь из u в v не подсчитан, dist_to[u, v] бесконечно. • dist_to[u][v]—a two-dimensional structure that holds the value of the shortest path between every pair of nodes, u and v. If there is no path from u to v, dist_to[u][v] = infinity.

2. В словаре node_from[u, v] будем записывать последний узел на вычисленном кратчайшем пути от u до v. Это поможет нам восстановить весь кратчайший путь от u до v. • node_from[u][v]—a two-dimensional structure that contains information to make it possible to compute for any two nodes, u and v, the actual shortest path between them.

Что предлагается делать. The following insight helps lead to a solution.

Начнём с того, что занесём в dist_to[u, v] вес дуги (u, v), если такая есть, а если нет — бесконечность для разных u и v и ноль, когда u и v совпадают. Для каждой дуги (u, v) запишем в node_from[u, v] информацию о том, что это последняя (она же первая) дуга на кратчайшем пути из u в v, и стало быть, в v этим путём мы попали из u. На иллюстрации 7-21 показаны словари node_from и dist_to в виде квадратных таблиц: по вертикали идёт первый узел пары, по горизонтали — второй. Для заполнения таблиц мы использовали граф с иллюстрации 7-16. Start by initializing dist_to[u][v] to be the weight associated with each edge u to v; if no edge exists in the graph, then set dist_to[u][v] to be infinity. Also initialize node_from[u][v] to be u to record that the last node on the shortest path from u to v is u. Figure 7-21 presents the node_from[][] and dist_to[][] after initializing these values using the graph from Figure 7-16.

"Иллюстрация 7-21. Что хранится в node_from и dist_to при полном поиске кратчайших путей

Теперь выберем узел b в качестве t и проверим, можно ли найти два таких узла, u и v, чтобы сумма расстояний от u до t и от t до v была меньше вычисленного кратчайшего пути dist_to[u, v]. В нашем небольшом примере dist_to[a, b] равно 6, а dist_to[b, c] равно 2, так что кратчайший путь от a до c лежит именно через b — теперь он равен 8. Вдобавок нужно обновить node_from[a, c], потому что предыдущий узел на кратчайшем пути теперь b. Принцип тот же, что и в алгоритме Дейкстры, когда мы сокращаем контур. Now imagine that you select k = b and check if you can find any two nodes, u and v, where the path from u to k and then from k to v is shorter than the best known short‐ est computed distance of dist[u][v]. In this small example, dist[a][b] is 6, and dist[b][c] is 2, which means that the shortest distance from a to c now goes through b and is a total of 8. In addition, you can set node_from[a][c] to b to record this fact. This situation is similar to the relaxation computation that was central to Dijkstra’s algorithm.

Здесь и далее — недосмотр редактора: вместо dist_to используется нигде не описанное dist; я исправил. Кроме того, в параграфе выше описывается несуществующая картинка, которую мне пришлось нарисовать. -- FrBrGeorge 2023-02-11 10:59:19

Как мы видим, словарь node_from[u, v] выполняет ту же функцию, что и аналогичный node_from[] в предыдущих алгоритмах: хранит последний узел на кратчайшем пути до v, только путь задаётся не один, от входного узла, а много — от любого узла в графе. I now have a clear explanation for node_from[u][v]: it stores the last node on the shortest path from node u to v. It is similar in spirit to the node_from[] structures computed by earlier search algorithms, although it is more complicated.

Мы поочерёдно просматриваем все узлы в цикле с переменной t и перебираем все пары узлов u и v в надежде на то, что расстояние между ними можно сократить с помощью этого t (как мы это сделали двумя параграфами раньше). Как только увидим, что dist_to[u, t] + dist_to[y, v] меньше dist_to[u, v], сокращаем значение dist_to[u, v] до этой суммы, а заодно обновляем node_from[u, v] — теперь там должен быть узел на пути от t, node_from[t, v]. One by one, you set k to each of the nodes in the graph and try to find a pair of nodes, u and v, that could reduce its shortest path distance using the logic in the pre‐ vious paragraph. Once you know that dist_to[u][k] + dist_to[k][v] is shorter than dist_to[u][v], you can update the value for dist_to[u][v]. You can also set node_from[u][v] to equal node_from[k][v].

Иными словами, поскольку мы уже вычислили dist_to[t, v], мы знаем, что node_from[t, v] содержит последний узел на кратчайшем пути от t к v — а значит, он будет последним и на новом кратчайшем пути от u к v, который идет через t, и следует приравнять node_from[u, v] к node_from[t, v]. Когда мы будем восстанавливать полный путь, мы пройдём вспять от v к этому t, а в node_from[u, t] будет лежать предыдущий узел на кратчайшем пути от u. In other words, since dist_to[k][v] has already been computed, you know that node_from[k][v] is the last node on the shortest path from k to v—and since the path from u to v now goes through k, set node_from[u][v] equal to node_from[k][v]. To reconstruct the full path, work backward from v to k, then node_from[u][k] con‐ tains the former node on the shortest path all the way back to u.

Все наши соображения выглядят не слишком простыми, потому что в самом алгоритме нет выделенной части, которая, скажем, вычисляет кратчайший путь от конкретного u к конкретному v. Мы храним не всю информацию: вычисляемые в процессе работы пути не обязаны быть кратчайшими — мы можем пересчитать их позже. Возьмём граф с иллюстрации 7-20 и заполним наши структуры его информацией о кратчайших путях; результат изображён на иллюстрации 7-22. В таблице dist_to записаны кратчайшие пути между двумя узлами, её координаты соответствуют первому и второму узлам в паре. Например, в строке, помеченной как a, хранятся кратчайшие дистанции от узла a до всех остальных узлов графа. В частности, dist_to[a, c] равно 3, потому что кратчайший путь от a до c — это a → c, то есть единственная дуга (a, c) с весом 3. Кратчайший путь от а до d, dist_to[a, d] — это a → b → d с суммарным весом 9. These concepts are challenging because they are abstract—I do not compute and store each shortest path between every u and v; rather, I store partial details about the paths to compute them later. Given the graph in Figure 7-20, Figure 7-22 contains the result that an algorithm must compute. The dist_to[][] structure contains the com‐ puted shortest distances between any two nodes. The dist_to[a] row, for example, contains the computed shortest distances from a to all other nodes in the graph. In particular, dist_to[a][c] is 3 because the shortest path from a to c is along the (a, c) edge with a total distance of 3. The shortest path from a to d, dist_to[a][d], is along the path a → b → d, whose accumulated total distance is 9.

Иллюстрация 7-22. Какими получаются dist_to, node_from и полные кратчайшие пути для графас иллюстрации 7-20

Решение задачи полного поиска кратчайших путей — словари node_from и dist_to. На иллюстрации 7-22 приведены сами эти пути: по вертикали — u, по горизонтали — v, на пересечении — полный путь от u до v. Становится понятнее, откуда такие значения в dist_to, при этом предпоследний узел в полном кратчайшем пути от u до v — выделен серым. Нетрудно заметить, что выделенный узел соответствует node_from[u, v]. A solution to the all-pairs shortest path problem needs to compute node_from[][] and dist_to[][]. To explain the values in node_from[][], Figure 7-22 shows the resulting shortest paths between each pair of nodes, u and v. In each of the shortest paths between u and v, the second-to-last node in the shortest path is highlighted. You can see that this highlighted node corresponds directly to node_from[u][v].

Рассмотрим кратчайший путь от d до c: d → b → a → c. Он состоит из пути от d до a и финальной дуги (a, c). Таким образом наши два словаря подсказывают рекурсивное решение задачи: последний узел на пути из d в c — это a, который как раз и хранится в  node_from[d, c]. Consider the shortest path from d to c, which is the path d → b → a → c. Decompose this path into a path from d to a followed by the final edge from a to c, and you can see the recursive solution hidden in these two-dimensional structures. node_from[d][c] equals a, which means the last node in the shortest path from d to c is the node a.

Продолжая в том же духе, обнаруживаем, что кратчайший путь от d к a идёт веред b, и именно b записан в node_from[d, a]. Next, the shortest path from d to a goes through b, which is why node_from[d][a] equals b.

Алгоритм Флойда-Уоршелла

Floyd–Warshall Algorithm

Задачу полного поиска кратчайших путей и идею её решения мы обсудили, теперь рассмотрим формализацию этой идеи: алгоритм Флойда-Уроршелла. Напомним: идея была в том, чтобы найти такие три узла u, v и t, чтобы окольный путь из u в v через t был короче прямого. Now that you are familiar with the all-pairs shortest path problem, I can present the Floyd–Warshall algorithm. The key to the algorithm is its ability to find three nodes, u, v, and k, such that there is a shorter path from u to v by going through k.

В примере 7-17 алгоритм Флойда-Уроршелла для начала заполняет node_from[] и dist_to[] данными из списка дуг — это часть исходного графа. На иллюстрации 7-23 представлен результат инициализации обоих словарей. In Listing 7-17, Floyd–Warshall initializes node_from[][] and dist_to[][] using just the edge information provided in the initial graph. These initial values are depic‐ ted in Figure 7-23.

Иллюстрация 7-23. Инициализация dist_to[] и node_from[] данными из графа G

В node_from[u, v] записано либо None (на иллюстрации — прочерк), либо u. В dist_to[u, v] лежит либо 0, если u — это v, либо вес дуги (u, v), если такая есть, а если её нет, то бесконечность (на иллюстрации — INF)¹⁶. The entry node_from[u][v] is either None (shown as a dash) or u, to reflect the row of the entry. dist_to[u][v] is 0 whenever u is equal to v. When u and v are distinct, dist_to[u][v] is either the weight of the edge from u to v, or infinity (shown by INF) when there is no edge between u and v.

   1 from math import inf
   2 
   3 def floyd_warshall(G):
   4     dist_to = {(u, v): 0 if u is v else inf for u in G.nodes() for v in G.nodes()}
   5     node_from = {(u, v): None for u in G.nodes() for v in G.nodes()}    # 1
   6     for u, v, data in G.edges(data=True):                               # 2
   7         dist_to[u, v] = data[WEIGHT]                                    # 3
   8         node_from[u, v] = u                                             # 4
   9 
  10     for t in G.nodes():
  11         for u in G.nodes():
  12             for v in G.nodes():
  13                 new_len = dist_to[u, t] + dist_to[t, v]                 # 5
  14                 if new_len < dist_to[u, v]:
  15                     dist_to[u, v] = new_len                             # 6
  16                     node_from[u, v] = node_from[t, v]
  17 
  18     return (dist_to, node_from)                                         # 7

• Пример 7-17. Алгоритм Флойда-Уоршелла Listing 7-17. Floyd–Warshall Algorithm

1. Создадим словари по всем возможным парам узлов. Заполняем dist_to нулями для путей из узла в тот же узел, и inf для путей между разными узлами, потому что мы ещё не знаем, есть ли эти пути. По той же причине заполняем node_from значением None. dist_to and node_from will be two-dimensional structures. Each is a dictionary containing sub-dictionaries dist_to[u] and node_from[u]. For each u row, initialize dist_to[u][v] to be infinity to reflect that each node, v, is initially unreachable. For each u row, initialize node_from[u][v] to be None to reflect that there may not even be a path from u to v.

2. Теперь добавим информацию из дуг графа. В цикле используется представление дуги в виде кортежа из двух вершин и массива с данными. Make sure to set dist[u][u] = 0 to reflect that the distance from u to itself is 0.

3. Изначальная длина пути из u в v — это вес дуги (u, v). For each edge e = (u,v) from u, set dist_to[u][v] = weight of e to reflect that the shortest distance from u to v is the edge weight for e.

4. Поскольку пока кратчайший путь из u в v совпадает с дугой (u, v), последний узел на пути к v — это u. Record that u is the last node on the shortest path from u to v. In fact, it is the only node on the path, which contains just the edge (u, v).

5. Вычислим длину обходного пути u → t → v. Select three nodes—k, u, and v—and compute new_len, the total path length from u to k added to the path length from k to v.

6. Если обходной путь короче предыдущей вычисленной длины, запомним новую длину dist_to[u, v] и обновим последний узел на пути от u к v, теперь node_from[u, v] совпадает с node_from[t, v]. If new_len is smaller than the computed length of the shortest path from u to v, set dist_to[u][v] to new_len to record the shortest distance, and record that the last node on the shortest path from u to v is the last node on the shortest path from k to v.

7. По вычисленным словарям dist_to и node_from можно восстановить кратчайший путь между любыми узлами. Вернём эти словари. Return computed dist_to[][] and node_from[][] structures so actual shortest paths can be computed for any two nodes.

Сам алгоритм оказался на удивление компактным. Сначала мы заполняем node_from и dist_to в предположении, что никакой узел не достижим ниоткуда, кроме себя самого. Затем добавляем в них сведения о дугах: вес пути и начальную вершину. Внешний цикл по t перебирает узлы, через которые мы будем пытаться строить обходные пути в паре узлов, два внутренних перебирают узлы этой пары — u и v. Мы проверяем, не короче ли путь u → t → v текущего пути u → v. По мере перебора узлов мы рассмотрим все улучшения, и в конце концов найдём настоящий ответ. Once the algorithm initializes node_from[][] and dist_to[][], the code is quite brief. The outermost for loop over k seeks to find two nodes, u and v, such that the shortest path from u to v can be shortened by first traveling from u to k and then from k to v. As k explores more nodes, it eventually tries every possible improvement and ultimately computes the final correct result.

Скажем, t — это a. Тогда во внутренних циклах по u и v в какой-то момент окажется, что u = b, а v = c. Проверяя, не короче ли путь от b к c через a, мы обнаружим, что dist_to[b, c] на данный момент бесконечно (см. иллюстрацию 7-23), а dist_to[b, a] = 2 и dist_to[a, c] = 3, и 5 явно короче бесконечности. Обновляем dist_to[b, c], а заодно и записываем a в node_from[b, c] в знак того, что в только что найденном коротком пути от b к c предпоследний узел — это a. When k is a, its inner for loops over u and v discover that for u = b and v = c, a shorter path exists from b to c if it goes through node a. Observe that dist_to[b][a] = 2 and dist_to[a][c] = 3, whose total of 5 is smaller than infinity (the current computed dist_to[b][c] value from Figure 7-23). Not only is dist_to[b][c] set to 5, but also node_from[b][c] is set to a to reflect the change in the newly discovered shortest path, b → a → c: note that the second-to-last node on the shortest path from b to c is a.

Ещё один способ понять работу алгоритма — это посмотреть, как именно меняются значения dist_to[u, v]. До первого прохода внешним циклом dist_to содержит только прямые пути из u в v, без возможности пойти в обход. Допустим, на первом проходе t стало равно a. Тогда под конец этого прохода в dist_to[u, v] будет лежать длина кратчайшего пути из u в v, в котором может присутствовать a. Например, найдётся более короткий путь b → a → c из b до c. Another way to explain why the algorithm works is to evaluate the values contained in dist[u][v]. Before the first pass through the for loop over k, dist[u][v] records the length of the shortest path from any u to any other v in the graph that doesn’t involve any node other than u and v. After the first k loop iteration has ended for k = a, dist[u][v] records the length of the shortest path from any u to any other v that can also involve a. The shortest path from b to c is b → a → c.

На втором проходе t станет равно b, и мы найдём все случаи, когда уже имеющийся путь длиннее, чем возможный путь через b. Например, кратчайший путь между d и c был длиной 7 — по длине соответствующей дуги в графе. Но теперь мы посчитали обходной путь через b: сначала от d к b (длиной 1), затем от b к c (длиной 5), и он оказался короче — равен 6. На иллюстрации 7-24 приведён результат работы алгоритма Флойда-Уоршелла после прохода циклом первых двух узлов — a и b. When k is b during its second pass through the for loop, Floyd–Warshall finds five different pairs of nodes u and v for which the path from u to v is shorter if the path goes through b. For example, the shortest path from d to c had been 7 because of edge (d, c) in the graph. Now, however, the algorithm finds a shorter path that involves b, specifically traveling from d to b (with distance 1) and then traveling from b to c (with distance 5) for a shorter accumulated path of length 6. The final values in dist[][] and node_from[][] are shown in Figure 7-24.

Иллюстрация 7-24. Как изменились node_from и dist_to после проверки a и b

Интересно, а почему мы не проверяем, что t, u и v не равны друг другу? Во-первых, dist_to[u, u] уже равно нулю, так что на результат эта проверка не повлияет. Во-вторых, заметного прироста производительности она не даст, а вот читать и понимать программу без неё легче.

В результате алгоритм Флойда-Уоршелла не потребовал каких-то особенных структур данных, и просто последовательно перебрал все N³ троек (t, u, v) из узлов графа. This algorithm surprisingly uses no advanced data structures but methodically checks all N3 total (k, u, v) nodes:

1. Во время инициализации node_from и dist_to запоминаются все кратчайшие пути от u к v, состоящие из одной дуги. • When Floyd–Warshall initializes node_from[][] and dist_to[][], it computes all shortest paths between any u and v that involve just a single edge.

2. На первом шаге вычисляются кратчайшие пути между любыми двумя узлами, при условии, что в них не больше двух дуг и помимо самих узлов в пути может присутствовать только узел a. • After the first pass through k, the algorithm has computed all shortest paths between any u and v that involve up to two edges, limited to u, v, and node a.

3. На втором шаге вычисляются кратчайшие пути, которые состоят не более, чем из трёх дуг и не более, чем из четырёх узлов — начального, конечного, a и b. • After the second pass through k, it has computed all shortest paths between any u and v that involve up to three edges, limited to u, v, and nodes a and b.

4. На k-м шаге рассматриваются пути, в которых, помимо начального и конечного узлов могут встречаться первые k элементов из списка узлов, а рёбер — не более k + 1.

После того, как внешний цикл по t переберёт все N узлов, в словарях окажутся сведения о кратчайших путях между любыми узлами, причём в них могут встречаться любые узлы графа и вплоть до N + 1 дуги. В действительности путь из N вершин не может содержать больше N - 1 дуги, так что упомянутых пределов хватит на то, чтобы подсчитать настоящие кратчайшие расстояния для любых пар u и v в графе. Once the outer for loop over k has completed processing N nodes, Floyd–Warshall has computed the shortest paths between any u and v that involve up to N + 1 edges and involve any node in the graph. Now, since a path over N nodes can only have N – 1 edges, this means that Floyd–Warshall correctly computes the distance for the shortest paths over all u and v in the graph.

Осталось только написать функцию, которая по результатам работы алгоритма восстанавливает конкретный кратчайший путь. Эта функция приведена в примере 7-18 — она мало чем отличается от такой же функции из примера 7-4, только в качестве индексов в словарях используется пара узлов, а не один. The code to recover the actual shortest path is shown in Listing 7-18. This code is nearly identical to Listing 7-4, except now it processes a two-dimensional node_from[][] structure.

   1   def all_pairs_path_to(node_from, src, target):        # 1
   2     if node_from[src, target] is None:
   3       raise ValueError('Unreachable')                   # 7
   4 
   5     path, v = [], target                                # 2
   6     while v != src:
   7       path.append(v)                                    # 3
   8       v = node_from[src, v]                             # 4
   9 
  10     path.append(src)                                    # 5
  11     path.reverse()                                      # 6
  12     return path

• Пример 7-18. Функция all_pairs_path_to() строит кратчайший путь по результатам работы алгоритма Флойда-Уоршелла Listing 7-18. Code to recover the shortest path as computed by Floyd–Warshall

1. Чтобы построить весь путь от src до target , функции нужен словарь node_from. node_from[][] structure is needed to recover path from src to any target.

2. Начнём с конца — с target. To recover the full path, start at target.

3. Пока не добрались до начала, то есть пока v не совпадает с src, добавляем v в список path (узлы пути от src до target в обратном порядке). As long as v is not src, append v to path, a backward list of nodes found on path from src to target.

4. Отступаем на шаг: теперь v — это предыдущий узел на пути, который мы взяли из node_from[src, v]. Set v to become the prior node in the search as recorded by node_from[src][v].

5. Когда мы добираемся до src, цикл завершается, остаётся только добавить в список сам src. Once src is encountered, the while loop terminates, so src must be appended to complete the backward path.

6. Восстанавливаем порядок узлов в пути, меняя обратный на прямой. Reverse the list so all nodes appear in proper order from src to target.

7. Если node_from[src, target] так и остался равным None, значит target не достижим из src. If node_from[target] is None, target is not reachable from src.

Заключение

Summary

С помощью графов можно моделировать данные самых разнообразных предметных областей — от географических карт до социальных сетей или последовательностей в биоинформатике. Граф состоит из узлов и соединяющих их рёбер, причём рёбра могут быть или не быть ориентированными, а также иметь или не иметь числовые веса. Множество естественно возникающих интересных задач на графах имеют практическое применение, и мы умеем их решать: Graphs can model a variety of application domains, ranging from geographic data to bioinformatic information to social networks. The edges of a graph can be directed or undirected, and the edges may store numeric weights. Given a graph, there are many interesting questions that naturally arise:

1. Связный ли граф? Обойдём его вглубину и посмотрим, все ли узлы затронул обход. • Is the graph connected? Apply Depth First Search and see if every node in the graph was visited.

2. Есть ли контур в ориентированном графе? Обойдём его вглубину и будем проверять, не привёл ли обход к вершине, всё ещё находящейся в множестве активного поиска — это и будет означать цикл. • Does a directed graph contain a cycle? Apply Depth First Search and maintain extra state while searching to detect if a cycle exists.

3. Как попасть из входной вершины в некоторую другую, чтобы путь занимал наименьшее количество рёбер? Обойдём граф из этой вершины вширину: длину кратчайшего пути можно вычислить сразу, а сам путь можно восстановить, если для каждого узла запомнить, откуда мы пришли в него кратчайшим путём. • Given two nodes, u and v, in a graph, what is the shortest path from u to v in terms of the number of edges involved? Apply Breadth First Search to compute a solution.

4. Как найти кратчайшее расстояние (сумму весов дуг в пути) во взвешенном графе из входного узла до любого другого? Алгоритм Дейкстры вычисляет эти расстояния, а также запоминает предпоследний узел каждого кратчайшего пути: по этим данным можно восстановить любой кратчайший путь до узла, достижимого из входного. • Given a weighted graph and starting node, s, what is the shortest path from s to every other node, v, in the graph in terms of accumulated weights of the edges? Apply Dijkstra’s algorithm to compute these distances and an edge_to[] struc‐ ture that can be used to recover the actual paths from s to any reachable node, v.

5. Можно ли решить ту же задачу — поиск кратчайшего расстояния из входного узла до любого другого, — если веса дуг в графе имеют разные знаки, но отрицательных контуров в нём нет? Применим алгоритм Беллмана-Форда. • If a graph contains negative edge weights—but has no negative cycles—is it still possible to determine the shortest path between a starting node, s, and every other node, u, in terms of accumulated weights of the edges? Apply Bellman– Ford.

6. Как эффективно решить задачу поиска всех кратчайших расстояний (суммарных весов дуг в путях) во взвешенном графе от любого узла к любому другому? Воспользуемся алгоритмом Флойда-Уоршелла, который составит таблицы, в которых для каждой пары узлов будет храниться кратчайшее расстояние и предпоследних узел в кратчайшем пути, — по этим таблицам можно будет восстановить полный путь. • Given a weighted graph, what is the shortest path between any two nodes, u and v, in terms of accumulated weights of the edges? Apply Floyd–Warshall to com‐ pute both the distances and a node_from[][] structure that can be used to recover the actual paths.

Изобретать собственный структуры данных для моделирования графа в Python не стоит: лучше воспользоваться имеющимися сторонними библиотеками, например NetworkX, в которой есть несколько различных типов графов и уже реализовано множество алгоритмов. When working with graphs, do not implement your own data structures to represent these graphs: better to use an existing third-party library, such as NetworkX, so you can benefit immediately from the many algorithms that it provides.

Тренировочные задания

Challenge Exercises

1. Хоть это и не рекомендуется, обход вглубину можно написать в виде рекурсивной функции¹⁷. Как всегда, получится ещё более читаемый текст программы, но большие графы обрабатывать этим алгоритмом будет невыгодно — а на Python, глубина рекурсии в котором ограничена тысячью вызовами, просто невозможно. Однако не небольших лабиринтах такое решение работать будет, и посмотреть на это стоит. Доработайте пример 7-19 так, чтобы пространство активного поиска содержалось в явно заданном стеке, а было распределено по контекстам рекурсивного вызова внутренней функции dfs(). Достаточно вызывать dfs() на каждом помеченном узле, и откатываться к предыдущему вызову для просмотра ещё не исследованных направлений. Depth First Search can be coded recursively. However, doing so has a weakness when searching large graphs, because Python imposes a recursion limit of around 1,000. Still, for small mazes, you can modify the search to use a recursive search. Modify the skeleton code in Listing 7-19 to recursively invoke Depth First Search. Instead of using a stack to store marked nodes to be removed and pro‐ cessed, only invoke dfs() on marked nodes, and let the recursion unwind to find paths not chosen.

   •    1         def dfs_search_recursive(G, src):
        2           marked = {}
        3           node_from = {}
        4 
        5             def dfs(v):
        6               """Допишите эту рекурсивную функцию."""
        7 
        8             dfs(src)
        9             return node_from
     

     • Пример 7-19. Допишите рекурсивную реализацию поиска вглубину Listing 7-19. Complete recursive implementation for Depth First Search

2. Функцию path_to(), которая строит полный путь для обхода вширину и обхода вглубину тоже можно написать рекурсивно (с теми же ограничениями, что и в предыдущем задании). Реализуйте рекурсивную генератор-функцию path_to_recursive(node_from, src, target), которая с помощью yield порождает последовательность узлов на пути от src до target. 2. The path_to() function to compute the path for Breadth First Search and Depth First Search can be implemented recursively. Implement path_to_recur sive(node_from, src, target) as a Python generator that yields the nodes in order from src to target.

3. Напишите функцию recover_cycle(G), которая определяет, есть ли контур в орграфе G, и возвращает его (или None, если контура нет). 3. Design a recover_cycle(G) function that detects when a cycle exists and returns the cycle.

4. Напишите функцию recover_negative_cycle(G), которая дополняет алгоритм Беллмана-Форда, отыскивая отрицательный контур. Сконструируйте своё исключение NegativeCycleError, унаследовав его от RuntimeError — это исключение будет порождаться, когда обнаружится, что некоторый путь можно сокращать постоянно. Возьмите последнюю дугу этого пути и постарайтесь найти весь цикл. Передайте цикл в качестве параметра порождаемого исключения¹⁸ . 4. Design a recover_negative_cycle(G) function to augment Bellman–Ford by creating a custom NegativeCycleError class extending RuntimeError that stores the negative cycle that was discovered in the graph. Start with the offending edge that was relaxed, and try to find a cycle including this edge.

5. Подберите такой простой орграф из N=5 узлов, чтобы алгоритму Беллмана-Форда для вычисления кратчайшего пути от определённого узла понадобилось 4 прохода. Для простоты веса всех дуг пускай будут единичными. Подсказка: результат зависит от порядка добавления дуг в граф. В частности, в алгоритме Беллмана-Форда дуги перебираются в том порядка, в каком их возвращает  G.edges(). 5. Construct a sample directed, weighted graph with N = 5 nodes that requires 4 iterations by Bellman–Ford to properly compute the shortest path from a desig‐ nated source node. For simplicity, assign each edge a weight of 1. As a hint, it depends on the way that the edges are added to the graph. Specifically, Bellman– Ford processes all edges in order based on how G.edges() returns the edges.

6. Исследуйте эффективность всех трёх вариантов обхода — вглубину, вширину и направленного для случайного лабиринта размером N × N. Для этого (1) останавливайте обход как только выход найден, и (2) отмечайте количество помеченных узлов. 6. For randomly constructed N × N mazes, compute the efficiency of Depth First, Breadth First, and Guided Search in reaching the designated target. Do this by revising each search algorithm to (a) stop when it reaches the target, and (b) report the total number of nodes in the marked dictionary.

   Теперь для разных N, равных степеням двойки от 4 до 128, сгенерируйте по 512 случайных графов и подсчитайте среднее количество помеченных узлов для каждого из вариантов обхода. Должно получиться, что направленный обход — в среднем самый быстрый, а обход вширину — в среднем самый медленный. For N equal to powers of 2 ranging from 4 to 128, generate 512 random graphs and compute the average number of marked nodes for each search technique. You should be able to demonstrate that Guided Search is the most efficient, while Breadth First Search is the least efficient.

   Затем создайте наихудший случай для направленного обхода, в котором он работает почти так же медленно, как обход вширину. На иллюстрации 7-25 приведён пример довольно «плохого» лабиринта размером 15×15: стены в нём образуют своеобразное «корыто», которое не даёт добраться до выхода. Направленный поиск сначала безрезультатно обшаривает все (N - 2)² ячейки «корыта», и только затем переваливает через стенку и обходным путём добирается до выходного узла. В файле ch07/maze.py репозитория есть класс Maze с методом .initialize(), который заполняет весь лабиринт стенками и формирует соответствующие структуры давнных, останется только удалить большую часть вертикальных и горизонтальных стен (они хранятся в массивах .south_wall[] и .east_wall[] соответственно). Now construct a worst case problem instance for Guided Search that forces it to work almost as hard as Breadth First Search. The sample 15 × 15 maze in Figure 7-25 contains walls that form a “U” shape that blocks the path to the exit. Guided Search will have to explore this entire inner space of (N-2)2 cells before “spilling over” one of the edges to find the roundabout path to the exit. The initialize() method in Maze will be helpful; you will have to manually remove south and east walls to create this shape.

   • Вариант наихудшего случая для направленного обхода

     Figure 7-25. Worst case maze for Guided Search

7. Не содержащий контуров орграф называется сетью. Алгоритм Дейсктры в худшем случае показывает производительность O((E + N) log N), но на сети он работает быстрее и может отыскать кратчайшие пути из заданного узла за O(E + N) действий. С помощью топологической сортировки построим линеаризацию вершин графа, и пройдёмся по ним в линеаризованном порядке, сокращая каждую дугу, исходящую из очередной вершины. Сконструируйте достаточное количество сетей в виде квадратных решёток и экспериментально подтвердите оценку сложности. Для простоты веса всех дуг будем считать единичными. Например, длина кратчайшего пути из узла 1 к узлу 16 в решётке с иллюстрации 7-26 равна 6. 7. A directed graph, DG, with no cycles is called a directed acyclic graph, or DAG for short. Dijkstra’s algorithm in the worst case is classified as O((E+N) log N), but for a DAG you can compute the single-source, shortest path in O(E+N). First, apply Topological Sort to produce a linear order of the nodes. Second, process each node, n, in linear order, relaxing the edges that emanate from n. There is no need to use a priority queue. Confirm runtime behavior on random mesh graphs where each edge has a weight of 1. In the mesh graph in Figure 7-26, the shortest distance from node 1 to node 16 is 6.

   • Иллюстрация 7-26. Орграф без контуров — сеть — на котором поиск кратчайших путей из заданного узла работает быстрее

     Figure 7-26. A directed, acyclic graph for single-source, shortest path optimization

8. Некоторые водители не пользуются платными дорогами — такими, как I-90 в Массачусетсе. В нашем графе дорог Массачусетса ребро (u, v) принадлежит трассе I-90, если метки обоих узлов содержат маркировку 'I-90'. Изо всех 2826 рёбер 51 штука принадлежит I-90. Удалите эти рёбра из графа и высчитайте кратчайшее расстояние из самой западной точки штата в центр Бостона (точка, обведённая кружком на иллюстрации 7-14, помеченная как I-90@134&I-93@20&MA3@20(93)&US1@I-93(20), потому что там встречаются шесть дорог). Если ехать и по платным дорогам, путешествие занимает 72 ребра суммарной длиной в 136.2 мили. Если же не заезжать на I-90, количество рёбер увеличится до 104, а длина — до 139.5 мили. Напишите программу, которая получает все эти результаты и создаёт файл с изображением «бесплатного» пути.

8. Some drivers prefer to avoid toll roads, such as I-90 in Massachusetts. Given the graph constructed for Massachusetts highways, an edge (u, v) is part of I-90 if the label for both u and v contains 'I-90'. Of the original 2,826 edges, 51 edges are part of I-90: remove these edges from the graph and compute the shortest distance from the westernmost point in Massachusetts to downtown Boston, whose label (as circled in Figure 7-14) is the string I-90@134&I-93@20&MA3@20(93)&US1@I-93(20) representing where six highways converge. With no restrictions, the trip requires 72 edges and a total distance of 136.2 miles. However, if you choose to avoid I-90, the trip requires 104 edges and a total distance of 139.5 miles. Write code to produce these results and output an image file showing the altered route.