Cтраница 4
Активная вершина ДВР принадлежит либо данному и предыдущему уровням иерархии слоев вершин ДВР, лиГю данному ( либо предыдущему) уровню иерархии слоев вершин. Активной вершиной ДВР называют такую висячую вершину, для которой на данном этапе декомпозиции образуются все ее вершины-потомки на следующем уровне иерархии слоев вершин ДВР. Процесс оГфазования, или порождения, вершин-потомков для активной вершины-предка также называют процессом декомпозиции, или раскрытия, активной вершины. Процесс раскрытия активной вершины соответствует операции декомпозиции некоторого множества решений НФЗ на совокупность подмножеств решений. Процесс декомпозиции активной вершины ДВР отображает операцию применения некоторого оператора к состоянию, которое соответствует данной активной вершине ( см. разд. [46]
Сущность ее заключается в том, что в качестве активной вершины ДВР выбирают одну из висячих вершин последнего образовавшегося при декомпозиции исходной задачи слоя вершин ДВР. После завершения цепи ДВР до некоторого альтернативного варианта решения или просмотра всех висячих вершин некоторого слоя вершин ДВР выбор активной вершины происходит на предыдущем слое. [47]
Этот алгоритм последовательно применяется на каждом уровне ветвления до получения полностью целочисленного решения. Ветвление осуществляется фиксированием некоторой переменной XL в предшествующем нецелочисленном решении Xi, которому соответствует i-я активная вершина дерева вариантов решений. Следует отметить, однако, что в работе [239] не предложено правило, в соответствии с которым необходимо каждый раз выбирать фиксируемую переменную в i - й активной вершине дерева вариантов решений. [48]
Теперь если взять произвольный запрос х Е X, то алгоритм функционирования сети на запросе х можно описать аналогично алгоритму разметки графа [51, 61]: считаем, что в начальный момент все вершины сети, кроме корня, неотмеченные, а некоторое упорядоченное множество вершин сети, которое назовем множеством активных вершин, содержит только корень сети. На каждом очередном шаге делаем следующее. Если множество активных вершин не пусто, то выбираем первую активную вершину и удаляем ее из множества активных вершин. Алгоритм завершает работу в тот момент, когда множество активных вершин окажется пустым. [49]
Активная вершина ДВР принадлежит либо данному и предыдущему уровням иерархии слоев вершин ДВР, лиГю данному ( либо предыдущему) уровню иерархии слоев вершин. Активной вершиной ДВР называют такую висячую вершину, для которой на данном этапе декомпозиции образуются все ее вершины-потомки на следующем уровне иерархии слоев вершин ДВР. Процесс оГфазования, или порождения, вершин-потомков для активной вершины-предка также называют процессом декомпозиции, или раскрытия, активной вершины. Процесс раскрытия активной вершины соответствует операции декомпозиции некоторого множества решений НФЗ на совокупность подмножеств решений. Процесс декомпозиции активной вершины ДВР отображает операцию применения некоторого оператора к состоянию, которое соответствует данной активной вершине ( см. разд. [50]
X, то алгоритм функционирования сети на запросе х можно описать аналогично алгоритму разметки графа [51, 61]: считаем, что в начальный момент все вершины сети, кроме корня, неотмеченные, а некоторое упорядоченное множество вершин сети, которое назовем множеством активных вершин, содержит только корень сети. На каждом очередном шаге делаем следующее. Если множество активных вершин не пусто, то выбираем первую активную вершину и удаляем ее из множества активных вершин. Алгоритм завершает работу в тот момент, когда множество активных вершин окажется пустым. [51]
Наименьшее число ветвлений обеспечивает стратегия волнового ветвления, что соответствует минимальному количеству рассматриваемых альтернативных вариантов решения при поиске оптимального решения. Но большой объем информации о висячих вершинах ДВР, что соответствует информации о промежуточных вариантах размещения ЕО, усложняет организацию вычислительного процесса и резко увеличивает необходимый объем оперативной памяти ЭВМ. Хотя стратегия лучевого ветвления дает наибольшее число ветвлений, а следовательно, и наибольшее число просматриваемых вариантов решений, она является наиболее предпочтительной при решении сложных эвристическо-комбинаторных задач оптимального размещения ЕО. Это вызвано простотой организации вычислительного процесса на ЭВМ и меньшим требуемым объемом оперативной памяти, необходимой для запоминания характеристики активных вершин ДВР. [52]
Теперь если взять произвольный запрос х Е X, то алгоритм функционирования сети на запросе х можно описать аналогично алгоритму разметки графа [51, 61]: считаем, что в начальный момент все вершины сети, кроме корня, неотмеченные, а некоторое упорядоченное множество вершин сети, которое назовем множеством активных вершин, содержит только корень сети. На каждом очередном шаге делаем следующее. Если множество активных вершин не пусто, то выбираем первую активную вершину и удаляем ее из множества активных вершин. Алгоритм завершает работу в тот момент, когда множество активных вершин окажется пустым. [53]