Приведенные на рис. 5, а—в схемы имеют специальное название — графы и состоят из нескольких вершин (на рис. 5, а—в вершины обозначены в виде прямоугольников) и соединяющих их отрезков — ребер. Так, в виде графа изображают схемы движения транспорта, например метрополитена, на которых вершинами являются станции, а ребрами — соединяющие их пути.
Предположим, что необходимо найти на схеме метрополитена путь от станции А к станции В. Если такой путь найден, на математическом языке этот факт может быть выражен так: вершина А связана с вершиной В. В этом случае граф называется связным. Показав стрелками на отрезках, соединяющих станции, порядок прохождения станций при движении от станции А к станции В, получим граф, называемый ориентированным. При разветвленной схеме линий метрополитена можно выбрать несколько вариантов пути от станции А к станции В. Путь, даже проходящий через одни и те же станции, но по разным ребрам графа, называют цепью. Замкнутую цепь, т. е. начинающуюся и заканчивающуюся в одной и той же вершине, называют циклом. На схеме метрополитена примером цикла может служить кольцевая линия.
Наличие циклов в графах, отражающих поиск дефектов, говорит о том, что выполнение тех или иных действий не приближает нас к искомому дефекту. Поэтому поиск дефектов должен строиться таким образом, чтобы отражающий его граф не имел циклов. Для связных графов, не имеющих циклов, используют специальный термин — дерево, или дерево решений.
Дерево решений представляет собой граф, не имеющий кратных ребер, т. е. каждая пара его вершин соединяется только одной цепью. Таким образом, оказывается, что оно показывает один и только один путь от вершины А к вершине В. Для обозначения элементов дерева используют специальную терминологию, частично заимствованную из ботаники. Вершину, соответствующую первой проверке, обычно называют корнем дерева, а вершины, не имеющие выходящих ребер, — висячими. Путь, соединяющий корень дерева с висячей вершиной и проходящий по ребрам графа, называют ветвью.
Из каждой вершины дерева может выходить несколько ребер. Применительно к поиску дефектов, когда вершиной представляют проверку, которая имеет два результата — проверяемый блок исправен или неисправен, — из нее соответственно выходят только два ребра. В соответствии с этим рассматриваемые здесь и ниже деревья можно характеризовать следующими параметрами:
числом проверок я, равным числу невисячих вершин; числом ветвей h, которое численно равно количеству N возможных дефектов в рассматриваемой модели объекта контроля; кроме того, каждая ветвь показывает путь через невисячие вершины-проверки к висячей вершине-дефекту, проходимый от корня дерева к /-й висячей вершине при поиске /-го дефекта;
длиной ветви hh определяемой как число проверок, выполняемых для выявления /-го дефекта; она равна числу вершин (не считая висячей), проходимых при «движении» от корня дерева к /-й висячей вершине;
суммарной длиной ветвей кс представляющей собой общее число проверок, которое надо выполнить для выявления всех N дефектов;
средней длиной ветвей kcp=kс/N, т. е. среднему числу проверок, затрачиваемому на отыскание одного дефекта.
Таким образом, ни один из дефектов не может быть обнаружен быстрее, чем за h0min число проверок.
Принципиально любая из вершин дерева может быть его корнем, что применительно к поиску дефектов позволяет осуществить любую из возможных проверок первой. Однако изменение места выполнения первой проверки изменяет не только внешний вид дерева, что видно из примеров 4 и 5, но и количество проверок, затрачиваемых на обнаружение того или иного дефекта, а также среднюю длину ветвей.
Применительно к объектам контроля, представленным моделями из последовательно соединенных блоков или элементов, достаточно эффективным является способ средней точки, задающий принцип выбора места выполнения первой проверки и последовательности остальных. Для этого способа характерно то, что первую проверку выполняют в точке, делящей цепочку из последовательно соединенных блоков или элементов пополам (при четном их числе) или примерно пополам (при нечетном) .
В модели, показанной на рис. 4, число блоков нечетное, поэтому место первой проверки можно выбрать на входе блока 5 (проверка зтЗ) либо на его выходе (проверка тс8). Точки выполнения второй, а также всех последующих проверок выбирают по этому же принципу. Последовательность выполнения проверок в том случае,
Рис. 6. Последовательность выполнения и результаты проверок при выборе места первой проверки способом средней точки (цифрами показаны номера блоков по модели рис. 4)
когда первой осуществляется проверка п8, приведена на рис. 6.
Теоретически минимальное количество проверок способом средней точки в том случае, когда проверку блока выполняют только с учетом критериев исправен — неисправен, составляет
kmin = log2n, (1)
где п — число последовательно соединенных блоков (элементов) в модели объекта контроля.
Так как количество проверок k может быть только целым числом, справедливы следующие соотношения:
п | 2 | до 4 | до 8 | до 16 | до 32 | до 64 |
k | 1 | 2 | 2 или 3 | 3 или 4 | 4 или 5 | 5 или 6 |
