Часть 3: Поиск оптимального пути на графе
Перевод статьи gladius: Section 3: Finding the Best Path through a Graph
Предыдущие части: Часть 1, Часть 2
Поиск наилучшего пути на графе
Очень распространенной задачей на topcoder является поиск кратчайшего пути на графе. Имеется несколько подходов к решению этой задачи, каждый из которых имеет различные практические применения. Мы рассмотрим два метода: использование кучи по методу Дейкстры и метод Флойда Уоршелла (Floyd Warshall).
Дейкстра (метод кучи)
Метод Дейкстры является одним из самых мощных методов из арсенала topcoder. Он, по сути, позволяет вам использовать поиск в ширину, а вместо обычной очереди предлагает воспользоваться очередь с приоритетами и определить функцию сортировки узлов, так чтобы узел с минимальной стоимостью оказался вверху очереди. Это позволяет найти оптимальный путь на графе за время O(m*log (n)), где n — количество вершин, а m — количество ребер на графе.
Примечание:
Если вы еще не встречались с нотацией «О» большое, рекомендуем об этом почитать.
Однако, во-первых, необходимо сделать небольшое введение в сами типы структур данных очереди с приоритетами и кучи. Куча является фундаментальной структурой данных и оказывается чрезвычайно полезной при решении множества задач. При этом нас больше всего интересует свойство полу упорядоченности этой структуры данных. Под полу упорядоченностью подразумевается наличие такого порядка на элементах, помещаемых в структуру, при котором на верхушке очереди остается наименьший (или наибольший) элемент. Куча обладает хорошим свойством — добавление или удаление элемента с вершины занимает время O(log n), где n — количество элементов в куче. Извлечение значения с вершины кучи — это операция O(1), таким образом, куча идеально подходит для решения наших задач.
Основные операции над кучей:
- Add — вставляет элемент в кучу, помещая элемент в правильное упорядоченное местоположение.
- Pop — извлечение верхнего элемента из кучи, верхний элемент будет либо максимальным, либо минимальным элементом, в зависимости от выбранного порядка при реализации.
- Top ‑ возвращает верхний элемент в кучу.
- Empty — проверяет, пуста куча или нет.
Все операции очень похожи на операции над очередью или стеком, поэтому вполне естественно, что мы применяем тот же метод поиска, что и раньше, за исключением применения кучи вместо очереди или стека. Наша основная процедура поиска (запомните это!) будет выглядеть примерно так:
void dijkstra(node start) {
priorityQueue s;
s.add(start);
while (s.empty() == false) {
top = s.top();
s.pop();
mark top as visited;для проверки условия завершения (был ли достигнут целевой узел?) добавим все верхние соседние элементы, которые мы еще не обошли, в стек.
}
}К сожалению, библиотеки не всех языков программирования, используемых в topcoder, поддерживают простую в использовании структуру очереди с приоритетом.
Пользователям C ++ повезло иметь фактическую структуру priority_queue в STL, которая используется следующим образом:
#include
using namespace std;
priority_queue pq;
1. Add - void pq.push(type)
2. Pop - void pq.pop()
3. Top - type pq.top()
4. Empty - bool pq.empty()Однако вы должны быть осторожны, так как C ++ priority_queue в первую очередь возвращает наибольший, а не наименьший элемент. Это стало причиной того, что большинство решений, для которых должно выполняться O(m*log (n)), либо слишком сложны, либо просто не работают.
Чтобы определить порядок в типе, существует несколько разных методов. С практической точки зрения наиболее полезным является следующий:
Define your structure:
struct node {
int cost;
int at;
};А поскольку мы хотим упорядочить по стоимости, определим минимальный оператор для этой структуры следующим образом:
bool operator<(const node &leftNode, const node &rightNode) {
if (leftNode.cost != rightNode.cost) return leftNode.cost < rightNode.cost;
if (leftNode.at != rightNode.at) return leftNode.at < rightNode.at;
return false;
}Несмотря на то, что нам не нужно отсортировать элементы в структуре по «.at», мы по-прежнему элементы с одинаковой стоимостью, но разные по «.at» значения могут быть объединены в одно значение. Повторное включение false нужно для того, чтобы убедиться, что при сравнении двух повторяющихся элементов, для меньшего значения вернется false.
Программистам на Java, к сожалению, придется импровизировать, так как в Java нет реализации структуры данных типа кучи. Мы можем аппроксимировать кучу структурой TreeSet, которая будет выполнять полное упорядочение нашего набора данных. Это менее эффективно, но вполне может послужить нашим целям.
import java.util.*;
TreeSet pq = new TreeSet();1. Add - boolean add(Object o)
2. Pop - boolean remove(Object o)
В этом случае мы можем удалить все, что хотим, но pop должен удалить первый элемент, поэтому мы всегда будем вызывает его как
this: pq.remove(pq.first());
3. Top - Object first()
4. Empty - int size()Для определения порядка мы сделаем нечто похожее на уже использованное нами в C++:
class Node implements Comparable {
public int cost, at; public int CompareTo(Object o) {
Node right = (Node)o;
if (cost < right.cost) return -1;
if (cost > right.cost) return 1;
if (at < right.at) return -1;
if (at > right.at) return 1;
return 0;
}
}
Пользователей C # сталкиваются с аналогичной проблемой, поэтому они также должны использовать аппроксимацию. Самым подходящим для наших целей является класс SortedList, но он не обладает требуемой скоростью обработки (скорость вставки и удаления выполняется за время O(n) вместо O(log n)). К сожалению в C# нет и подходящего встроенного класса для реализации алгоритмов на основе кучи, поскольку HashTable для этих целей тоже не пригодна.
Возвращаясь к нашему алгоритму заметим, что изящность метода состоит в возможности применить его также к графам с взвешенными ребрами, поскольку, как мы писали в предыдущей чести статьи, поиск в глубину оперирует над графами с не взвешенными ребрами. А теперь мы можем уже решать более сложные задачи (и более распространенные в topcoder), чем это было возможно для нас при первом знакомстве с методом поиска в глубину.
Также имеется ряд весьма полезных свойств, например, когда начинается обход графа, сначала выбирается узел с наименьшей стоимостью, поэтому путь к этому узлу является наилучшим (следует оговориться — в том случае, если на графе нет ребер с отрицательными весами). Таким образом, нам нужно посетить каждый узел только один раз и, когда мы попадаем в целевой узел, алгоритм завершается.
В качестве примера воспользуемся задачей KiloManX, взятой с SRM 181, Div 1 1000. Это отличный пример применения метода Дейкстры, заметим попутно, что эта задача изначально относилась к типу задач, решаемых методами динамического программирования. В этой задаче вес ребер изменяется в зависимости от того, какое оружие мы выбрали изначально. Поэтому для конкретного узла, по меньшей мере, мы должны отслеживать, какое оружие было выбрано, и какое количество выстрелов было сделано (это и будет формировать стоимость). В данном случае удобно то, что оружие, которое мы подобрали, соответствует боссам, которых мы победили, поэтому мы можем использовать это как основу для структуры нашего обхода графа. Если мы представим каждое оружие в виде целого числа, нам нужно сохранить максимум 32 768 значений (это 2 в 15-й степени, так как существует максимум 15 видов оружия). Поэтому мы можем сделать наш массив обхода узлов просто как массив из 32,768 булевых величин. Определение порядка узлов в этом случае очень просто, мы сначала хотим обойти узлы с наименьшим количеством выстрелов, поэтому, учитывая эту информацию, мы можем определить нашу основную структуру следующим образом:
boolean visited[32768];class node {
int weapons;
int shots;
// Define a comparator that puts nodes with less shots on top appropriate to your language
};
Теперь мы применим уже знакомую структуру для решения этих задач.
int leastShots(String[] damageChart, int[] bossHealth) {
priorityQueue pq; pq.push(node(0, 0)); while (pq.empty() == false) {
node top = pq.top();
pq.pop(); // Make sure we don't visit the same configuration twice
if (visited[top.weapons]) continue;
visited[top.weapons] = true; // A quick trick to check if we have all the weapons, meaning we defeated all the bosses.
// We use the fact that (2^numWeapons - 1) will have all the numWeapons bits set to 1.
if (top.weapons == (1 << numWeapons) - 1)
return top.shots; for (int i = 0; i < damageChart.length; i++) {
// Check if we've already visited this boss, then don't bother trying him again
if ((top.weapons >> i) & 1) continue; // Now figure out what the best amount of time that we can destroy this boss is, given the weapons we have.
// We initialize this value to the boss's health, as that is our default (with our KiloBuster).
int best = bossHealth[i];
for (int j = 0; j < damageChart.length; j++) {
if (i == j) continue;
if (((top.weapons >> j) & 1) && damageChart[j][i] != '0') {
// We have this weapon, so try using it to defeat this boss
int shotsNeeded = bossHealth[i] / (damageChart[j][i] - '0');
if (bossHealth[i] % (damageChart[j][i] - '0') != 0) shotsNeeded++;
best = min(best, shotsNeeded);
}
} // Add the new node to be searched, showing that we defeated boss i, and we used 'best' shots to defeat him.
pq.add(node(top.weapons | (1 << i), top.shots + best));
}
}
}
На topcoder имеется большое количество подобных задач; вот несколько из них:
SRM 150 — Div 1 1000 — RoboCourier
SRM 194 — Div 1 1000 — IslandFerries
SRM 198 — Div 1 500 — DungeonEscape
TCCC ’04 Round 4–500 — Bombman
Метод Флойда Уоршелла
Метод Флойда Уоршелла ‑ очень мощный метод в том случае, когда граф представлен матрицей смежности. Он работает в за O(n³) время, где n — число вершин графа. Тем не менее, по сравнению с методом Дейкстры, который дает нам только один кратчайший путь к целевому узлу, то метод Флойда Уоршелла позволяет найти все кратчайшие пути от любых узлов источников к любым заданным целевым узлам. Кроме того имеются и другие способы применения метода Флойда Уоршелла, например, его можно использовать для поиска связности графа (так называемое транзитивное замыкание графа).
Однако, прежде всего мы обсудим алгоритм Флойда Уоршелла для поиска всех пар кратчайших путей, который более всего похож на метод Дейкстры. После запуска алгоритма на матрице смежности элемент в узле adj[i][j] представляет длину кратчайшего пути от узла i к узлу j. Псевдокод для алгоритма приведен ниже:
for (k = 1 to n)
for (i = 1 to n)
for (j = 1 to n)
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);Как вы можете видеть, его очень просто запомнить и набрать. Если граф невелик (содержит менее 100 узлов), этот метод может быть использован для быстрого получения результата.
Отличная задача для проверки эффективности этого метода описана в разделе 2 1000 в SRM 184, TeamBuilder.
