Поиск минимальных разбиении. Приближенные методы, страница 3

Здесь находится строка 4, совместимая лишь со строкой 7. Сливаясь, они образуют вторую каплю, «выпадающую в осадок». Остальные три строки оказываются взаимно совместимыми и образуют третий элемент решения. Таким образом завершается формирование результата — матрицы-импликантьг U с минимальным числом строк:

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

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

8. Приближенные методы

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

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

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

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

Обширен и практически весьма важен класс оптимизационных задач. Такая задача обладает некоторым множеством решений S ={s1,s2,…,sk}, на котором обычно задается функция стоимости с (si). Решая оптимизационную задачу, надо найти такое ее решение, на котором функция стоимости принимает минимальное значение (в этом случае задача называется также минимизационной).

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

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

Получить полное дерево поиска можно методом его обхода или методом поярусного построения. Каждый из них задает свой порядок расщепления вершин. Метод обхода дерева поиска был уже рассмотрен нами ранее, на примере задачи нахождения кратчайшего покрытия. Идея этого метода отображена на рис. 26, где показано направление обхода дерева и порядок его построения (отображенный на рисунке нумерацией вершин). При методе поярусного построения дерева поиска последовательно строится ярус за ярусом, как это показано на рис. 27.