Дерево - вариант - решение
Cтраница 1
Дерево вариантов решений отображает иерархический процесс генерации ( вывода) решений задачи синтеза и упорядоченного поиска оптимального решения. Вершина - корень дерева - соответствует параметрам входных потоков синтезируемой системы, которые известны из постановки задачи. Промежуточные вершины соответствуют некоторым промежуточным состояниям ХТС, определяемым не только значениями параметров выходных потоков сгенерированных подсистем, но и величиной критерия ф и некоторыми эвристическими коэффициентами различия между этим промежуточным и требуемым конечным состоянием ХТС. [1]
Рассмотрим алгоритмы упорядоченного ограниченного перебора решении НФЗ на дереве вариантов решений ( см. разд. [2]
Методы синтеза ТС, основанные на поиске оптимального варианта ТС на дереве вариантов решений, являются, как правило, процедурами полного перебора, стратегии которого не рассматриваются в разработанных работах. При использовании процедур упорядоченного перебора [8,46,47] не проведен сравните ьный анализ эффективности различных стратегий упорядоченного еребора. [3]
Методы синтеза ТС, основанные на поиске оптимального варианта ТС на дереве вариантов решений, являются, как правило, процедурами полного. При использовании ппоцедур упорядоченного перебора [8,46,47] не проведен сравните ьный анализ эффективности различных стратегий упорядоченного еребора. [4]
 |
Решающий И / ИЛИ подграф для дерева декомпозиции ( к. [5] |
Поиск решений НФЗ в пространстве состояний отображается с помощью семантического графа, называемого деревом вариантов решений. [6]
 |
Нопые факты, добанляемые ПП, сопоставляются с другими ПП.| Выполнение ПП влияет на действия лица, принимающего решения. [7] |
Процедура сопоставления с фактами условия ПП (6.1) при поиске решения НФЗ порождает дерево вывода решений, или дерево вариантов решений ( см. разд. Результат решения НФЗ в виде ДВР хранится в БД, или в рабочей БЗ продукционной системы. [8]
В соответствии с математическими формулировками стратегий декомпозиции множества решений НФЗ, представленными соотношениями (6.7) - (6.10) предлагаются три алгоритма упорядоченного ограниченного перебора на дереве вариантов решений ( ДВР), или три вида порождающих процедур построения для некоторого имплицитного ДВР усеченного эксплицитного дерева ( см. разд. [9]
Блок Б4 ( Блок вывода решений) используется для поиска оптимального варианта размещения ЕО и трассировки ТП. Блок программно реализует процедуры генерации дерева вариантов решения с использованием различных стратегий Ветвления ( лучевого, волнового и луче-волнового - см. разд. Блок написан на языках Пролог и Фортран-77, требуемый объем памяти - 100 Кбт. [10]
Декомпозиция исходной задачи оптимизации резервирования системы также осуществляется на каждом уровне ветвления и заключается в следующем. Фиксируемые переменные xi ( / l N) в активных вершинах дерева вариантов решений выбираются таким образом, чтобы как можно больше исключить из рассмотрения ( отсеить) вершин дерева вариантов решений и снизить при этом размерность решаемых задач оптимизации. Однако в предложенном методе выбора фиксируемых переменных [241] не учитывается их влияние на удельное повышение показателя надежности системы в целом. [11]
Этот алгоритм последовательно применяется на каждом уровне ветвления до получения полностью целочисленного решения. Ветвление осуществляется фиксированием некоторой переменной XL в предшествующем нецелочисленном решении Xi, которому соответствует i-я активная вершина дерева вариантов решений. Следует отметить, однако, что в работе [239] не предложено правило, в соответствии с которым необходимо каждый раз выбирать фиксируемую переменную в i - й активной вершине дерева вариантов решений. [12]
Декомпозиция исходной задачи оптимизации резервирования системы также осуществляется на каждом уровне ветвления и заключается в следующем. Фиксируемые переменные xi ( / l N) в активных вершинах дерева вариантов решений выбираются таким образом, чтобы как можно больше исключить из рассмотрения ( отсеить) вершин дерева вариантов решений и снизить при этом размерность решаемых задач оптимизации. Однако в предложенном методе выбора фиксируемых переменных [241] не учитывается их влияние на удельное повышение показателя надежности системы в целом. [13]
Этот алгоритм последовательно применяется на каждом уровне ветвления до получения полностью целочисленного решения. Ветвление осуществляется фиксированием некоторой переменной XL в предшествующем нецелочисленном решении Xi, которому соответствует i-я активная вершина дерева вариантов решений. Следует отметить, однако, что в работе [239] не предложено правило, в соответствии с которым необходимо каждый раз выбирать фиксируемую переменную в i - й активной вершине дерева вариантов решений. [14]
В программах П1 и П2 реализован метод ветвей и границ с использованием оригинальных нижних и верхних границ решения. При решении задач с помощью П2 в качестве КО используется минимизация суммарного времени запаздывания, которое будет характеризовать соответствующий вариант расписания. Допускается задание таких видов останова ВП: по величине е, по времени счета, по числу анализируемых подзадач, по максимальному номеру подзадачи, по тому, пуст ли список активных подзадач. Пользователь может различными способами влиять на процесс ветвления дерева вариантов решения задачи. [15]
Страницы: 1