Материал: Алгоритмы пособие
Схемы алгоритмов выбора шага спуска(λ) выбирается в зависимости от используемого метода (рис.2.7-2, рис.2.7-3).
Рис. 2.7-2. Выбор шага в методе ГДШ В методе градиентного спуска с дроблением шага выбор шага спуска
осуществляется следующим образом.
Начальный шаг спуска 0, как правило, задается равным 0,5. На каждой k-й итерации для выбора шага kпроизводится проверка условия:
|
|
|
) Q(x |
|
λ |
p |
|
|
λ |
s |
) |
λ |
|
2 |
s |
2 |
|
Q(x |
,y |
|
|
,y |
|
k |
(p |
). |
|||||||||
k |
k |
k |
|
|
|
||||||||||||
k |
|
|
k |
k |
|
k |
k |
|
2 |
k |
k |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
где p |
Q(x,y) x xk |
s |
|
Q(x,y) x xk |
||
|
|
|
|
|||
k |
x |
y yk |
k |
|
y |
y yk . |
|
|
|
||||
|
|
|
|
|
41 |
|
Если условие выбора шага не выполняется, то шаг полагается равнымk = k/2 и проверка условия возобновляется. При выполнении условия выбора шага его значение передается в процедуру вычисления координат очередной точки спуска.
В методах наискорейшего спуска из выбранной точки (x0,y0) спуск осуществляют в направлении антиградиента до тех пор, пока не будет достигнуто минимальное значение целевой функции Q(x, y) вдоль луча, направление которого определяет вектор антиградиент.
Если выразить целевую функцию Q(x, y) через шаг , то на определенном шаге, при фиксированных значенияхxи y, целевую функцию можно представить как функцию одной переменной:
(λ) Q(x |
k |
λ |
p |
,y |
k |
λ |
s |
). |
|
k |
k |
|
k |
k |
|
Величина шага на каждой итерации определяется из условия минимума функции (λ) :
(λ*)
= min(
( ))
k = *(xk, yk), |
>0. |
Таким образом, выбор шага k на каждой итерации предполагает решение задачи одномерной оптимизации. По способу решения этой задачи различают два метода наискорейшего спуска [3]:
-аналитический метод (НСА);
-численный метод (НСЧ).
В методе НСА[3] формулу для вычисления значения текущего шага спуска получают аналитически перед компьютерной реализацией алгоритма
из условия |
'(λ) 0 . |
В методе НСЧ величину k находят на отрезке [0;1] c заданной точностью, используя один из методов одномерной оптимизации, например, метода золотого сечения (рис. 2.7-3). В качестве целевой функции
используется |
(λ) |
. |
|
|
42
Рис. 2.7-3. Выбор шага в методе НСЧ методом золотого сечения
43
3. Создание схем алгоритмов с использованием графического редактора MS Visio
3.1.Назначение MS Visio
Основным назначением графического редактора MSVisio является визуализация данных: создание схем алгоритмов, иллюстраций и диаграмм и др.Далее будут рассмотрены в основном только те возможности Visio, которые необходимы для создания схем алгоритмов вычислительных задач.
Процесс оформления схем алгоритмов достаточно прост. В Visio имеется большое количество готовых элементов, называемых«фигурами» или как в нашем случае блоками. Каждый из блоков имеет свое назначение. С помощью мыши эти элементы можно переносить в нужные места на рабочий лист. Затем выбранные блоки соединяются линиями, указывающими связи между ними(или ход выполнения алгоритма), и снабжаются поясняющими надписями. Готовую схему можно использовать как самостоятельный документ или поместить в качестве рисунка (иллюстрации) в документ, подготовленный в другом приложении.
Так как Visio является составной частью MS Office, то большинство кнопок, команд и инструментов имеют одинаковый смысл, а назначение кнопок и элементов меню, являющимися специфическими для Visio комментируются всплывающими пояснениями.
К сожалению Visio не обладает функциональными средствами редактора формул, поэтому при необходимости включения формул в блоки формируемой схемы алгоритма рекомендуется использовать встроенный редактор формул MS Word.
3.2.Создание документа, открытие и сохранение файлов
После запуска Visio на экране появиться окно, представленное на рис. 3.2-1. Расположение элементов этого окна очень похоже на другие приложения MSOffice. В верхней части окна под основным меню находятся различные панели инструментов и другие элементы, которые существенно ускоряют доступ к функциональным возможностям приложения, с которыми познакомимся по мере необходимости.
В центральной части окна можно увидеть большую стрелкусообщение, указывающую на список категорий шаблонов документов, расположенный в левой части окна. В этом списке перечислены основные категории шаблонов документов, с которыми способно работать Visio. Выбор категории шаблона осуществляется щелчком по нужному пункту списка, после чего нужно уточнить свой выбор, щелкнув по одному из шаблонов, расположенных в центральной части окна (рис. 3.2-1).
44
В зависимости от выбранной категории шаблонов, Visio подготовит к использованию тот или иной набор базовых элементов (фигур, блоков) для сборки схемы, чертежа или рисунка:
Бизнес
Блок-схема
Карты и планы этажей
Общие
Программное обеспечение и базы данных
Расписание
Сеть
Техника
Рис 3.2-1. |
Окно MS Visio сразу после запуска программы |
Выбрав |
нужный шаблон, следует нажать кнопкуСоздать |
(рис. 3.2-2).
45