Определение порядка решений для графовых моделей бинарных отношений

Бинарные отношения между решениями могут быть представлены в виде графовой модели , дуги на графе соединяют вершины и если бинарное отношение связывает решения и .

Задание. На графе , определяющем бинарные отношения и представленным на Рис.8, идентифицировать сравнимые и несравнимые решения.

Рисунок 8 – Вид графовой модели бинарных отношений

x4

x3

x5

x1

x2

x6

x7

Если граф не содержит контуров, то все его вершины могут быть упорядочены таким образом, что направления всех дуг будут совпадать. В результате вершины графа (решения ) могут быть распределены по ярусам. В вершины яруса входят дуги из вершин ()-го яруса если , из вершин k -го яруса вы ходят дуги в вершины -го яруса в том случае, если . Формирование распределения вершин по ярусам для графовой модели позволяет определить порядок этих вершин (порядок решений) и, соответственно, выделить лучшие решения. Для определения порядка (упорядочивания) решений (вершин графа ) может быть реализован следующий алгоритм. На i- ой итерации алгоритм реализует выделение вершин источников (т.е.вершин. в которые не входят стрелки). Решения, соответствующие этим вершинам, ставятся на i -е место в последовательности решений , после чего выбранные вершины отбрасываются. Обобщенный порядок шагов алгоритма, реализующего определение последовательности решений с точки зрения бинарного отношения предпочтения, следующий:

1) ;

2) выбрать варианты–источники (вершины, решения). Если таковые отсутствуют – переход на шаг 7;

3) выбранные вершины отнести к -ому ярусу;

4) ;

5) выбранные на втором шаге вершины – источники удаляются из графа (в дальнейшем не рассматриваются);

6) переход к шагу 2;

7) конец.

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

Реализацию алгоритма построим на примере графа , представленного на Рис. 9, и соответствующей ему матрицы инциденций.

x4 x3 x5 x1 x2

Рисунок 9 – Вид графовой модели бинарных отношений и соответствующая ей матрица отношений

/ обозначение параметров, используемых при реализации алгоритма

// - количество элементов, добавленных в массив

// - массив решений, упорядоченных с точки зрения убывания предпочтения

// счётчик – текущее количество решений, которые могут быть проанализированы

Счётчик =5; =0; К1=1;

Пока счётчик >=5

// определение исключаемых элементов

Цикл до 5

Сумма =0;

Цикл до 5

Сумма=Сумма + ;

Если Сумма =0 то

= +1;

;

Цикл до

// обнуление элементов в , зависящих только от решений,

// находящихся в массиве .

Цикл до 5

;

// исключение элементов, добавленных в

Цикл до

Цикл до 5

;

K1=K+1; Cчетчик=5-К;

Конец цикла пока;

В результате реализации приведенного фрагмента программы все решения будут упорядочены, при этом лучшее решение будет являться первым в массиве .

Аналогичный подход может быть реализован и при анализе вершин-приемников, т.е вершин, в которые идут стрелки. Тогда самыми первыми в упорядоченном массиве решений будут являться те вершины, из которых не выходят стрелки, а самым лучшим решением в их последовательности будет являться последнее решений.