Исследование методов решения линейных уравнений
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?ь подлежит исследованию. Если, пройдя по новому пути, получим значение длины меньше 27, то это новое значение следует взять в качестве новой оценки. Итак, мы прошли по дереву вариантов до вершины и длину одного их путей используем для последующей оценки вариантов.
Возвращаемся теперь по дереву вверх до ближайшего узла (12). Не рассмотренная ветвь дерева () имеет нижнюю оценку 30, что хуже достигнутого результата. Значит, эту ветвь можно далее не исследовать. Переходим к ветви (). Оценка для этой ветви ниже 27, поэтому данное множество следует рассмотреть.
В результате исследования придем к результату, что оптимальный путь (123541).
Сравним теперь данный метод с динамическим программированием. В ДП на очередном шаге выбирается самый короткий путь, ведущий в данную точку; все остальные пути исключаются из дальнейшего рассмотрения. В МВГ при разбиении также рассматривается самый короткий путь, содержащий переход (ij) и множество остальных путей (). Но, в отличии от ДП, мы не может множество (ij) исключить из дальнейшего рассмотрения. В процессе последовательного разбиения, двигаясь от корня к одной из вершин, необходимо запомнить в каждом из узлов информацию для последующего анализа множества возможных путей при возврате от вершины к корню дерева. Следует отметить, что МВГ весьма экономичен с точки зрения требуемой памяти. Если решение задачи метод ветвей и границ прервать (например, по истечении отведенного времени), то хотя оптимальное решение не будет достигнуто, в памяти будет храниться одно из возможных решений. В динамическом программировании решение получается только на последнем шаге вычислительного процесса (оно же и оптимальное).
Из изложенного следует сделать вывод, что МВГ - весьма эффективный метод, с помощью которого можно решать разнообразные задачи с аддитивной целевой функцией.
Листинг программы
var
Way:TVector;
LengthOfWay:real;:boolean;Addiction(var Matrix:Tarray;SizeOfMatrix:integer):real;,MinInCol:real;,j:integer;,d2,d:real;MinElInRow(NumRow:integer):real;:integer;:real;:integer;:=0;min:=1e38;i:=1 to SizeOfMatrix do(Matrix[NumRow,i]BestColumn) and (Matrix[RowOfBasis,i]<min1) then
min1:=Matrix[RowOfBasis,i];:=1e38;
RowOfBasis)and(Matrix[i,BestColumn]=LowLimit2 theni:=1 to SizeOfMatrix doRound(Matrix[i,0])=Basis then:=i;;i:=1 to SizeOfMatrix doRound(Matrix[0,i])=NextPoint then:=i;;[Row,Column]:=1e38;(Matrix,SizeOfMatrix);:=LowLimit2LengthOfBestWay<=LowLimit2;(Way.CountOfPoints);raise Error;:=1e38;.CountOfPoints:=1;.Points[1]:=1;:=;:=Addiction(MatrixOfLinking,n);:=false;(MatrixOfLinking,n,1,d0)
end;.
Метод первого порядка
В этом методе Xk+1=Xk-hkf(Xk). Очередная точка выбирается в направлении скорейшего убывания функции. Шаг hk должен выбираться достаточно малым, чтоб выполнялось f(Xk+1)< f(Xk)(рис 3).
Рис.3 Рис.4
Величина шага должна уменьшаться по мере приближения к X0. тогда у нас происходит дробление шага. Шаг hk выбирают так, чтоб выполнялось неравенство
f(Xk+1) - f(Xk) ? - ? hk// f(Xk)//2
где 0 < ? < 1 - произвольно выбранная константа.
На очередном шаге процесса проверяется неравенство. Если оно выполнено - шаг сохраняется, если нет - шаг уменьшается так, чтобы выполнилось неравенство. Геометрическая интерпретация представлена на рис.4. траектория движения аппроксимирует ломаной линией градиентную кривую, проходящую через точки X0 и X0. Если выбрана постоянная величина шага, то количество итераций, которое необходимо выполнить, может оказаться очень большим.
Разновидностью является метод покоординатного спуска (рис.5). Движение к X0 осуществляется по отрезкам прямых, ?/p>