Часть 2: Поиск на графах
Nuances of programmingПеревод статьи gladius: "Section 2: Searching a Graph"
Предыдущие части: Часть 1
Основные методы поиска на графах
Введение
К настоящему времени мы уже изучили представление графа в памяти, и теперь мы начнем практически применять эту информацию Существует два наиболее распространенных метода поиска на графах, которые в дальнейшем станут основой для более сложных алгоритмов. Этими двумя методами является поиск в глубину и поиск в ширину.
Начнем с метода поиска в глубину, в котором используется стек. Этот стек либо может быть представлен явно (с помощью стекового типа данных ), либо неявно - при помощи рекурсивных функций.
Стэк
Стек - одна из самых простых доступных структур данных. Над стеком можно совершать четыре основных операции:
- Push – добавляет элемент в верхнюю часть стека.
- Pop ‑ удаляет верхний элемент из стека.
- Top ‑ возвращает верхний элемент стека.
- Empty – проверяет, пуст стек или нет.
В C ++ это делается классом стека в STL:
#include <stack> std::stack<int> myStack;
В Java, используется класс стека:
import java.util.*; Stack stack = new Stack();
В C# используется класс стека:
using System.Collections; Stack stack = new Stack();
Поиск в глубину
Научимся использовать методы поиска для решения задач! Поиск в глубину хорошо подходит в том случае, если отсутствуют требования поиска оптимального по каким либо критериям или наикратчайшего пути, или при обходе графа нам важно пройти через все его узлы. Пример задачи с topcoder - это классический вариант применения метода поиска в глубину, называемый закраской. С представлением об операции закраски знакомы все пользователи графических приложений. Идея метода состоит в том, чтобы закрасить определенную область одним цветом.
Данную концепцию удобно рассмотреть с помощью метода поиска в глубину. Основная идея состоит в том, чтобы остановившись в некотором узле, поместить все посещенные по пути к нему узлы в стек. Тогда поиск следующего узла осуществляется с помощью операции извлечения его из стека и размещения в стек всех соседних, непосредственно соединенных с ним узлов. Мы будет повторять эту операцию до тех пор, пока не посетим все узлы. Это ключевое свойство поиска поиска в глубину и при этом мы посещаем один и тот же узел не более одного раза, так как в противном случае возможно зацикливание вплоть до бесконечного перебора узлов графа. Поэтому мы помечаем посещенные узлы, во избежание повторного прохода через них.
Таким образом, базовая структура алгоритма будет выглядеть примерно так:
dfs(node start) {
stack<node> s;
s.push(start);
while (s.empty() == false) {
top = s.top();
s.pop();
if (top is not marked as visited) {
check for termination condition (have we reached the node we want to?)
mark top as visited;
add all of top's neighbors to the stack.
}
}
}
Или же можно определить функцию рекурсивно следующим образом:
dfs(node current) {
mark current as visited;
visit all of current's unvisited neighbors by calling dfs(neighbor)
}
Рассмотрим задачу grafixMask (маска с 1 500 точками, SRM 211). В этой задаче, по сути, нужно найти число уже заполненных некоторыми значениями областей в сетке. Работа с сетками (или решетками) с помощью графов – очень мощный метод, с помощью которого решение задачи существенно упрощается.
Примечание переводчика: здесь речь идет о графической маске (grafixMask). Рассматривается полотно прямоугольной формы размером 400 на 600 точек. На нем рисуется набор прямоугольников, координаты которых заданы в массиве rectangles. Дыркой называется максимальное множество соседних точек, не принадлежащих ни одному прямоугольнику. Две точки называются соседними, если они прилегают друг к другу по горизонтали или по вертикали.
Необходимо найти все размеры дырок и вывести их в возрастающем порядке.
Определим граф, в котором каждый узел имеет 4 соединения, по одному на узел выше, слева, справа и ниже. Однако мы можем неявно представлять эти соединения внутри сетки, нам не нужно создавать какие-либо новые структуры данных. Структура, которую мы будем использовать для представления сетки в задаче grafixMask, представляет собой двумерный массив булевых значений, при этом те области, которые мы уже определили для заполнения, будут установлены в состояние true, еще незаполненные области будут установлены в false.
Построить такой массив с помощью заданных значений для этой задачи очень просто и выглядит это примерно следующим образом:
bool fill[600][400];
initialize fills to false;
foreach rectangle in Rectangles
set from (rectangle.left, rectangle.top) to (rectangle.right, retangle.bottom) to true
Теперь у нас есть инициализированная решетка связей. Когда мы хотим переместиться из положения на сетке (x, y), мы можем двигаться вверх, вниз, влево или вправо. Например, когда мы хотим двигаться вверх, мы просто проверяем положение сетки в точке (x, y-1), чтобы определить, значение истинно или ложно. Если положение имеет значение fasle, мы сможем туда перейти, а если true – не сможем.
Теперь нам нужно определить площадь каждой оставшейся области. Мы не хотим считать области или пиксели дважды, поэтому мы установим множество fill[x][y] в состояние true, при проходе через узел в точке (x, y). Это позволит нам выполнить поиск в глубину проходя через все соседние узлы в области и никогда не заходить в какой-либо из узлов дважды – как раз именно то, нам и нужно! Итак, наш цикл после всех настроек все будет выглядеть следующим образом:
int[] result; for x = 0 to 599 for y = 0 to 399 if (fill[x][y] == false) result.addToBack(doFill(x,y));
Этот код проверяет, дошли ли мы до точки (x, y), а затем вызывает doFill (), чтобы закрасить эту область. На этом этапе у нас имеется выбор – определить doFill рекурсивно (это, как правило, самый быстрый и простой способ поиска в глубину), или определить его явно с помощью классов стека. Сначала я расскажу о рекурсивном методе, но вскоре мы увидим, что с рекурсивным методом возникают серьезные проблемы.
Сейчас мы определим doFill, чтобы вернуть размер связанной области и ее начальную точку:
int doFill(int x, int y) {
// Check to ensure that we are within the bounds of the grid, if not, return 0
if (x < 0 || x >= 600) return 0;
// Similar check for y
if (y < 0 || y >= 400) return 0;
// Check that we haven't already visited this position, as we don't want to count it twice
if (fill[x][y]) return 0;
// Record that we have visited this node
fill[x][y] = true;
// Now we know that we have at least one empty square, then we will recursively attempt to
// visit every node adjacent to this node, and add those results together to return.
return 1 + doFill(x - 1, y) + doFill(x + 1, y) + doFill(x, y + 1) + doFill(x, y - 1);
}
Это решение должно хорошо работать, однако есть одно ограничение, связанное с архитектурой компьютерных программ. К сожалению, память для неявного стека, которую мы выше использовали для рекурсии, имеет больше ограничений, чем память общей кучи. В данном случае, скорее всего произойдет переполнение стека из-за применения рекурсивных вычислений, поэтому рассмотрим явный метод решения этой задачи.
Заметка на полях
Память стека используется всякий раз, как вызывается функция; компилятор помещает переменные функции в стек. При использовании рекурсивной функции переменные хранятся в стеке до тех пор, пока не завершится работа функции. Кроме того, любые переменные, которые компилятор должен сохранять для обмена между вызываемыми функциями, также должны быть помещены в стек. Это затрудняет прогноз относительно возможности возникновения сложностей со стеком. Рекомендуем использовать явный поиск в глубину каждый раз, как только у вас возникнет сомнение о величине глубины рекурсии.
В этой задаче можно использовать рекурсию максимум 600 * 400 раз (сначала рассмотрим пустую сетку и глубину стека при первой итерации – сначала алгоритм поиска в глубину зайдет в узел с координатами 0,0, затем 1,0, в 2,0, в 3,0 и так далее вплоть до 599, 0. Затем он перейдет к 599, 1 затем к 598, 1, затем к 597, 1 и т.д. До тех пор, пока он не достигнет узла с координатами 599, 399. Это приведет к помещению в стек в лучшем случае 600 * 400 * 2 целочисленных величин, но в зависимости от того, как работает компилятор, на самом деле в стек может быть помещено и больше чисел. Поскольку одно целое число занимает 4 байта, в стек будет помещено 1 920 000 байт, что может вызвать серьезные проблемы.
Мы можем использовать то же самое определение функции, по структуре функция будет аналогична, но мы при этом обойдемся без применения рекурсии:
class node { int x, y; }
int doFill(int x, int y) {
int result = 0;
// Declare our stack of nodes, and push our starting node onto the stack
stack<node> s;
s.push(node(x, y));
while (s.empty() == false) {
node top = s.top();
s.pop();
// Check to ensure that we are within the bounds of the grid, if not, continue
if (top.x < 0 || top.x >= 600) continue;
// Similar check for y
if (top.y < 0 || top.y >= 400) continue;
// Check that we haven't already visited this position, as we don't want to count it twice
if (fill[top.x][top.y]) continue;
fill[top.x][top.y] = true; // Record that we have visited this node
// We have found this node to be empty, and part
// of this connected area, so add 1 to the result
result++;
// Now we know that we have at least one empty square, then we will attempt to
// visit every node adjacent to this node.
s.push(node(top.x + 1, top.y));
s.push(node(top.x - 1, top.y));
s.push(node(top.x, top.y + 1));
s.push(node(top.x, top.y - 1));
}
return result;
}
Как вы можете видеть, эта функция несколько более ресурсоемка при управлении структурой стека, но преимущество ее заключается в том, что мы можем использовать все пространство памяти, доступное нашей программе, и в этом случае необходимо использовать этот больший объем информации. Однако структура очень похожа, и, если вы сравните две реализации, они окажутся практически эквивалентными.
Поздравляем, мы разрешили нашу первую задачу методов поиска в глубину! Теперь мы перейдем к поиску в ширину.
Если вы хотите практиковать в решение задач с помощью метода поиска в глубину, рекомендуем обратить внимание обратить внимание на некоторые задачи:
TCCC 03 Quarterfinals – Marketing – Div 1 500
TCCC 03 Semifinals Room 4 – Circuits – Div 1 275
Очередь
Очередь - это простое расширение типа данных стека. В то время как стек представляет собой структуру данных типа FILO (first-in last-out – «первым вошел, последним вышел»), очередь представляет собой структуру данных типа FIFO (first-in first-out – «первым вошел, первым вышел»). Это означает, что первый элемент, помещенный в очередь, будет первым, который вы получите при выполнении команды извлечения из очереди – pop ().
Для очереди имется четыре основных операции:
- Push - добавляет элемент в конец очереди
- Pop - удаляет первый элемент из очереди
- Front - возвращает первый элемент очереди
- Empty - проверяет, пуста очередь или нет.
В C ++ все это выполняется на основе класса очереди из STL:
#include <queue> queue<int> myQueue;
В Java, к сожалению, класса Queue нет, поэтому мы будем аппроксимировать его классом LinkedList. Операции в связанном списке хорошо моделируют очередь (и на самом деле иногда очереди выполняются как связанные списки), поэтому это будет не слишком сложно.
Операций с классом LinkedList выглядят следующим образом:
- Push – булево LinkedList.add (Object o)
- Pop – объект LinkedList.removeFirst ()
- Front - объект LinkedList.getFirst ()
- Empty - int LinkedList.size ()
import java.util.*; LinkedList myQueue = new LinkedList();
В C# мы можем использовать класс Queue:
Операций с классом Queue выглядят следующим образом:
- Push – void Queue.Enqueue(Object o)
- Pop – объект Queue.Dequeue()
- Front – объект Queue.Peek()
- Empty – int Queue.Count
using System.Collections; Queue myQueue = new Queue();
Поиск в ширину
Метод поиска в ширину является чрезвычайно полезным. В отличие от поиска в глубину в нем используется структура данных типа "очередь", поэтому порядок, в котором происходит обход узлов иной. Этот метод обладает весьма полезным свойством - если все ребра в графе не имеют веса (или имеют одинаковый вес), найденный в первый раз путь к узлу является самым коротким путем к нему из узла-источника. В этом легко убедиться, если вспомнить, что в алгоритме используется очередь. Когда мы проходим узел и помещаем в очередь всех его соседей, а затем берем следующий узел из очереди, - мы, тем самым, извлекаем соседние узлы из очереди первыми. Таким образом, это свойство объясняется свойствами организации хранения данных в самой очереди - свойством FIFO ("первым вошел, первым вышел"), что, в конечном итоге, оказывается чрезвычайно полезным. Однако мы должны быть крайне осторожны при осуществлении поиска в ширину, так как при повторном посещении одного и того же узла (возникновении циклом на графе) теряется свойство быстрого поиска наикратчайшего пути к узлу из узла-источника.
Основная структура поиска в ширину будет выглядеть следующим образом:
void bfs(node start) {
queue<node> s;
s.push(start);
mark start as visited
while (s.empty() == false) {
top = s.front();
s.pop();
check for termination condition (have we reached the node we want to?)
add all of top's unvisited neighbors to the queue
mark all of top's unvisited neighbors as visited
}
}
Обратите внимание на сходство между этим методом и поиском в глубину, заключающуюся только в используемой структуре данных, и том, что мы отмечаем посещенную вершину, помещая ее в очередь, а вынимая из очереди.
Задача, которую мы будем обсуждать при рассмотрении алгоритма поиска в глубину, немного сложнее, чем в предыдущем примере, поскольку здесь мы имеем дело с немного более сложным пространством поиска. Рассмотрим задачу Pathfinding – задачу поиска наилучшего, оптимального маршрута между двумя точками (1000 из раздела 1 в SRM 156). Еще раз рассмотрим решение задачи на сетке, поэтому мы сможем представить структуру графа неявно.
Краткое изложение задачи состоит в том, что мы хотим обменять позиции двух игроков на сетке. Те части пространства, через которые проход невозможен обозначим символом «X» и пробелами, а через которые возможен – символом «-». Поскольку рассматривается два игрока, структура узлов становится немного сложнее – мы должны представлять позиции игрока А и игрока В. Кроме того, мы больше не сможем использовать массив для хранения посещенных узлов, для этого нам потребуется вспомогательная структура данных. Кроме того, в этой задаче мы разрешаем совершать движения по диагонали, поэтому у нас появляется 9 вариантов – либо мы можем двигаться в одном из 8 направлений, либо оставаться на месте. Еще одно небольшое замечание – игроки не могут просто менять позиции за один ход, поэтому нам необходимо проверять правильность состояния.
Сначала мы создаем структуру узлов и массив посещенных узлов:
class node {
int player1X, player1Y, player2X, player2Y;
int steps; // The current number of steps we have taken to reach this step
}
bool visited[20][20][20][20];
Здесь узел представлен как точка (x, y) игрока 1 и игрока 2. Нам также нужны текущие шаги игроков, которые они совершили, что занять текущее состояние. Это нам необходимо, поскольку в задаче имеется вопрос о минимальном количестве шагов для каждого из двух игроков. Мы уверены на основе свойств поиска в ширину, что мы попадем в конечный узел настолько быстро, насколько это возможно (так как стоимости всех ребер одинаковы и равны единице).
Массив посещений узлов является прямым представлением нашего узла в форме массива, причем первое измерение массива – это player1X, второе – player1Y и т.д. Обратите внимание, что нам не нужно отслеживать пути в массиве посещенных узлов.
Теперь, когда мы создали базовую структуру, можно решать задачу (обратите внимание, что этот код не компилируется):
void pushToQueue(queue<node> q, node v) {
if (visited[v.player1X][v.player1Y][v.player2X][v.player2Y]) return;
q.push(v);
visited[v.player1X][v.player1Y][v.player2X][v.player2Y] = true;
}
int minTurns(String[] board) {
int width = board[0].length;
int height = board.length;
node start;
// Find the initial position of A and B, and save them in start.
queue<node> q;
pushToQueue(q, start)
while (q.empty() == false) {
node top = q.front();
q.pop();
// Check if player 1 or player 2 is out of bounds, or on an X square, if so continue
// Check if player 1 or player 2 is on top of each other, if so continue
// Check if the current positions of A and B are the opposite of what they were in start.
// If they are we have exchanged positions and are finished!
if (top.player1X == start.player2X && top.player1Y == start.player2Y &&
top.player2X == start.player1X && top.player2Y == start.player1Y)
return top.steps;
// Now we need to generate all of the transitions between nodes, we can do this quite easily using some
// nested for loops, one for each direction that it is possible for one player to move. Since we need
// to generate the following deltas: (-1,-1), (-1,0), (-1,1), (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1)
// we can use a for loop from -1 to 1 to do exactly that.
for (int player1XDelta = -1; player1XDelta <= 1; player1XDelta++) {
for (int player1YDelta = -1; player1YDelta <= 1; player1YDelta++) {
for (int player2XDelta = -1; player2XDelta <= 1; player2XDelta++) {
for (int player2YDelta = -1; player2YDelta <= 1; player2YDelta++) {
// Careful though! We have to make sure that player 1 and 2 did not swap positions on this turn
if (top.player1X == top.player2X + player2XDelta && top.player1Y == top.player2Y + player2YDelta &&
top.player2X == top.player1X + player1XDelta && top.player2Y == top.player1Y + player1YDelta)
continue;
// Add the new node into the queue
pushToQueue(q, node(top.player1X + player1XDelta, top.player1Y + player1YDelta,
top.player2X + player2XDelta, top.player2Y + player2YDelta,
top.steps + 1));
}
}
}
}
}
// It is not possible to exchange positions, so
// we return -1. This is because we have explored
// all the states possible from the starting state,
// and haven't returned an answer yet.
return -1;
}
Это оказалось довольно сложным, по сравнению с базовой реализацией поиска в ширину, хотя вы можете отметить основные элементы кода базовой версии. Если хотите попрактиковаться в решении задач на применение поиск в ширину, попробуйте следующее:
Inviational 02 Semifinal Room 2 – Div 1 500 – Escape
(продолжение читайте в третьей части...)
Статью перевел Владислав Семёнов.