Системы представителей множеств

⇐ ПредыдущаяСтр 14 из 16Следующая ⇒

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

Рассмотрим две из наиболее простых задач этого типа - нахождение систем различных представителей и систем общих представителей (С.Р.П., С.О.П.). Типичным примером первой задачи является следующая. Даны пять множеств S ₁= {1,2,3}, S₂= { 1,2,4 }, S ₃ ={1,2,5},S ₄ ={3,4,5,6}, S ₅ ={3,4,5,6]. Требуется выбрать такие различные числа x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , что .Одним из способов выбора является x ₁ =1, x ₂ =2, x ₃ =5, x ₄ =3, x ₅ =4. Но если взять множества Т₁={1, 2},T₂={1,2}, T ₃= {1,2 },T ₄={3,4,5,6}, T ₅={3,4,5,6}, то такой выбор оказывается невозможным, Возникает вопрос: при каких условиях подмножества Si, i=1, 2,…,n, множества S обладают различными представителями x_i ; i =1;…, n т.е. и если. . Заметим, что ^;не требуется, чтобы Si и Sj с были различными подмножествами множества S. Ответ на этот вопрос дает теорема Ф.Холла [23,24]. Пусть, имеются n-множество S и его булеан В (S). Пусть - некоторая m-выборка из B(S) и некоторая m-выборка из S.

Подмножества S ₁ , S ₂ ,..., S_m имеют С.Р.П, тогда и только тогда,, когда объединение любых k из этих множеств содержит не менее k элементов. Необходимость очевидна. Достаточность этого утверждения дается следующей т е о р е м о й, задающей одновременно и нижнюю грань для числа различных представителей.

Пусть семейство M={S ₁ , S ₂,…; S_m} удовлетворяет необходимому условию существования С.Р.П., и пусть каждое из множеств S ₁ , S ₂ ,..., S_m состоит не менее чем из t элементов. Тогда: а) если , то М имеет не меньше, чем t ! С.Р.П.; б) если t > m, то М имеет не менее, чем t !/( t - m )! С.Р.П. Доказательство этого утверждения методом индукции дано в [23], и мы не будем на нем останавливаться, а остановимся на практической реализации решения задачи выбора С.Р.П., так как практически очень трудно проверить, выполняются ли в данном конкретном случав условия теоремы Ф.Холла, которую можно отнести к теоремам существования. Теоремы существования чаще всего появляются там, где бывает трудно или невозможно найти алгоритм, приводящий к нахождению решения. Алгоритм, который позволяет подобрать С.Р.П. для конечного числа множеств или показать, что такой системы не существует для данного набора множеств, дал М.Холл [23, 24]

Рассмотрим n множеств S ₁ , S ₂ ,…, S_n. Найдем для них С.Р.П. или покажем, что ее найти нельзя. Произвольно выберем элемент первого множества качестве его представителя. Поочередно будем выбирать представителей других множеств , заботясь только о том, чтобы все они были различны. Если мы доведем этот процесс до включительно, то получим искомую С.Р.П. Может случиться, чтo на r -м шаге мы дойдем до некоторога t-множества S_r все элементы которого b ₁ , b ₂ ,…, b_t уже были представителями других множеств. Это, однако, еще не означает, что С.Р.П. не существует. Будем брать поочередно все те множества, представителями которых являются элементы bi ( i =1,2,…) и удалять из них все элементы последовательности b₁,b₂,..,b_t а оставшиеся приписывать в конец этой последовательности. Так будем поступать до тех пор, пока не случится одно из двух: либо 1) мы достигнем элемента b_i, который не может служить представителем, 2) последовательность исчерпывается элементами b ₁ , b ₂ ,…, b_s как представителями множеств, В случае 2) С.Р.П. не существует. В самом деле, элементы b ₁ , b ₂ ,…, b_s являются представителями S множеств, и по построению каждый, элемент этих S множеств содержится. в данной последовательность. Но тогда эти S множеств ,а также множество S_r образуют S+1 множеств, которое содержат только S различных элементов, что противоречит условию теорем существует С.Р.П., Ф.Холла.

В случае 1) на некотором этапе мы находим элемент ,не являющийся до сих пор представителем. Это означает, что представителем S_j ₁ уже был выбран другой, элемент , Если i ₂ > t, то значит представителем которого является b_i ₃ ( i _3< i ₂ ).Таким образом, возникает последовательность индексы которой убывают , причем в этой последовательности каждый ее член входит в множество, представителем которого является следующий член. Заменяем представителей, выбирая элементы: bi ₁ для S_j ₁ , b_i ₁ для Sj 2,… b_im _-1, для S_jm _-1 .Элемент b_im в результате этой замены освобождается для выбора в качестве представителя S_r,. Итак, S ₁ ,..., S_r имеют различных представителей, и мы можем следовать тем же путем, имея в виду либо возможность дойти до S_n и получить полную С.Р.П., либо встретить случай 2) и установить не существование С.Р.П. Заключение о числе С.Р.П. получается из приведенного алгоритма как следствие.

Рассмотрим решение задачи нахождения общих представителей (С.О.П.). Пусть даны два различных разбиения одного и того же множества S на К непустых составляющих:

Если существует подмножество 0 множества S состоящее из k элементов, и такое, что его пересечение с любым из составляющих не пусто (O ∩ A_i ≠Ǿ, O ∩ B_i ≠Ǿ, i =1,2,…, k) то оно называется системой общих представителей (С.О.П.) данных разбиений. При этом каждое из пересечений оказывается состоящим только из одного элемента. Попарно взятые множества первого и второго разбиений, подобранные, если надо, соответстзующим образом, имеют один и только один общий элемент который и является их общим представителем обязательно, чтобы соблюдалось требование существования только одного общего элемента. Можно ставить условия: существование заданного числа общих элементов, заданного множества их. Критерий существования или не существования С.О.П. близок к критерию, применяемому к С.Р.П. Два разбиения множеств тогда и только тогда имеют С.О.П., когда объединение любых m из множеств A_i пересекаются не менее чем с m из множеств B_j, где m = I , ... k .

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

Дата добавления: 2018-11-24; просмотров: 908; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 7 8 9 10 11 12 131415 16 Следующая ⇒

Мы поможем в написании ваших работ!