Вступление
До сих пор мы знали, как реализовать поиск по глубине и ширине графика . Эти два подхода имеют решающее значение для понимания алгоритмов обхода графа. Однако они просто объясняют, как мы можем пройти в ширину или глубину, и иногда этого недостаточно для эффективного решения обхода графа.
До сих пор в примерах у нас был неориентированный невзвешенный граф, и мы использовали матрицы смежности для представления графов. При использовании матрицы смежности мы хранить 1 в A [I] [J] , если есть ребро между вершиной я и вершиной у. В противном случае мы ставим 0 . Однако значение 1 дает нам только информацию о том, что у нас есть грань между двумя вершинами, что не всегда достаточно при разработке графиков.
Действительно, графики могут быть взвешенными. Иногда путь между двумя вершинами может иметь значение. Думая о дорожной карте, мы знаем, что расстояния между городами представлены в милях или километрах. Таким образом, часто представляя дорожную карту в виде графика, мы не ставим только 1 между городом A и городом B, чтобы сказать, что между ними есть путь, но также мы помещаем некоторую значимую информацию — скажем, расстояние в милях от A и Б.
Обратите внимание, что это значение может быть расстоянием в милях, но может быть и другим, например, временем в часах, которое мы должны пройти между этими двумя городами. В общем случае это значение является функцией от A и B. Поэтому, если мы сохраняем расстояние между A и B, мы можем сказать, что эта функция F (A, B) = X или расстояние (A, B) = X миль.
Конечно, в этом конкретном примере F (A, B) = F (B, A), но это не всегда верно на практике. Мы можем иметь ориентированный граф, где F (A, B)! = F (B, A).
Здесь я говорю о расстоянии между двумя городами, и это край, который приносит некоторую дополнительную информацию. Однако иногда мы должны хранить значение вершин. Допустим, я играю в игру (например, в шахматы), и каждый ход приносит мне дополнительное преимущество. Таким образом, каждый ход (вершина) может быть оценен с определенным значением. Таким образом, иногда мы имеем не функцию и ребро, как F (A, B), но функцию вершин, как F (A) и F (B).
В поиске по ширине и поиску по глубине мы просто выбираем вершину и последовательно проходим все ее наследники, которые еще не были посещены.
Прохождение невзвешенного графика
Чтобы просмотреть невзвешенный граф с использованием DFS, мы последовательно выбрали каждого преемника узла i!
В частности, в DFS мы начали слева направо в массиве выше. Таким образом, первый узел, который должен быть исследован — это вершина «1».
0: [0, 1, 0, 0, 1, 1]
Однако иногда, как я уже говорил выше, у нас есть взвешенные графики, поэтому возникает вопрос — есть ли какие-либо проблемы, связанные со скоростью алгоритма, если мы последовательно проходим все преемники. В общем, ответ да, поэтому мы должны немного изменить наш код, чтобы продолжить не с первого, а с наиболее подходящим преемником. Под лучшим соответствием мы подразумеваем, что преемник должен соответствовать некоторым критериям, таким как — минимальное или максимальное значение.
обзор
В следующем примере мы видим, что некоторые из преемников вершины 0 очень далеки от нее, а другие ближе. Таким образом, 4 имеет значение 5, в то время как значение узла 1 равно 2, а 5 равно 1.
Прохождение невзвешенного графика
Взвешенный граф приносит нам больше информации о преемниках данной вершины. Таким образом, мы должны тщательно выбирать, какой из них получить первым в нашем исследовании пути!
0: [0, 2, 0, 0, 5, 1]
В этом случае, если мы ищем кратчайший путь между 1 и 3, хотя 1 и 4 являются первыми двумя преемниками в матрице смежности «стартовой» вершины, мы не выбираем их, так как есть лучшее решение — идущий через узел 5.
В поиске лучших сначала мы продолжаем путь к цели через наиболее подходящего преемника!
Проблемы
Вопрос в том, уверены ли мы, что, выбрав узел 5, мы найдем лучший путь? Даже больше! Есть ли путь через узел 5? Как мы видим на изображении ниже, возможны оба случая.
Somtimes Best-First Search не находит «лучший» (самый короткий / самый длинный / самый дешевый) путь к цели!
Практически поиск по первому совпадению идентичен поиску по глубине, с основным отличием в том, что мы выбираем наиболее подходящего преемника вместо выбора первого подходящего преемника. Таким образом, мы уверены, что мы проходим все преемники, но в определенном порядке, отличном от DFS. Таким образом, мы знаем, что если есть путь, мы его найдем.
Однако даже если мы найдем путь между A и B, мы не можем быть уверены, что лучшего пути нет. Мы только знаем, что этот путь пока лучший.
Другой вопрос — как мы можем эффективно найти лучшего подходящего преемника. Хорошо, если мы ищем минимальное или максимальное значение, одним из возможных решений является сортировка массива наследников.
Разница между глубиной первой и лучшей первой заключается в том, что мы меняем порядок выбора следующего преемника!
0: [0 => 0, 1 => 2, 2 => 0, 3 => 0, 4 => 5, 5 => 1] // sorted by value 0: [5 => 1, 1 => 2, 4 => 5, 0 => 0, 2 => 0, 3 => 1]
Другим хорошим подходом будет использование приоритетных очередей или куч.
Таким образом, на каждом шаге мы получим лучшего подходящего преемника.
Код
В целом, поиск по принципу «лучший вначале» основан на поиске по глубине, поэтому его реализация не сложнее! Следующий фрагмент кода PHP показывает очень маленькую разницу между этими двумя алгоритмами.
class Graph
{
protected $_len = 0;
protected $_g = array();
protected $_visited = array();
public function __construct()
{
$this->_g = array(
array(0, 2, 0, 0, 5, 1),
array(1, 0, 3, 0, 0, 0),
array(0, 2, 0, 8, 0, 0),
array(0, 0, 3, 0, 5, 0),
array(1, 0, 0, 8, 0, 1),
array(1, 0, 0, 0, 5, 0),
);
$this->_len = count($this->_g);
$this->_initVisited();
}
protected function _initVisited()
{
for ($i = 0; $i < $this->_len; $i++) {
$this->_visited[$i] = 0;
}
}
public function bestFirst($vertex)
{
$this->_visited[$vertex] = 1;
echo $vertex . "\n";
asort($this->_g[$vertex]);
foreach ($this->_g[$vertex] as $key => $v) {
if ($v > 0 && !$this->_visited[$key]) {
$this->bestFirst($key);
}
}
}
}
$g = new Graph();
// 2 1 0 5 4 3
$g->bestFirst(2);
заявка
Поиск по принципу «лучший первый» — это типичный жадный алгоритм. В его принципах лежит главный жадный подход к выбору наилучшего из возможных решений. Важно отметить, что поиск в глубину и поиск в ширину — это базовая схема обхода графа, но они также могут быть широко расширены для решения более сложных задач.