Безусловные алгоритмы контроля и их оптимизация

При синтезе алгоритмов контроля, как правило, рассматриваются различные варианты их построения. Если у нас безусловный алгоритм, то там важен состав используемых проверок. Этот состав должен быть такой, чтобы накрывались все столбцы таблицы покрытий. Каждому алгоритму соответствует свой параметр (стоимость, простота, время, количество проверок). Оптимизация всегда ведётся в определённом поле параметров. Чем больше параметров, тем труднее построить и выбрать оптимальное решение.

Оптимизация всегда ведётся по определённому параметру или по определённому полю параметров.

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

Оптимальные алгоритмы могут быть единственными и множественными. Множественные оптимальные алгоритмы называют равносильными.

Для того, чтобы построить алгоритм проверки, нужно в безусловном алгоритме отобрать проверки по определённому правилу. Когда строится алгоритм контроля, проверки оцениваются по определённой функции предпочтения – целевая функция. Обычно алгоритмы построения целевого решения громоздки. Важно доказать оптимальность построенного алгоритма. Квазиоптимальный алгоритм – недоказанный алгоритм.

Функции предпочтения.

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

1. Отдаёт предпочтения функции с минимальным номером проверки. Глупо. Это вальюнтаристический подход. Чем больше номер – тем менее рационален. Предельно проста.

2. Выбор функции предпочтения, которая максимизирует модуль характеристического числа проверок. Лучше использовать превращение, которое получает алгоритм при включении этой проверки.

3. Построена по принципу: «минимальный столбец – максимальная строка». Выбираем проверки, в столбцах которых минимальное число единиц, а из них выбираем проверку с максимальным модулем.

4. Связана с минимальной стоимостью.

5. По отношению стоимости к модулю характеристического числа проверки.

Общая схема получения оптимального алгоритма контроля (безусловного)

Построение алгоритма контроля предполагает выполнение типовых этапов.

1. Формирование таблицы покрытий. Анализ таблицы, удаление клонов по столбцам и строкам, упрощение.

2. По функции предпочтения минимальный столбец выбираются строки ядра. Выбранные строки ядра из таблицы покрытий исключаются. Вместе со строками ядра, выбрасываются и столбцы, которой этой строкой накрываются.

3. Используя одну из функций, формируем квазиоптимальный алгоритм контроля. Квазиоптимальность появляется тогда, когда есть точки ветвления (выбора).