Математика \ Дискретная математика

Задача о кодировании. Задача о генерировании, страница 2

В качестве первого элемента теста целесообразно выбрать такую строку из матрицы X, в которой число единиц как можно ближе к числу нулей, так, чтобы два блока разбиения были по возможности равномощными. Следующий выбранный нами признак будет делить эти блоки на более мелкие части, и здесь мы также должны заботиться о том, чтобы Дробление блоков шло равномернее, в идеале на равные части. В конце концов этот процесс приведет к некоторому тесту — множество А окажется разбитым на одноэлементные блоки.

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

Вернемся к той же матрице X, пронумеровав для удобства ее строки и столбцы:

Следуя сформулированным правилам, выберем в качестве первого признака строку 1, разбивающую множество столбцов матрицы Х на два блока:

(строка, задающая разбиение, отмечена символом +).

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

Дальнейший процесс конструирования теста отображается  следующей последовательностью разбиений:

в качестве второго включаемого в тест признака выбирается строка 6, и матрица Х разбивается на три столбцовых минора

следующий выбор падает на строку 2, и при этом множество столбцов матрицы Х разбивается на пять блоков

наконец, последней выбирается строка 9, в результате чего множество столбцов разбивается на одноэлементные блоки, а выбранные строки образуют тест:

Обобщение задачи о минимальном тесте. Нахождение минимального теста для матрицы Х позволяет иногда получать хорошие приближения к оптимальному решению задачи о перекодировании столбцов этой матрицы, осуществляемом дизъюнктивным матричным оператором ВÑ. Однако при малой плотности единиц в матрице Х оно приводит обычно к завышенной длине находимого кода. В этом случа ецелесообразно решать данную задачу в ее первоначальной постановке, конструируя решение не из отдельных строк матрицы X, а из некоторых совокупностей ее строк, точнее, из покомпонентных дизъюнкций строк, образующих ту или иную совокупность.

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

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

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

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

Скачать файл