Cтраница 2
Исходные данные для определения характеристик вычислительных работ в АСУП представляются в виде графов задач управления: G / ( R /, Г /), где t - периодичность повторения ( t 1, 2, 3, 4, 5, 6 соответственно для задач часовой, сменной, суточной, недельной, квартальной и годовой периодичности); Rt г - множество распределяемых задач ( программ); Ft - отображение Rt в Rt по информационным связям. [16]
При объединении в пары элементов X с определенными элементами набора операторов Г достижима в пределе ( 7) ситуация, при которой граф задачи заменяется на дерево стратегии, как показано на фиг. Поиск в графе заменяется более легкой задачей установления множества, в которое входят элементы X, находящиеся на пути решения. [17]
Решение возникающей задачи может быть осуществлено при помощи алгоритмов решения СТЗ ДО ( однако их применение требует дополнительного обеспечения специальными приемами связности графа задачи) и алгоритмов, учитывающих блочный характер матрицы СТЗ. В статье [12] рассмотрены соответствующие модификации алгоритма К. В. Кима и известного метода декомпозиции. В частности, соответствующие графы могут иметь большую размерность вследствие многократного дублирования ( по числу продуктов) вершин и дуг исходной транспортной сети, однако на практике существует возможность существенного уменьшения этой размерности. В статье даются сравнительные оценки этих моделей для случая, когда возможно применение их обеих. [18]
Стандартное представление, принятое в работах по эвристическому поиску, - это направленный граф, узлы которого представляют дискретные состояния, а дуги, выходящие из некоторого узла, представляют процесс генерирования возможных его преемников. Множество X и функция генерирования множеств преемников Г: Х - 2Х определяют граф задачи. При этом стандартное представление задач в отношении полезности уступает упомянутому выше представлению ( X, Г) в виде раскрашенного графа. [19]
На основе имеющихся матриц смежности строятся соответствующие им матрицы достижимости, используемые для разбиения графов Gn на связные подграфы и части подграфов, соответствующие этапам и уровням преобразования информационных элементов. В результате каждый граф Gn разбивается на подграфы G. J G - Gn таким образом, что каждый подграф G является связным, а связи между элементами определяются отношениями типа Яа. Таким образом, каждый граф G задачи Zn разбивается на связные компоненты, которые соединены между собой совокупностью дуг, соответствующих отношениям Я / типа разреза или перешейка, то есть такими отношениями, устранение которых не нарушает полноты связности каждой компоненты. Каждая связная компонента представляет относительно замкнутый технологический этап обработки данных, характеризующийся определенными промежуточными результатами. [20]
Рассмотрим стандартные случаи изменения базисной пары множеств. Соответствующие этим случаям преобразования графа для удобства изложения мы будем расчленять на несколько последовательных преобразований, имеющих более специальный вид. Каждый раз будет получаться граф по своему строению допустимый в качестве базисного графа двухкомпонентной задачи. Поэтому каждое частичное преобразование мы вправе рассматривать как самостоятельное преобразование базисного - графа. [21]