О древовидности оптимальных ИГ включающего поиска

Результаты предыдущей главы показывают, что древовидность оптимальных информационных графов помимо удобств практической реализации позволяет получать нижние оценки сложности, отличные от мощностной нижней оценки. Поэтому представляется интересным поиск таких типов задач поиска, которые имели бы древовидные оптимальные информационные графы. Факт, что граф, разрешающий некоторую задачу включающего поиска, представляет собой многополюсник, реализующий некоторую систему элементарных монотонных конъюнкций, позволял надеяться на древовидность оптимальных ИГ для задач включающего поиска. Но эта гипотеза не подтвердилась, что и доказано в данном разделе. Но несмотря на это для задач включающего поиска удается получить нижние оценки сложности ИГ, отличные от мощностной нижней оценки, и эти оценки приводятся в последующих разделах. В данном разделе мы будем рассматривать информационные графы над двумя базовыми множествами: базовым множеством Т = (Х^п, 0), которое будем называть базовым множеством переменных, и базовым множеством Тг = (АС", 0), которое будем называть базовым множеством элементарных монотонных конъюнкций. Для каждого из этих базовых множеств доказано существование таких задач включающего поиска, для которых удалось найти такие недревовидные ПИГ, которые по сложности проще любого древовидного ПИГ. Этот же вопрос для базового множества (М^п, 0) монотонных булевых функций остается открытым из-за громоздкости вычислений, которые надо произвести при доказательстве. Результаты данного раздела опубликованы в [36].

Докажем два полезных свойства.

Свойство 6. Пусть U произвольный ПИГ над базовым множеством (Л4″, 0), (АС^П, 0) или (Х^п, 0), разрешающий некоторую задачу типа Sbool• Тогда любое (существенное) ребро ПИГ U имеет сложность, не меньшую, чем 2″" .

Доказательство. Поскольку любая функция из множеств Х^п, АС" и М^п принимает значение 1 на запросе вида (1,1,…, 1), то запрос (1,1,…, 1) пройдет в любую вершину графа U Следовательно, сложность любого ребра графа U не меньше чем 2″". Что и требовалось доказать.

Свойство 7. Пусть U произвольный ПИГ над базовым множеством (М^п, 0), (АС", 0) или (Х^п, 0), разрешающий некоторую задачу I типа Sbool и имеющий вид дерева, в некоторой главной цепи записи которого встречаются два разных ребра, которым приписан один и тот же символ. Тогда граф U не может быть оптимальным для задачи I.

Доказательство. Согласно условию граф U содержит фрагмент, изображенный на рис. 3.1, т. е. U содержит главный путь некоторой записи, в котором встречаются два ребра, которым приписан один и тот же символ /.

Обозначим первое ребро, которому приписан символ / (нижнее на рис. 3.1), через С, а второе ребро, которому приписан символ / (верхнее на рис. 3.1), — через С2;

Рис. 3.1. Фрагмент графа U.

Так как граф U древовидный, то к каждой вершине ведет только одно ребро (с учетом того, что в графе нет несущественных ребер). Поэтому все цепи, проходящие через ребро С2, проходят и через ребро ci. Следовательно, выбрасывание ребра С2 не изменит функций проводимости цепей, которые проходили через СгОтсюда следует, что если заменить фрагмент, изображенный на рис. 3.1, на фрагмент, изображенный на рис. 3.2, то функционирование графа U не изменится, а сложность согласно свойству 6 уменьшится. Это означает, что граф U не мог быть оптимальным. Что и требовалось доказать.

Рис. 3.2. Заменяющий фрагмент.

Базовое множество переменных. В этом подпункте мы будем рассматривать графы над базовым множеством (Х^п, 0) и покажем существование такой ЗИП типа Sbooh которая имеет недревовидный оптимальный ПИГ.

Теорема 22. Если п > 9 и базовое множество есть множество переменных (Xⁿ, 0), то существует такая ЗИП типа Sbooi, для которой любой оптилюяьиый ПИГ над (Х^п, 0) не является деревом.

Доказательство. Договоримся обозначать запись у € В^п через ее характеристическую функцию, т. е. представлять ее в виде конъюнкции переменных, номера которых совпадают с номерами разрядов вектора у, в которых стоят 1.

Рассмотрим библиотеку V = {2/1,2/2?2/з?2/4}" такую, что.

где К и К2 — элементарные монотонные конъюнкции, состоящие из I переменных, — элементарная монотонная конъюнкция длины т (1, т > 0), К, К2, Кз не пересекаются по переменным и не содержат *1? %2)? *^4>*?5? *^6 •.

ь

Покажем, что для ЗИП I = (J3ⁿ, V, У) при надлежащем подборе параметров I и лп оптимальный ПИГ над базовым множеством (Л" ^п, 0) не является деревом.

Рис. 3.3. Граф и₀

Рассмотрим граф Щ, разрешающий ЗИП Ji, который изображен на рис. 3.3. Здесь и далее всюду в данном подпункте ребром с приписанной ему конъюнкцией обозначается цепочка ребер, которым приписаны переменные, входящие в эту конъюнкцию.

Если К' и К" — элементарные монотонные конъюнкции, то справедливы следующие простые соотношения.

где к — длина конъюнкции К'. Последнее соотношение следует из того, что Nk' — (п — к)-мерная грань куба В^п.

Покажем, что можно так подобрать параметры I и т, что любой граф, разрешающий ЗИП 1 и имеющий вид дерева, будет иметь сложность большую, чем T (Uo) —

Согласно следствию 10 из теоремы 21 будем рассматривать деревья, состоящие только из четырех главных цепей записей, при этом, согласно свойству 7 не имеет смысла рассматривать деревья, в которых дублируются вхождения переменных. Таким образом, возможны только следующие случаи, изображенные на рис. 3.4, которые схематически отображают отношения (в смысле пересечения) главных цепей.

Рис. 3.4. Возможные случаи пересечения главных цепей.

На рис. 3.4 и далее цифра внутри схематического изображения дерева означает число листьев в дереве.

Сразу отметим, что деревья вида (4) и (5), изображенные на рис. 3.4, не могут разрешать ЗИП 1, так как нет переменной, которая бы входила в три записи из библиотеки V одновременно и, следовательно, не существует ни одного ребра, которое принадлежало бы трем главным цепям одновременно. Рассмотрим оставшиеся случаи.

Если имеет место случай (1), то объединяя главные цепи записей 2/1 и j/2, например, по ребрам, соответствующим переменным из ifj, мы получим дерево меньшей сложности. Тем самым, дерево вида (1) не может быть оптимальным.

Если главные цепи пересекаются, как в случае (2) на рис. 3.4, то единственный кандидат на оптимальное дерево имеет вид, изображенный на рис. 3.5. Это дерево обозначим через U.

Рис. 3.5. Граф U.

Подсчитаем сложность дерева U:

Таким образом, T (U) > Т ((/о), например, при выполнении следующих неравенств: 2/ + га-4−3^/ + га + 4и/> log₂(/ + 5) — 2, а эти неравенства справедливы при любых га, / > 0.

Если главные цепи пересекаются, как в случае (3) на рис. 3.4, то единственный кандидат на оптимальное дерево имеет вид, изображенный на рис. 3.6. Это дерево обозначим через (/г;

Рис. 3.6. Граф С/г.

Тогда.

Таким образом, Т (иъ) > Т (%), например, при выполнении неравенства тп 4−1 ^ / -f 1 -f log₂(/ -f 5), т. e. при m ^ log₂(/ + 5) + /.

Таким образом, если взять m > log₂(/ 4- 5) 4- l и / > 0 (при n > 9 это можно сделать), то для любого дерева, разрешающего ЗИП />, его сложность будет больше сложности графа C/q, что и доказывает недревовидность оптимального графа для ЗИП 1.

Базовое множество элементарных монотонных конъюнкций. В этом подпункте мы будем рассматривать графы над базовым множеством (/С^п, 0) и докажем существование такой ЗИП типа Sbool, которая имеет недревовидный оптимальный ПИГ. Заметим, что ЗИП Д, приведенная в предыдущем подпункте не дает желаемого результата для базового множества элементарных монотонных конъюнкций. В самом деле, подсчитаем сложность графа Uq, изображенного на рис. 3.3, но уже понимая (как и везде далее в этом подпункте) под ребром, которому приписан символ конъюнкции, не цепочку ребер, как в предыдущем подпункте, а именно одно ребро с нагрузкой в виде этой конъюнкции. Итак,.

Сложность же графа L/2, изображенного на рис. 3.6, будет равна Откуда.

Очевидно, что T (Uo) > ^(^2) для любых т,/ > 0.

Докажем два полезных свойства.

Свойство 8. Пусть U произвольный ПИГ над базовым множеством (JCⁿ, 0), разрешающий некоторую задачу типа Sbool, такой,.

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

Доказательство. Пусть С и — упомянутые в условии главные цепи записей у и у2 соответственно. Пусть у = К и у2 = К2. Поскольку цепи С и С2 не пересекаются ни с какими другими, то сложность, вносимая цепями Ci и С2 в сложность графа U, не меньше чем 2 (она равна двум, когда каждая из цепей представляет собой ребро с приписанной ему конъюнкцией). Заменим в графе U цепи С и С2 на три ребра. Первое, исходящее из корня, которому приписана конъюнкция К & К2, и два, исходящих из конца первого ребра, которым приписаны конъюнкции К[ и К'₂ соответственно, где К[ есть конъюнкция, состоящая из переменных, оставшихся от конъюнкции К{ после удаления переменных конъюнкции К & К2 («= 1,2). Сложность этих трех ребер будет не больше чем 1 + 2 • 2~² = 3/2 < 2, так как по условию длина конъюнкции К & К2 не меньше чем 2. Следовательно, сложность графа, полученного после такой замены, будет меньше сложности графа U что и доказывает неоптимальность графа U.

Свойство 9. Пусть U произвольный ПИ Г над базовым множеством (?^п, 0), разрешающий некоторую задачу типа Sboolt такой, что в нем есть вершина, отличная от корня, с полустепенью исхода 1. Тогда ПИГ U не может быть оптимальным.

Доказательство. Пусть (3 — вершина графа U, отличная от корня, с полустепенью исхода 1. Пусть с — ребро, входящее в 0, а С2 — ребро, исходящее из (3. Пусть К и К2 — конъюнкции, приписанные ребрам Ci и С2 соответственно. Тогда припишем ребру с конъюнкцию К1К2 и удалим ребро сгТем самым согласно свойству 6 получим более простой граф, разрешающий исходную задачу. Следовательно, граф U не был оптимальным, что и требовалось доказать.

Теорема 23. Если п > 26 и базовое множество есть множество элементарных монотонных конъюнкций (АС^П, 0), то существует такая ЗИП типа Sbooij для которой любой оптимальный ПИГ над (АС^П, 0) не является деревом.

Доказательство. Рассмотрим библиотеку V₂={yi, y2, Уз, 2/4, Уь, Уб}, такую, что.

где К1 и К2 — элементарные монотонные конъюнкции, состоящие из I переменных (I > 1), К4, К& — элементарные монотонные конъюнкции длины т (га > 1), и все (г = 1,5) попарно не пересекаются по переменным и не содержат переменных х, • • •, ^хб-

Покажем, что для ЗИП /2 = (В^п, V^,^) при надлежащем подборе параметров / и т оптимальный ПИГ над базовым множеством (?^п, 0) не является деревом.

Рассмотрим граф С/з, разрешающий ЗИП /2, который изображен на рис. 3.7. Здесь и далее всюду в данном подпункте ребром с приписанной ему конъюнкцией обозначается именно ребро, а не цепочка ребер, как было ранее.

Рис. 3.7. Граф С/з.

Подсчитаем сложность графа [/3:

Покажем, что можно так подобрать параметры I и га, что любой граф, разрешающий ЗИП /2 и имеющий вид дерева, будет иметь сложность большую, чем Т (С/₃).

Согласно следствию 10 из теоремы 21 будем рассматривать деревья, состоящие только из шести главных цепей записей, причем в соответствии со свойством 9 будем считать, что в них нет вершин, кроме, может быть, корня, которые имели бы полустепень исхода 1. Возможны только следующие случаи, изображенные на рис. 3.8, которые схематически отображают отношения (в смысле пересечения) главных цепей.

Напомним, что цифра внутри схематического изображения дерева означает число листьев в дереве.

Сразу отметим, что деревья вида (1), (2) и (3), изображенные на рис. 3.8, не могут разрешать ЗИП /2, так как нет переменной, которая бы входила в четыре записи из библиотеки V2 одновременно и, следовательно, не существует ни одного ребра, которое принадлежало бы четырем главным цепям одновременно.

Рис. 3.8. Возможные случаи пересечения главных цепей.

Так как из любых трех записей из всегда можно выбрать две записи, которые будут иметь по крайней мере две общие переменные (напомним, что l, m > 1), то деревья вида (4) подпадают под свойство 8, откуда следует, что они не могут быть оптимальными.

Рассмотрим случай (5), изображенный на рис. 3.8. Так как через правое ребро, растущее из корня, проходят три главные цепи, то, следовательно, это цепи соответствуют либо тройке записей гд, уз и ys, либо тройке записей у2, у 4 и уеБез ограничения общности будем считать, что они соответствуют первой из троек. Тогда оставшиеся цепи соответствуют записям уг, у л и ув, которые имеют общими только переменные из конъюнкции К2. Следовательно, левому ребру, растущему из корня (обозначим его через с, а его конец — через /?), может соответствовать только конъюнкция, состоящая из переменных конъюнкции К2- Но тогда мы можем приписать ребру с конъюнкцию К2 и перебросить среднее ребро, растущее из корня в вершину 0. Так как сложность вершины 0 меньше сложности корня, то дерево типа (5) не может быть оптимальным.

Рассмотрим случай (6), изображенный на рис. 3.8. Так как через правое ребро, растущее из корня (обозначим его через С, а его конец — через /3), проходят три главные цепи, то без ограничения общности можно считать, что они соответствуют записям у 1, уз и у5. Поскольку эти три записи имеют общими только переменные из конъюнкции К, то как ребру Ci, так и правому ребру, растущему из 0 (обозначим его через C2), могут соответствовать только конъюнкции, состоящие из переменных конъюнкции К. Но тогда мы можем приписать ребру с конъюнкцию К и вообще выбросить ребро сгСледовательно, согласно свойству 6 дерево типа (6) не может быть оптимальным.

Рассмотрим случай (7), изображенный на рис. 3.8. Так как две пары главных цепей пересекаются, то соответствующие им две пары записей пересекаются по переменным, но тогда однозначно оставшаяся пара записей также пересекается по переменным. Откуда следует, что оставшаяся пара главных цепей подпадает под свойство 8, и значит, дерево типа (7) не может быть оптимальным.

Если главные цепи пересекаются, как в случае (8) на рис. 3.8, то единственный кандидат на оптимальное дерево имеет вид, изображенный на рис. 3.9. Это дерево обозначим через С/₄.

Рис. 3.9. Граф U4.

Подсчитаем сложность дерева ?/₄:

Тогда

Таким образом, при т > I + 1 будем иметь Т (?/₄) > Т (?/з).

Если главные цепи пересекаются, как в случае (9) на рис. 3.8, то единственный кандидат на оптимальное дерево имеет вид, изображенный на рис. 3.10. Это дерево обозначим через ?/5.

Рис. 3.10. Граф С/5.

Подсчитаем сложность дерева ?/5: Тогда Отсюда, например, при I > 2 имеем T (U$) > T (U$).

Таким образом, если взять />2ит>/4−1(а при п > 26 это можно сделать), то для любого дерева, разрешающего ЗИП /2, его сложность будет больше сложности графа ?/3, что и доказывает недревовидность оптимального графа для ЗИП /2.