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

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

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

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

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

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

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

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

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

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

Обратимся к конкретному примеру. Зададим исходную информацию булевой матрицей Р, столбцы которой поставлены в соответствие элементам объединенного множества аргументов системы, а строки соответствуют функциям и показывают наборы их аргументов: первая строка соответствует некоторой функции f1 (a, g, j), вторая — функции f2 (b, f, k), третья — функции f3 (f, j, k) и т. д.