54. Алгоритмы поиска решений на графах отношений с легковыделяемыми контурами

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

Пусть B – конечное или бесконечное множество объектов, на котором задано бинарное отношение ³, граф которого содержит контуры.

Известно [11], что элементы, принадлежащие одному контуру в графе бинарного отношения, можно отнести к одному классу эквивалентности, то есть к примерно одинаковым или равноценным объектам. Поэтому каждый контур в графе может быть заменен одной вершиной, соответствующей классу эквивалентных элементов. Полученный граф может отображать некоторое отношение порядка и тогда можно построить диаграмму отношения порядка, и применять алгоритмы поиска решений с использованием диаграмм отношений порядка, рассмотренные в пункте 5.7.1. Поэтому полученный ациклический граф проверяют на свойства транзитивности, асимметричности, антисимметричности, рефлексивности, антирефлексивности и линейности. Если граф удовлетворяет свойствам одного из отношений порядка, то для поиска лучших решений используются вышеуказанные алгоритмы из пункта 5.7.1. Если граф не удовлетворяет свойствам отношений порядка и нет возможности внесением дополнительной информации достроить его до такого графа, тогда дальнейший поиск решения может выполняться в несколько этапов и следующим образом. На каждом из этапов из графа удаляются все вершины, которые соответствуют доминируемым элементам (объектам, альтернативам). Затем вносится дополнительная информация в форме отношения порядка: информация о доминировании и (или) информация о безразличии. Из нового графа опять удаляются доминируемые вершины и т. д. Процесс продолжается до тех пор, пока не останется единственная вершина или заданное число вершин, если ищется не единственное решение, а некоторое множество решений. В тех случаях, когда в качестве единственной вершины остается вершина, соответствующая классу эквивалентности, порожденному контуром графа, для выделения лучшего элемента из класса эквивалентности может применяться алгоритм, использующий понятия силы N-порядка, который описан в следующем подразделе.

< Предыдущая		Следующая >