Парадигма развития науки. Методологическое обеспечение (стр. 96 )

По отношению к этому упорядочению максимальным в множестве T является элемент такой, что

Рассмотрим еще одну задачу упорядочения, иллюстрируемую следующим примером.

Требуется решить, кто из детей: старший сын x1, младший сын x2 или дочь x3больше всего похож на отца z. Заданы "результаты измерений": x1 и x2 взятые отдельно, похожи на отца со степенями 0,8 и 0,5 соответственно; x2 и x3, взятые отдельно, похожи на отца со степенями 0,4 и 0,7; наконец, x1 и x3, взятые отдельно, похожи на отца со степенями 0,5 и 0,3.

Таким образом, в этой задаче, в отличие от предыдущей, имеется стандартный элемент (шаблон) для упорядочиваемого множества T, т. е. элемент, обладающий свойствами, общими для всех элементов этого множества. Иначе говоря, если — нечеткое отношение в (например, отношение сходства), то

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

Максимальным в смысле этого упорядочения является элемент такой, что

Для задачи о сходстве отца и детей значения этой функции таковы:

Отсюда вытекает, что наиболее похож на отца старший сын, затем следуют дочь и младший сын.

14.5. Разложение на максимальные подотношения подобия

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

Сначала рассмотрим этот алгоритм для более общего случая, а затем вернеся к частому случаю, который нас особенно интересует.

Алгоритм Мальгранжа. Получение максимальных полных подматриц или главных подматриц.

Описание этого алгоритма требует введения некоторых предварительных определений.

В матрице с бинарными элементами (0 или 1), т. е. в булевой матрице, задаюшей граф (а точнее, граф Бержа), полной подматрицей называется подматрица, все элементы которой равны 1.

Основной подматрицей (говорят также «максимальной полной

подматрицей») называется полная подматрица, не содержащая никакой другой полной подматрицы. Например, на рис. 1 представлены семь основных подматриц матрицы [М].

Рис. 1.

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

Пусть L — множество строк и J — множество столбцов булевой матрицы. Каждая полная подматрица определяется упорядоченной парой обычных подмножеств (Ip, Jq), где IрI, Jq J. Можно показать, что операции и , которые двум полным подматрицам булевой матрицы [М], скажем,

[М1], определенной посредством (І1, J1),

[М2], определенной посредством (І2, J2),

ставят в соответствие две подматрицы:

[М1] [М2]= [М′], определенной упорядоченной парой

(І1 I2, J1 J2 ),

[М1] [М2]= [М′′], определенной упорядоченной парой

(І1 I2, J1 J2 ),

есть внутренние операции на множестве М полных подматриц матрицы [М].

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

С= {[ М1], [ М2], .... [Мр]},

позволяет получить основные подматрицы матрицы [М] за конечное число итераций.

Первая итерация. Вычеркиваем все матрицы [Mk], которые содержатся в других подматрицах покрытия С.

Вторая итерация. Добавляем к С подматрицы, которые получены применениям определенных выше операций и ко всем парам матриц [Mk] и [Mt] , которые входят в покрытие (кроме полных подматриц, которые уже содержатся в подматрицах покрытия С, что исключает бесконечный процесс).

Пример. Найдем основные подматрицы булевой матрицы на рис. 1.

Этап 1. Выберем покрытие

Этап 2 (вторая итерация). Подсчитаем объединения и пересечения:

I1 I2= {А, В}, J1 J2 = ,

I1I3= {А, С}, J1 J3 = {b, d, e},

откуда получим новую подматрицу

I1 I4= {A, D}, J1 J4 = {b, f}

и новую матрицу

I2 I3= {В, С}, J2 J3 = ,

I2 I4= {В, D}, J2 J4= {с},

что дает новую матрицу

I3 I4 = {С, D}, J3 J4 = {b},

что дает новую матрицу

Так как все пересечения IiIj, i, j пустые, то бесполезно подсчитывать Ji Jj.

Этап 3 (первая итерация). Выпишем новое покрытие

С′ = { [M1], [M2], [M4], [М5], [М6], [М7], [М8]}.

Матрица [М3] содержится в [М5] и потому не включена в покрытие С.

Этап 4 (вторая итерация).

С дидактической целью приводим все детали расчетов, не исключая вычислений даже тех матриц, которые уже были получены или оказываются пустыми:

I1 I5= {А, С}, J1 J5 = {b, d, e}, дает [М5],

I1 I6 = {A, D}, J1 J6 = {b, f}, дает [М6],

I1 I7 = {А, B, D}, J1 J7 = ,