Рассмотрим критерий память. Память вычислительных машин ограничена характеристиками системы. Память, требуемая для решения проектной задачи средствами САПР на каждом этапе определяется как сумма затрат памяти на хранение модели (модель соответствует позиции). Пусть для хранения модели pi требуется
МЕМ(рi) единиц памяти. Тогда на очередном m-ом этапе проектирования требуется хранить MEM(vm)= MEM(pi) для всех i
таких, что pi w(vm).
Если все k этапов известны, то реализация пректной задачи потребует памяти:
max MEM(vm) m=1,2,...,k.
Здесь будем считать, что существенных изменений в весах вершин не имеется, если MEM(pi) << MEM(vj) - МЕМ(pi) -мало, pi отбрасываемые методом "обратной волны" позиции из весов w(vi).
Следует отметить, что MEM - в общем виде зависит как от типа модели, так и от ее размерности. Для хранения матрицы системы уравнений в форме Коши с двойной точностью требуется 2n**2 машинных слов, где n - порядок системы. Для хранения собственных значений матрицы с той же точностью:
2n -для действительной и 2n для мнимой частей - всего 4n
машинных слов.
Таким образом, каждой позиции можно поставить в соответствие некоторую функцию MEM(pi), которую можно хранить, например, в виде коэфициентов полинома при степенях n, где n размерность задачи, либо в виде вызываемых программно функций от n.
Критерий быстродействие. Быстродействие определяется временем, требуемым на решение проектной задачи. На каждом этапе проектирования требуется выполнить модули, которые соответствуют переходам, входящим в вес дуги: t1,t2,...,tl. Если мы имеем дело с планированием в многопроцессорной системе, с числом процессоров Kп >= 1, то здесь возможны два случая:
1. Если Кп >= l, то максимальное время выполнения m-ого этапа определяется как:
TIM(um) = max TIM(ti), i=1,2,...l,
2. Если Кп < l, то требуется решить известную [6,7] задачу распределения l задач по Кп ресурсам с критерием минимальности времени и это минимальное время принять за время выполнения этапа (обозначим его также TIM(um)).
Если все k этапов известны, то реализация проектной задачи потребует.
TIM(ui), i=1,2,...,k.
Здесь считаем, что существенных изменений в весах дуг не имеется, если TIM(tj) << TIM(ui) - TIM(tj) - мало, где tj отбрасываемые методом "обратной волны" переходы из весов w(ui).
TIM - в общем виде зависит как от типа модуля, так и от размерности решаемой задачи. Процедура транспонирования матрицы выполняется за (n-1)n/2 шагов, где n - размерность матрицы.
Таким образом, аналогично функции MEM(pi), функции TIM можно поставить в соответствие вычисляемые процедуры, либо хранить как параметры некоторых функций. Аргументом будет являться размерность задачи.
Для вычислительных процедур при проектировании существенным априорным критерием является точность.
Если считать, что на каждом этапе, каждый модуль
t1,t2,...,tl дает ошибку , ,..., , то можно построить вектор ошибок =( , ,..., ), а в качестве ошибки этапа принять величину:
Em = !! !!x, где m - номер этапа, x - вид нормы.
Ошибку всего проекта можно посчитать как норму вектора:
E=(E1,E2,...,Ek), где Ei i=1,2,...,k-ошибка i-го из k этапов: важно, чтобы задача сводилась к задаче поиска кратчайшего пути (см.[32])
ОШИБКА = !!Е!!x
Считаем, что существенных изменений в весах дуг не имеется, если
<< Em, где - точность отбрасываемого модуля ti
Аналогичным образом точность зависит от метода и размерности решаемой задачи. Эти зависимости могут быть представлены тем же способом, в зависимости от аргумента - размерность задачи - n.
По каждому из рассмотренных критериев можно поставить и решить оптимизационную задачу.
По критерию память:
J1 = max MEM(vm) , m=1,2,...,k
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.