Алгоритм оптимального поиска Нильсона
В системе FreeStyle Router для поиска кратчайшего расстояния между выводами компонентов при прокладке трасс используется алгоритм Нильсона. Как было доказано самим автором это наиболее быстрый алгоритм среди ныне существующих [12]. Для того чтобы понять его суть, необходимо ввести некоторые обозначения:
g(v) – стоимость пути от источника до вершины v;
h(v) – нижняя оценка стоимости пути от вершины v до приемника (в качестве h(v) для данной задачи примем расстояние от вершины v до приемника);
f(v) = g(v) + h(v) - нижняя оценка стоимости пути от источника до приемника, проходящего через вершину v.
Последовательность операций при решении задачи поиска с помощью алгоритма Нильсона следующая (рис. 67):
1) Среди вершин графа, граничащих с приемником, найти вершину v, имеющую наименьшую оценку f(v);
2) Если вершина v не граничит с источником определить среди вершин, достижимых из v, вершину v1 с наименьшей оценкой f1(v) (нижняя оценка стоимости пути от источника до приемника, проходящего через вершину v1 и соседнюю с ней вершину v).
3) Если вершина v граничит с источником, она является единственной вершиной графа между источником и приемником
4)
Рис. 67
Алгоритм оптимального поиска Нильсона
