Алгоритм поиска неисправностей с использованием оптимизации на графах

Если информационная система может быть представлена в виде графа, то для решения задачи технической диагностики могут использоваться алгоритмы поиска кратчайшего пути, соединяющего две выделенные вершины исходного графа. При этом длина пути определяется как сумма длин отдельных дуг, составляющих этот путь, а длины дуг можно интерпретировать как некоторые затраты или весовые коэффициенты.

Итерационный алгоритм, представленный Дейкстрой, считается одним из наиболее эффективных алгоритмов решения такой задачи. В этом алгоритме при поиске кратчайшего пути из вершины S в вершину E каждой вершине в ходе выполнения алгоритма присваивается число l (x), равное длине кратчайшего пути из S в x включающего только окрашенные вершины.

1. Первый шаг: положим для всех x, не связанных с S, а также y=S (y – последняя из окрашенных вершин), а также определим значение l для вершин, связанных с вершиной S.

2. Итерационный шаг: для каждой неокрашенной вершины пересчитать величину , где - длина дуги. Если для всех неокрашенных вершин x, закончить процедуру алгоритма, т.к.в исходном графе отсутствуют пути из вершины S в неокрашенные вершины. В противном случае окрасить ту из вершин x, для которой величина является наименьшей. Кроме того окрашивается дуга, ведущая в выбранную на данном шаге вершину x. Положить y=x, т.е окрасить вершину х.

3. Заключительный шаг: если y=E, то закончить процедуру, т.к. кратчайший путь в вершину E найден.Это единственный путь в E, составлены из окрашенных дуг. Полученное решение обладает следующими свойствами. Окрашенные дуги образуют в исходном графе ориентированное дерево с корнем в вершине S. Это дерево называется деревом кратчайших путей. Единственный путь до любой из вершин x, принадлежащих дереву кратчайших путей, является кратчайшим путем между указанными вершинами. Если кратчайшему пути из вершины S в вершину в дереве кратчайших путей принадлежит вершина , то часть этого пути, заключенная между и , является кратчайшим путем между этими вершинами.

Дата добавления: 2015-04-30