4.11. Кратные условные диагностические эксперименты

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

Алгоритм 4.4. Даны автомат М, его множество допустимых начальных состояний и дерево кратного эксперимента для М и требуется найти начальное состояние М с помощью кратного условного эксперимента. (1) Приложим входную последовательность, указанную для начальной ветви, к первому экземпляру М. Пусть Перейдем к ветви, для которой перечисленная выходная последовательность совпадает с реакцией, данной последней примененной входной последовательностью. (3) (а) Если ветвь не является оконечной, то приложим входную последовательность, указанную для этой ветви, к экземпляру М. Увеличим k на 1 и вернемся к (2). (б) Если ветвь оконечная, то одноэлементное множество связанное с этой ветвью, содержит начальное состояние М.

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

Следовательно, устраняется необходимость в тех экземплярах М, которые не появляются вдоль этого пути.

Алгоритм может быть продемонстрирован деревом кратного эксперимента на рис. 4.13. Если истинное начальное состояние есть 3, то приложение а к первому экземпляру дает 0, который ведет к ветви, связанной с . Соответственно последовательность, примененная ко второму экземпляру, есть , что дает и, следовательно, ведет к ветви, связанной с (3). Тогда можно заключить, что начальное состояние есть 3.

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

это число не может превышать общего числа экземпляров в дереве. Тогда, по теореме 4.8, кратность кратного условного эксперимента не превышает Если индивидуальные диагностические последовательности построены возможно более короткими, то, по теореме 4.7, длина эксперимента не может превосходить

Следовательно, мы имеем теорему.

Теорема 4.9. Диагностическая задача для автомата с n состояниями и m допустимыми состояниями может всегда быть решена с помощью кратного условного эксперимента длины l и кратности с, где

Граница в (4.10) может быть достигнута для и любого Граница в (4.11) может быть достигнута для любого n и как показано на примере автомата в таблице 4.9 и дерева кратного эксперимента на рис. 4.14: если начальное состояние есть либо либо m, то для диагностической задачи для и множества допустимых начальных состояний требуется в точности экземпляров.

Преимущество кратного условного эксперимента над кратным безусловным экспериментом может быть измерено величиной, на которую число экземпляров в дереве кратного эксперимента превышает высоту этого дерева. Таблица 4.10 представляет автомат с состояниями, для которого преимущество условного эксперимента над безусловным для любого множества допустимых начальных состояний является существенным. Дерево кратного эксперимента для и множества допустимых начальных состояний (где и где как m, так и n являются четными) показано на рис. 4.15. Очевидно, что число экземпляров, включенное в дерево кратного эксперимента, есть

Таблица 4.10. Автомат (см. скан)

а его высота есть 2. Таким образом, экземпляров А23 требуется для решения задачи с помощью безусловного эксперимента и только 2 экземпляра для решения задачи путем условного эксперимента.

Следует отметить, что метод построения кратного условного эксперимента, как и метод построения кратного безусловного эксперимента, вообще говоря, не минимизируют длину или кратность эксперимента. Длина и кратность во многих задачах могут быть уменьшены с помощью метода, описанного в конце § 4.10.