Cтраница 4
Чистка дерева, т.е. удаление информации об отсеянных вершинах, выполняется при невозможности записи информации о новых вершинах дерева, появляющихся в процессе решения задачи. При просмотре информации о вершинах отсеянные вершины отмечаются, но информация о них не удаляется. Процедура удаления информации о вершинах требует большой вычислительной работы, связанной с перестройкой системы указателей и ссылок; поэтому эта процедура выполняется лишь в крайнем случае - при невозможности записи информации об очередной группе новых вершин. В процессе чистки удаляется информация как об отсеянных вершинах, так и о таких, все подвешенные вершины к которым отсеяны. Это достигается с помощью просмотра информации о дереве от концевых вершин вверх по путям, ведущим к корневой вершине. В процессе такого просмотра отмечаются все удаляемые вершины; после удаления информации о них список оставшихся вершин сжимается вверх, перестраивается система указателей и ссылок и процесс решения задачи продолжается. [46]
В этой связи наиболее перспективными представляются методы, которые удачно сочетают в себе элементы детерминистических и стохастических методов поиска. Один из них - комплекс-метод - является модификацией симплексного метода и сохраняет его основную идею. В комплекс-методе используется N - - P вершин ( Р 0), каждая из которых должна удовлетворять ограничениям всех k этапов. В допустимой области факторного пространства эти вершины формируются случайным образом. Затем в каждой вершине комплекса вычисляется значение целевой функции. Вершина, в которой f ( x) имеет наихудшее значение, заменяется новой вершиной, находящейся на прямой, проходящей через отброшенную точку. Центр тяжести оставшихся вершин комплекса расположен на расстоянии, равном или большем, чем расстояние от отброшенной точки до центра тяжести. Если окажется, что в новой вершине - наихудшее значение по сравнению со всеми вершинами в новом комплексе, то новая вершина формируется на половине расстояния от худшей точки к лучшей вершине комплекса. При удачном движении происходит расширение комплекса с деформацией его в сторону экстремума. Процесс поиска продолжается до тех пор, пока комплекс не будет стянут в центр тяжести в пределах заданной точности. Метод позволяет успешно решать многоэкстремальные задачи. [47]
В этой связи наиболее перспективными представляются методы, которые удачно сочетают в себе элементы детерминистических и стохастических методов поиска. Один из них - комплекс-метод - является модификацией симплексного метода и сохраняет его основную идею. В комплекс-методе используется N Р вершин ( Р О), каждая из которых должна удовлетворять ограничениям всех k этапов. В допустимой области факторного пространства эти вершины формируются случайным образом. Затем в каждой вершине комплекса вычисляется значение целевой функции. Вершина, в которой Дх) имеет наихудшее значение, заменяется новой вершиной, находящейся на прямой, проходящей через отброшенную точку. Центр тяжести оставшихся вершин комплекса расположен на расстоянии, равном или большем, чем расстояние от отброшенной точки до центра тяжести. Если окажется, что в новой вершине - наихудшее значение по сравнению со всеми вершинами в новом комплексе, то новая вершина формируется на половине расстояния от худшей точки к лучшей вершине комплекса. При удачном движении происходит расширение комплекса с деформацией его в сторону экстремума. Процесс поиска продолжается до тех пор, пока комплекс не будет стянут в центр тяжести в пределах заданной точности. Метод позволяет успешно решать многоэкстремальные задачи. [48]
Так как поле в воздушном зазоре при удалении от кромки полюса к его середине равномерно, линию потока AG можно принять удаленной в бесконечность. Таким образом, две пары сторон многоугольника AGFDCB уходят в бесконечность. Сложная конфигурация границ исследуемой области поля не позволяет сразу найти функцию, описывающую это поле в осях х, у. С с координатой zc j принимаем соответственной точку с с. Координату одной из двух оставшихся вершин можно выбрать на оси плоскости t также произвольно. Неизвестную координату вершины В на плоскости t обозначаем через Ь; в дальнейшем она будет определена через геометрические параметры области. [49]
Рассмотрим алгоритм трассировки соединений, заданных матрицей контактов Т, описанной в гл. По матрице контактов составляется список 5 ( k l) цепей, где k - номер цепи, а / - число контактов в цепи. Задача заключается в соединении контактов каждой цепи деревом минимальной длины. С этой целью из списка цепей S ( k l) выбирается k - я цепь. От произвольной вершины ( контакта) этой цепи распространяется волна в соответствии с алгоритмом Ли, в результате чего данная точка соединяется кратчайшей трассой с ближайшей вершиной ( контактом) данной цепи. Для того чтобы построенный фрагмент соединить кратчайшим путем с ближайшим контактом цепи, поступаем следующим образом. Поочередно от всех вершин цепи, не принадлежащих построенному фрагменту дерева, распространяем волну до достижения фрагмента. Выбираем ту вершину, волна от которой достигает фрагмента наиболее быстро. Строим трассу и присоединяем ее к фрагменту. С оставшимися вершинами цепи поступаем аналогично до тех пор, пока все вершины цепи не будут соединены трассой. [50]