Трассировка печатных плат




Алгоритм оптимального поиска Нильсона


       В системе 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) 

Поиск прекращается, когда найдена вершина vn, граничащая с источником, и цепочка  v, v1, v2vn от приемника к источнику определяет искомый путь.

Рис. 67

Алгоритм оптимального поиска Нильсона




Содержание  Назад  Вперед