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

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

Если провели оптимизация по одной группе параметров, то этот он может быть совершенно не оптимальный по другой группе параметров. Алгоритм оптимальный по количеству проверок, может быть не оптимальный по стоимости… в любом случае, оптимальный алгоритм должен содержать полный набор проверок и не должен быть избыточным. Оптимальный алгоритмы могут быть единственные, а могут быть множественными (равносильными).

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

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

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

Типовые виды функции предпочтения:

• Отдаётся предпочтению функции с минимальным номером проверок.

Вставка 2 глупо. Это вальюристический подход. Чем больше номер – тем менее рационален. Это функция предельно проста.

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

• Функция которая построена по принципу «минимальный столбец, максимальная строка».

Отбираются проверки di, которые строятся по принципу отбора проверок столбцов с минимальным количеством единиц.

• Функция предпочтения связанная с минимальной стоимостью.

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

{} – обозначают группу проверок.