Свойство канонического эффекта

Понятие канонического эффекта

Как можно видеть, из предыдущих разделов работы, для каждого из 7 модельных классов задач поиска нам удалось описать условия, при которых решение этих задач оптимально или близко к оптимальному. Это свойство существования условий, при которых решение базовых задач оптимально или близко к нему, предлагается называть каноническим эффектом. В данной главе исследуется насколько устойчив канонический эффект при вариации 3-х основных управляющих параметров модели, таких как объем памяти, имеющийся в распоряжении (т. е. число ребер информационного графа), множество функций, которые разрешается использовать при решении (т. е. множество базовых функций, используемых при нагрузке графа), и е-расширение запроса, которое позволяет ответу на задачу несколько отходить (на величину е) от требований задачи. В данной главе показывается, что при любой вариации, кроме 5-расширения запроса, мы уходим от канонического эффекта.

Напомним результаты, подтверждающие канонический эффект для наших 7 базовых классов ЗИП, как для средней сложности, так и для В-сложности:

• • для задач поиска с коротким ответом — следствия 4 и 5;
• • для задач поиска идентичных объектов — теоремы 13 и 14;
• • для задач о близости — теоремы 19 и 20;
• • для задачи включающего поиска — теоремы 31 и 34;
• • для задачи поиска с отношением поиска, являющимся отношением линейного предпорядка, — теорема 35;
• • для задачи о доминировании — теоремы 39 и 40;
• • для задачи интервального поиска — теоремы 50 и 51 (в частности, для одномерного случая — теорема 49).

Если практически не накладывать ограничений на базовое множество и объем памяти, то можно сформулировать теорему о наличии канонического эффекта для произвольной ЗИП.

Если Xi,…, X_n — разбиение множества X, то характеристической функцией разбиения Xi,…, X_n назовем переключатель такой, что для любого х е X

Скажем, что разбиение Х,… , Х_п множества X порождается ЗИП I = (X, V, р), если для любых х, х' € X.

Понятно, что если разбиение Xi,…, X_n порождено некоторой ЗИП I = (X, V, p), то п ^ 24.

Теорема 53. Если I = (X, V, р) — ЗЯЯ, Т = (F, (?) — такое измеримое базовое множество, что F содержит функцию тождественная 1, G содержит переключатель д, являющийся характеристической функцией некоторого разбиения, порождаемого ЗИП I, то

Доказательство. Пусть g? G — такой переключатель, что для некоторого разбиения Х,…, Х_п множества X, порожденного ЗИП.

I=(X, V, p), g = _Xx_l…

Обозначим Vi = j/(x), где х — произвольно взятый запрос из Х{

(* = М");

Построим следующий ИГ U над базовым множеством Т. Возьмем вершину, выпустим из нее п ребер, занумеруем их числами от 1 до п, объявим эту вершину корнем и припишем ей переключатель д. Из конца каждого ребра с номером г выпустим |VJ| ребер, концы этих ребер объявим листьями и сопоставим им взаимно однозначно записи из Vi, а ребрам припишем функцию тождественная 1.

Так как для любого запроса хб^ (г = 1, тг).

то ИГ U разрешает ЗИП I.

По построению для любого запроса х 6 X

откуда сразу следует, что.

Нижняя оценка следует из теоремы 4.

Заметим, что

Тем самым, теорема доказана.

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

В отличии от теоремы 53 условия, при которых достигается канонический эффект в наших 7 базовых классах ЗИП, описанные в перечисленных выше теоремах, являются вполне естественными и практически значимыми. Некоторое исключение составляет результат теоремы 31, предполагающий возможность вычислить за один шаг любую монотонную функцию, но для включающего поиска для «разумных» базовых множеств переменных и элементарных монотонных конъюнкций получены практически ценные алгоритмы, на которых достигается асимптотика функции Шеннона (теоремы 29 и 30).

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

• • базовое множество функций, характеризующее набор доступных средств;
• • ограничения на объем ИГ, характеризующий объем памяти, соответствующего ИГ алгоритма поиска;
• • е-расширение запроса; этот параметр позволяет получать вообще говоря новые типы задач поиска и применим к классу задач, которые можно условно назвать непрерывными (к нему относятся задача о доминировании, задача интервального поиска и задача поиска идентичных объектов, когда пространство запросов, например, — компактное подмножество вещественной прямой) и состоит в том, что запрос в новой задаче получается е-расширением запроса старой задачи.