Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
Seminar 1
| Т е о р е м а [2]. Существует специальная индексация гиперинтерва-
лов D i , полученных при генерировании АДК на текущей итерации алгоритма, позволяющая по индексу гиперинтервала D i находить координаты его вершин a(i) и b(i), в которых вычисляется f(x). Информация о функции в конкретной вершине вычисляется только один раз, а затем просто считывается из некоторой базы данных, при- чем метод в состоянии определить, была ли f(x) уже вычислена в вер- шинах, сгенерированных на текущей итерации. Так как каждая точка испытания f(x) может принадлежать различным (до 2 N ) гиперинтерва- лам, то может возникнуть необходимость считывать 2 N раз одну и ту же информацию о значении функции. Поэтому правильная организа- ция данных в связи с фактом существования индексации гиперинтер- валов позволяет существенно повысить эффективность процедуры поиска. Возможно построение различных структур данных для реализации АДК. Например, будем хранить информацию в специализированной базе данных, структура которой приведена на рисунке 1. Координаты вершин X и соответствующая им информация F(X) (значения функции, градиента и др.) хранятся в записях v i массива вершин. Записи массива вершин образуют (при помощи 2N указателей) двунаправленные линейные списки, каждый из которых 79 соответствует одной из N координат. Информация о гиперинтервалах (значение характеристик R i , описательная информация INFO i ) организуется в виде линейного списка, элементы которого соответствуют данным о каждом из существующих на текущей итерации алгоритма гиперинтервалов. В таком случае гиперинтервалы D i из списка содержат только указатели A i и B i на записи из массива вершин и не дублируют информацию о вершинах a(i) и b(i). Например, подобласти с индексами i и k (см. рис.) имеют общую вершину b(i)=b(k): информация о ней хранится в единственной записи v 2 массива вершин, на которую установлены указатели B i и B k соответствующих элементов i и k списка гиперинтервалов. Рис.1. Структура специализированной базы данных Для обеспечения быстрого доступа к данным необходима эффек- тивная реализация операции вставки новых элементов в список гипе- ринтервалов с соответствующей настройкой указателей и операции поиска информации о вершинах. Предлагаемая структура данных в связи с процедурой построения АДК отвечает данному требованию. При параллельной реализации методов [4,5], использующих АДК, на каждой итерации значения характеристик R i упорядочиваются по невозрастанию и испытания f(x) проводятся одновременно в нескольких гиперинтервалах с наибольшими значениями характе- 80 ристик, что соответствует одновременному подразбиению АДК в пре- делах данных гиперинтервалов. Предлагаемая структура данных эффективна также при использовании параллельных методов глобальной оптимизации. жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|