§ 5. Применение ориентированных деревьев в задачах теории кодирования и диагностирования

Ориентированные деревья применяются при представлении в ЭВМ комбинаторных объектов.

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

Пример. □

■

Двоичные деревья используются при анализе алгоритмов, в методах поиска информации и т.д.

Одной из часто встречающихся задач является следующая:

даны п весов и п листьев (висячих вершин) такие, что

1. - вес вершины v_i ;

2. -длина пути из корня дерева в v_i ;

3. длина взвешенных путей минимальна.

Более общая задача возникает в теории кодирования.

Префиксным кодом называется множество таких слов, среди которых никакое не является началом другого.

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

Пример. □ Пусть набор 000, 001, 01, 10, 11 образует префиксный код. Если последовательность букв 1011001000 образована из его слов, то она раскладывается на слова 10, 11, 001, 000. ■

Пусть алфавит из т букв, Т – такое ордерево, что

1. полустепень исхода каждой вершины не превышает т ;

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

Тогда всякий лист можно связать со словом, образованным конкатенацией букв в том порядке, в котором они появляются на пути к листу v от корня. Слова, связанные таким образом, образуют префиксный код.

В двоичном дереве из рассмотренного примера слова образуют следующий префиксный код: { 000, 001, 010, 011, 10, 110, 111 }.

Задача состоит в том, чтобы для данного т и длин построить, используя буквы алфавита , префиксный код, длины слов которого составляют .

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

Процесс разложения последовательности на кодовые слова называется декодированием. Его можно осуществить с помощью дерева, соответствующего префиксному коду.

Из процесса декодирования следует, что стоимость декодирования кодового слова пропорциональна числу букв в этом слове. Если w_i частота появления сообщения М_i , то ожидаемая стоимость деко-дирования зависит от длины взвешенных путей, т.е. от суммы ,

где l_i – длина пути от корня до листа, соответствующего сообщению М_i .

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

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

Чтобы выполнить это, можно слить любые два из этих списков, например, S₁ и S₂ и получить новый список . Затем можно слить два списка из множества и продолжить слияние до тех пор, пока не будет получен один список. Для описания такого способа можно использовать бинарное дерево.

Пример. □ Рассмотрим дерево, которое описывает порядок слияния пяти списков .

С ливаем списки S₁ и S₂ , чтобы получить . Сливаем списки и S₃ , чтобы получить .

Сливаем списки S₄ и S₅ , чтобы получить .

Сливаем списки и , и полу-чаем требуемый список. ■

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

Стоимость слияния любых двух списков пропорциональна общему числу элементов в списках. Поэтому стоимость слияния списков равна

,

где число процессов слияния, в которых участвуют элементы списка S_i .

Например, стоимость слияния списков из рассмотренного примера равна .

Из рисунка видно, что в этом случае l_i фактически равно длине пути из корня дерева в лист, соответствующий S_i .

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

Таким образом, задача минимизации стоимости слияния списков S₁, S₂,…,S_L эквивалентна задаче построения бинарного дерева с минимальной длиной взвешенных путей для весов .

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

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

Выбор очередной точки контроля при стратегии половинного деления определяется минимумом функции предпочтения:

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

Функция предпочтения определяет такую линию, которая разделяет пространство подозреваемых дефектных координат на две более-менее равные группы. В процессе решения задачи строится взвешенное дерево поиска дефектов. На практике более предпочтительной является стратегия половинного деления, позволяющая построить дерево поиска дефектов, которое хуже оптимального не более, чем на 15 - 20%.

Рациональная методика построения допустимого решения при (условном) поиске дефектов по взвешенному дереву диагностирования основывается на методах комбинаторной оптимизации динамического программирования, ветвей и границ, рекурсивном методе, которые уменьшают число рассматриваемых вариантов по сравнению с полным перебором. Результат диагностического эксперимента – определение технического состояния объекта с точностью до неисправного функционального элемента. Условные алгоритмы оцениваются с позиции минимума средних затрат при поиске дефектов и минимума максимального значения, а безусловные – суммарных затрат на создание бинарного дерева поиска дефектов.

Таким образом оцениваются временные затраты на диагностирование неисправных элементов и для поиска дефектов устройства.