Алгоритм Уоршалла

Кратчайшие пути между всеми парами вершин

Методологические и теоретические основы экспертизы.

Основные задачи, принципы и методы проведения экспертизы закреплены в основных положениях ЕГСД (единая государственная система делопроизводства). Ценность документов устанавливается в соответствии с принципами историзма, системности и целостности.

Принцип историзма означает, что оценивать документы следует с точки зрения их роли, места, значения в историческом процессе развития общества.

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

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

Система делится на три группы комплексно применяемых критерий:

• Происхождение – к критериям происхождения относятся:

• роль и место организации в системе государственного управления или конкретной отрасли, значимость выполняемых ею функций;

• значение физического лица в жизни общества;

• время и место образования документа.

• Содержание – к критериям содержания относятся:

• значимость события (явления), отраженного в документе;

• значение имеющейся в документе информации;

• повторение информации документа в других документах;

• вид документа;

• подлинность документа.

• Внешние особенности документов – к критериям внешних особенностей документов относятся:

• форма фиксирования и передачи содержания, удостоверения, оформление документа;

• физическое состояние документа.

Экспертиза ценности электронных документов проводится экспертной комиссией во взаимосвязи с документацией организации на традиционных носителях. Но помимо общих критерий должны учитываться некоторые специальные:

• Стоимость возможного перевода электронных документов в другой формат.

• Наличие сопроводительной документации и соответствующего электронного оборудования.

Пусть A - матрица смежностей ориентированного графа.

Метод определения матрицы достижимости P вначале путем вычисления A1, A2,..., An, а затем Bn является очень громоздким.

Более эффективный метод - использование в вычислениях булевские матричные операции.

Матрица смежностей, так же как и матрица достижимости, является булевской матрицей. Заметим, что AÙA^(r-1)=A^(r) для любого r=2,3,...

Здесь A^(r) является булевской матрицей, и элемент на пересечении i-й строки и j-го столбца A^(r) = 1 в том случае, когда существует по крайней мере один путь длины r из v_i в v_j, при любом целом положительном r.

Из этих рассуждений понятно, что матрица достижимости P задается выражением

Например, если

Описанный метод получения матрицы достижимости ориентированного графа называется алгоритмом Уоршалла [Warshall,1962], этот алгоритм обрабатывает матрицу по столбцам.

Уоррен [Свами,Тхуласираман,1984,с.320] предложил двухпроходной "строко-ориентированный" алгоритм, в котором при обработке i-ой вершины в первом проходе обрабатываются только ребра, связанные с вершинами, меньшими i, а во втором проходе - только ребра, связанные с вершинами, большими i.

Другими словами, алгоритм преобразует матрицу смежности графа G в матрицу достижимости, обрабатывая в первом проходе только элементы матрицы, расположенные ниже ее главной диагонали, а во втором проходе - только элементы матрицы, расположенные выше ее главной диагонали.

Таким образом, при каждом проходе обрабатывается не более n(n-1)/2 ребер.

Дата добавления: 2014-01-20