|
108 где через обозначен вектор, которому соответствует значение функционала 6. к к + 1,г = если е < R, то к п.2. 7.Если e=R, то за решение задачи принимается вектор А*'7. Таким образом, работа алгоритма сводится к последовательной замене единичной компоненты найденного решения (вектора А*) на нулевую, при этом случайным образом выбранной нулевой компоненте присваивается единичное значение (вектор А^+;). Целенаправленность в работе алгоритма получена за счет возврата к предыдущему вектору (А*) при неудачной замене компонент. В заключении данной части хочется отметить, что из всех рассмотренных методов и подходов для решения задач данного класса и такой размерности, как решаемая здесь задача, наиболее приемлемыми являются эвристические алгоритмы. Кроме того, эвристический алгоритм определяется как алгоритм со следующими “удобными” для нас свойствами: 1.Он обычно находит хорошее, хотя не обязательно оптимальное решение. 2.Его можно быстрее и проще реализовать чем любой известный точный алгоритм (то есть тот, который гарантирует оптимальное решение). Понятие “хороший” и “обычно” в первом свойстве меняются от задачи к задаче. Поэтому если для решения задачи все известные точные алгоритмы требуют непозволительно больших затрат машинного времени, то мы можем охотно принять любое нетривиальное приближенное решение, которое может бьггь получено за разумное время. С другой стороны, уже имея быстрое, близкое к оптимальному решение, мы можем стремиться все же к точному решению. 3.2.3. Понятие полного построения алгоритма При дальнейшем рассмотрении будем руководствоваться идеями, изложенными в [14]. Определим алгоритм, как однозначно трактуемую процедуру решения задачи Процедура это конечная последовательность точно определенных шагов или операций, для выполнения каждой из которых требуется конечный объем оперативной памяти и конечное время. Дополнительно потребуем, чтобы алгоритм работал конечное время для любых входных данных. Основными этапами полного построения алгоритма являются: 1.Постановка задачи 2. Построение модели. |
3. Вычисляются %(Хг), i = I,г. 4. Определяется лучшее значение функционала Хк mini=i^x(X’), если I = 0; mini=:T7(xfc-i,x(A^)), если I > 0. 5. I = 1 + 1, е — Е[1/т] (здесь через 2£[си] обозначена целая часть числа). { 0, если Xj = 1 С Хк, j — I — е; 1, если Xj = 1 С Хк, j I — е; 1/(п — т), если Xj = 1 С Хк, где через Хк обозначен вектор, которому соответствует значение функционала хк6. к — к + 1, г — 1 и, если е < R, то к п.2. 7. Если е = R, то за решение задачи принимается вектор Хк~г. Таким образом, работа алгоритма сводится к последовательной замене единичной компоненты найденного решения (вектора Хк) на нулевую, при этом случайным образом выбранной нулевой компоненте присваивается единичное значение (вектор А/;+1 ). Целенаправленность в работе алгоритма получена за счет возврата к предыдущему вектору (Хк) при неудачной замене компонент. Реализация условия пункта 4 алгоритма при специфике пространства булевых переменных придает алгоритму глобальный характер. Итак, предложенные для решения моделей алгоритмы МСПА и СПВ позволяют получить первоначальное решение задачи. Для уточнения решения перейдем к рассмотрению регулярных процедур. По сравнению с первоначальным вариантом [102] анализируемые далее алгоритмы пришлось несколько модифицировать. Дело в том, что возможно отображение уровня 0„(0, ...,0) С Вп в Вп. Обозначим вновь полученное пространство Вп. Для него характерно: 1) V А,У G В'п : p(X,Y) = 2k, к = 1,..., Е[п/2] , где £[а] — целая часть числа а, р(Х, У) — метрика Хемминга; 2) cardBn < cardBnДля пространства Вп справедливы практически все свойства Вп, использованные нами ранее при построении алгоритмов (естественно с учетом сделанного выше замечания). Поэтому, модифицировав алгоритмические модули регулярных процедур на движение по точкам В'п, сможем 159 |