Поиск на графах
Поиск пути
Во многих задачах поиск решения сводится к поиску кратчайшего расстояния между двумя узлами на некотором графе. Один узел обычно является стартовым (начальное состояние системы), а втрой - целевым. Целевых узлов, в принципе, может быть несколько, однако пока мы будем считать его единственным.
Напомним, что метрикой называют функцию, которая для любых точек x,y,z, в частности, удовлетворяет неравенству треугольника: d(x,z) ≤ d(x,y) + d(y,z). Поэтому будем называть пространство состояний метрическим, если приведенная на картинке ситуация невозможна. К метрическим пространствам относятся графы с прямыми рёбрами, длина которых равна евклидовому расстоянию между узлами. Часто метрическими являются пространства состояний головоломок, в которых каждый шаг (ход, действие) имеет единичную длину. Метрические пространства несколько проще при поиске кратчайшего пути.
Система и искатель
Определим абстрактный интерфейс системы, в которой будем искать кратчайший путь. Её функция getMoves должна возвращать массив соседних состояний и расстояний от состояния s. Введём также функцию value, которая пригодится при организации направленного поиска:
function System() { }// массив соседних состояний к состоянию n в виде [ {s:имя_состояния, d:его_расстояние_от_n} ]System.prototype.getMoves = function(n) { return [ ] }// предпочтительность перемещения в узел n (эвристика расстояния от целевого узла)System.prototype.value = function(n, goal){ return 0 } |
Искателя кратчайшего пути оформим в виде класса Search. Его конструктору передаётся экземпляр системы system и id элемента html страницы в котором выводится информация о процессе поиска. Остальные свойства класса связаны с таймером (ниже) и диагностикой вычислений.
function Search(system, ID){ this.system = system; // система, в которой проводим поиск this.ok = 0; // -1:пути нет, 1:найден, 0:ещё нет this.time = 0; // общее время поиска пути this.timerID = null; // id JavaScript таймера this.period = 100; // период вызова таймера (ms) this.numIters = 1; // число вызовов функции run в таймере this.out = ID?document.getElementById(ID):null;// DOM элемент для вывода this.closedNum = 0; // число обследованных состояний this.openMax = 0; // максимальный размер списка open} |
Организация поиска
Процесс поиска решения разобьём не 3 этапа: подготовка (begin), собственно поиск (run) и построение списка состояний (end ) вдоль найденного пути. Функция run возвращает 1, если путь найден, 0 - если пока нет и -1, если пути не существует. За один вызов она производит одну итерацию поиска, поэтому её следует вызывать в цикле или в таймере (когда необходима визуализация поцесса поиска или устранение блокировки страницы при длительном поиске).
В отличии от деревьев, на графах возможны циклы. Чтобы поиск не зациклился, необходимо запоминать узлы в которых мы уже были. На практике, пространство состояний во многих системах "сгенерить" заранее невозможно и оно строится в процессе решения. Поэтому запоминать узлы (состояния) будем в отдельном списке под названием closed. Узлы для последующего анализа хранятся в списке open. Эти списки инициализируются в функции begin:
Search.prototype.begin = function(start, goal){ this.start = start; // начальный узел this.goal = goal; // целевой узел this.closed = {}; // таблица просмотренных узлов this.closed[start] = { p:null, d:0 }; // в начале уже были this.closedNum = 1; // число обследованных состояний this.open = new List(); // список узлов границы поиска this.open.lt = function(a,b){return a.f < b.f} // сортировка по расстоянию var h = this.system.value(start, goal); // оцениваем расстояние до цели this.open.push( {s:start, f:h, d:0 } ); // стартовый узел с оценками this.openMax = 1; // максимальный размер спсика open if(start === goal) // начало и цель совпадают return this.ok = 1; // путь "найден" this.path = []; // путь пока пуст this.time = 0; // время поиска this.timerID = setInterval(this.timer.bind(this), this.period); return this.ok = 0; // состояние goal ещё не найдено} |
Search.prototype.timer = function(){ if(this.ok){ // на предыдущем вызове поиск окончен clearInterval(this.timerID); // убиваем таймер this.timerID = null; // и его id-шник return; } var num = this.numIters; // число циклов поиска var start = new Date(); // начало времени этой итерации поиска while(num-- > 0 && this.run() === 0) ; this.time += (new Date() - start); // общее время поиска пути if(this.ok) // поиск окончен this.end(); // строим массив пути if(this.out) // выводим информацию о процессе поиска this.out.innerHTML = this.time + 'ms> ' + 'closed:'+this.closedNum +', open:' + this.open.length + ' max:'+ this.openMax + (this.path.length? (' path:'+(this.path.length-1)):"");} |
Поиск в ширину
Рассмотрим первый, простейший способ поиска пути - поиск в ширину на графе с рёбрами одинаковой длины (такое пространство автоматически метрическое). Как и в случае деревьев, ключевым является взятие следующего для анализа узла из начала очереди open, и помещение соседних к нему узлов в конец очереди. Тем самым обеспечивается первоочередной анализ узлов из open, которые ближе всего к стартовому узлу start. Равенство длин рёбер не требует дополнительного упорядочивания очереди.
Search.prototype.run = function(){ if(!this.open.length) return -1; // поиск закончился неудачей var n = this.open.shift(); // берём узел из начала списка var go = this.system.getMoves(n.s); // получаем всех соседей этого состояния var d = n.d + 1; // расстояние к ним считаем одинаковым if(this.maxDist && this.maxDist < d) return -1; for(var i=go.length; i--; ){ // бежим по соседям var si = go[i].s; // имя состояния i-го соседа if(this.closed[si] !== undefined ) // это состояние уже было continue; // пропускаем его this.open.push( {s:si, d:d } ); // добавляем в конец списка имя состояния this.closed[si] = {p:n.s, d:d}; // помним, что попали из n и расстояние this.closedNum++; if(si == this.goal) // дошли до целевого угла return 1; // поиск окончен } return 0; // продолжаем поиск} |
Ниже приведен пример поиска в ширину на 6-угольном регулярном графе и на графе с более запутанной топологией. Начальная и конечная точка между которым необходимо найти путь, помечены красным, те узлы, в которых алгоритм уже побывал - синим и зелёным - узлы, находящиеся в списке open. Скорость поиска можно замедлить, задав время таймера (под картинкой) и нажав на надпись "restart".
| restart ms | restart ms |
Направленный поиск
Предположим, что мы можем вычислять расстояние h(n) = value(n, goal) от данного узла n к целевому узлу goal. Тогда при выборе очередного узла, двигаясь к цели, очевидно, небходимо выбирать узел с минимальным значением функции h(n). Если бы всегда, функция, подобная h(n), существовала, поиск пути был бы тривиальной задачей. К сожалению, это не так и на практике h(n) приходится угадывать, подбирая наиболее "правильную" функцию. Поэтому её называют эвристикой (heuristics). На пространственном графе её можно задать как евклидово расстояние между узлами:
System.prototype.value = function(n, goal){ var n1 = this.graph.nodes[n]; var n2 = this.graph.nodes[goal]; return Math.sqrt( (n1.x-n2.x)*(n1.x-n2.x) + (n1.y-n2.y)*(n1.y-n2.y) );} |
Search.prototype.run = function(){ if(!this.open.length) return -1; // поиск закончился неудачей var n = this.open.shift(); // берём узел из начала списка var go = this.system.getMoves(n.s); // получаем всех соседей этого состояния for(var i=go.length; i--; ){ // бежим по соседям var ni = go[i], si = ni.s; // узел и имя состояния i-го соседа if(this.closed[si] !== undefined ) // это состояние уже было continue; // пропускаем его var d = n.d + ni.d; // расстояние к началу var h = this.system.value(si,this.goal); // оценка расстояния к цели var f = d + h; // оценка длины пути через ni this.open.add( {s:si, d:d, f:f } ); // вставляем, сортируя по f this.closed[si] = {p:n.s, d:d}; // помним, что попали из n this.closedNum++; if(si == this.goal) // дошли до целевого угла return 1; // поиск окончен } return 0; // продолжаем поиск} |
Ниже приведен направленый поиск на двух графах:
| restart ms | restart ms |
Свойства эвристик
Эвристика h = value(n, goal) может давать как заниженное значение расстояния к целевому узлу, так и завышенное. В первом случае она оказывается неэффективной и при h = 0 сводится к поиску в ширину. Если эвристика завышает расстояние, то найденный путь может оказаться не кратчайшим. Разберём эти случаи на примерах.
| restart ms | restart ms | restart ms, w: |
В первом примере для эвристики используется манхэттенское расстояние Math.abs(n1.x-n2.x) + Math.abs(n1.y-n2.y). На прямоугольной сетке равных рёбер и без дырок, оно является истинным расстоянием к целевому узлу, поэтому поиск пути происходит самым оптимальным образом. Ни каких лишних (кроме непосредственно прилегающих к пути) узлов не раскрывается.
Во втором случае value возвращает евклидово расстояние sqrt( (n1.x-n2.x)*(n1.x-n2.x) + (n1.y-n2.y)*(n1.y-n2.y) ). На прямоугольной сетке при диагональном пути евклидлидово расстояние на 30% меньше, чем "истинное" манхэттенское. Поэтому поиск в ширину начинает преобладать над направленным поиском и алгоритму приходится раскрыть существенно больше узлов. Путь выглядит более "диагональным", чем на первой картинке (Евклид!), и его длина в обоих случаях одинакова (равна 16).
В третьем примере функция value возвращает манхэттенское расстояние, умноженное на w = 3 (под картинкой этот коэффициент можно изменить). Так как расстояние к цели завышено, алгоритм устремляется к ней и не находит кратчайшего пути. Если положить w = 1, путь сократится с 18 рёбер до 12.
Если эвристика не переоценивает (не завышает) расстояние к целевому узлу, то она называется допустимой. Допустимые эвристики гарантируют нахождение кратчайшего пути. Из двух допустимых эвристик более информированной (лучшей) будет эвристика, дающая большее значение: h(n) = max( h1(n), h2(n) ).
Если h(a) ≤ d(a, b) + h(b), где d(a, b) - расстояние между соседними узлами, то эвристика называется преемственной (consistent). Для последовательных эвристик, по мере удаления от старта, монотонно меняется сумма f(n) = d(n) + h(n), где d(n) = d(start, n) точное расстояние от стартового узла. Последовательная эвристика гарантировано допустимая, но не каждая допустимая является преемственной.
Встречный поиск
Пусть существуют ссылки на узлы из которых можно попасть в данный (в классе Graph они (массивы on) строятся функцией createOn). Тогда можно организовать поиск одновременно от стартового узла start к целевому goal и от целевого к стартовому. Например от goal запускаем поиск в ширину (или с некоторой гарантированно допустимой эвристикой), а от start направленный поиск. Как только он (направленный) достигнет одного из узлов встречного списка close - можно строить путь. Возможны и другие варианты.
Поиск в ширину :Встречный поиск является частным случаем использования базы данных с шаблонами (pattern databases) заранее просчитанных кратчайших расстояний к целевому узлу. Например в головоломках, таких как 15-шки целевое состояние всегда одно, а начальные - каждый раз различны. Поэтому целесообразно сразу вычислить расстояния от некоторых ближайших состояний к целевому. Для этого используется обратный поиск в ширину: от целевого узла строятся все его соседние узлы (в 15-шках расстояния к ним равны 1), потом следующие соседи и т.д. на некоторую глубину. При направленном поиске очередной узел проверяется на наличие в базе шаблонов и, если он там есть, поиск оканчивается (от шаблонного узла всегда можно построить кратчайший путь к целевому).
Возможны и более хитрые варианты шаблонов, когда оценивается число ходов, которые необходимо сделать, чтобы постанвить на свои места группу конкретных костяшек (например под номерами 1,2,3), игнорируя при этом номера, написанные на остальных костяшках (это и есть шаблон). Такие, предварительно посчитанные шаблоны используются в функции вычисления эвристики.
A* алгоритм
A* алгоритм является алгоритмом направленного поиска, в котором не предполагается, что пространство состояний может быть не метрическим. Это накладывает определённое усложнение, связанное с возможной переоценкой расстояния от стартового узла. В алгоритме, как и ранее, из начала отсортированной очереди open извлекается наиболее перспективный узел n и строятся все его соседи ni=go[i]. В очереди closed храним не только как мы попали в этот узел, но и расстояние к нему. Если узел ni оказался в closed и расстояние к нему было больше, чем для текущего ni, мы меняем в closed его расстояние и предшественником ставим n. Кроме этого, убираем его из списка open и вставляем опять с новым расстоянием (параметры f и d).
var si = go[i].s;var was = this.closed[si];if(was !== undefined ){ // это состояние уже было if(was.d > d){ was.s = n.s; was.d = d; old = open.del(si); open.add( {s:si, d:d, f:f } ); } continue;} |
IDA* алгоритм
Алгоритм A* с итеративным углублением (iterative deepening A*) аналогичен соответствующему алгоритму поиска на дереве.