Что такое разветвляющийся алгоритм приведите примеры: Типы алгоритмов: линейные, разветвляющиеся, циклические – методическая разработка для учителей, Елеусизова Айнаш Досымхановна

линейные, разветвляющиеся, циклические. Способы описания алгоритмов

Известны три типа алгоритмов – линейные,
разветвляющиеся, циклические.

Линейный тип алгоритмов

Алгоритмы, в которых команды выполняются
друг за другом, независимо от каких-либо
условий, называются алгоритмами линейного
типа.

Например, алгоритм вычисления по самым
простейшим формулам, не имеющих
ограничений на значения входящих в них
переменных.

Пример

Постановка задачи

:
вычислить
площадь круга, если известен радиус.

Дано:
R– радиус круга.

Найти: S– площадь круга.

Решение: S=3,14R 2

Словесная форма записи алгоритма

Выберем русский язык для записи алгоритма
в этой форме и запишем последовательность
команд, выполнение которых при заданном
значении радиуса позволит найти площадь:

Прочесть
значение R.

Умножить
значение Rна 3,14.

Умножить
результат второго действия на значение
R.

Записать
полученный результат как значение S.

На языке блок-схем


– рис. 8

Разветвляющийся тип алгоритмов

Решение задач не всегда можно представить
в виде линейного алгоритма.

Алгоритмы, в которых требуется организовать
выбор последовательности действий в
зависимости от каких-либо условий,
называют алгоритмами разветвляющегося
типа.

При графическом способе ветвление
организуется с помощью логического
элемента (ромб), имеющего один вход и
два выхода. Назначение логического
элемента – проверка заданного условия.
В зависимости от выполнения (истинности)
или невыполнения (ложности) проверяемого
условия возможен выход соответственно
на ветвь «Да» или «Нет».

Пример

Постановка задачи

: вычислить

.

Дано
: х – значение аргумента.

Найти
: у – значение функции.

Решение:

y= x ,
если х  0

— x , если х

Блок-схема

— см. рис. 9.

Словесное представление

На псевдокоде

:

Прочесть значение х

Если х>0, то

Конец ветвления

Записать значение у

Выделяют полную и неполную условную
конструкцию

.

Циклический тип алгоритмов

При составлении алгоритмов решения
достаточно большого круга задач нередко
возникает потребность в неоднократном
повторении одних и тех же команд.

Алгоритм, составленный с использованием
многократных повторений одних и тех же
действий (циклов), называется алгоритмов
циклического типа
.

Однако, «неоднократно» не значит «до
бесконечности». Организация циклов,
никогда не приводящая к остановке в
выполнении алгоритма (так называемое
зацикливание), является нарушением
требования его результативности.

При разработке алгоритма циклической
структуры выделяют следующие понятия:

параметр цикла

– величина, с
изменением которой связано многократное
выполнение цикла;

начальное и конечное значение
параметра

цикла

;

шаг цикла

– это значение, на
которое изменяется параметр цикла при
каждом повторении.

Циклический алгоритм состоит из
подготовки цикла, тела цикла,
условия продолжения цикла

.

В подготовку цикла

входят
действия, связанные с заданием исходных
значений для параметра цикла (начальное
и конечное значения, шаг параметра).

В тело цикла

входят: многократно
повторяющиеся действия для вычисления
искомых величин; подготовка следующего
значения параметра цикла, подготовка
других значений, необходимых для
повторного выполнения действий в теле
цикла.

В условии продолжения

определяется
необходимость дальнейшего выполнения
повторяющихся действий. Если параметр
цикла превысил конечное значение, то
выполнение цикла должно быть прекращено.

Рассмотрим графическое представление
циклического блока алгоритма (см. рис.
10).

Циклы могут быть с предусловием
(когда условие проверяется перед началом
тела цикла) и спостусловием
(когда
условие проверяется после первого
прохождения тела цикла).

Цикл
с постусловием

Цикл
с предусловием

В рамках структурного программирования задачи, имеющие алгоритмическое решение, могут быть описаны с использованием следующих алгоритмических структур:

• Следование
  . Предполагает последовательное выполнение команд сверху вниз. Если алгоритм состоит только из структур следования, то он является линейным.
• Ветвление
  . Выполнение программы идет по одной из двух, нескольких или множества ветвей. Выбор ветви зависит от условия на входе ветвления и поступивших сюда данных.
• Цикл
  . Предполагает возможность многократного повторения определенных действий. Количество повторений зависит от условия цикла.
• Функция (подпрограмма)
  . Команды, отделенные от основной программы, выполняются лишь в случае их вызова из основной программы (из любого ее места). Одна и та же функция может вызываться из основной программы сколь угодно раз.

Описание различных алгоритмических структур на языке блок-схем

Ветвление if

Это самый простой тип ветвления. Если результат вычисления выражения-условия возвращает true (правда), то выполнение алгоритма идет по ветке «Да», в которую включены дополнительные выражения-действия. Если условие возвращает false (ложь), то выполнение алгоритма идет по ветке «нет», т.е продолжает выполняться основная ветка программы.

Ветвление if-else

Если выражение-условие возвращает true (правда), то выполнение алгоритма идет по ветке «Да», если условие не выполняется (false), то выполнение идет по ветке «Нет». При любом результате выражения-условия нельзя вернуться в основную ветку программы, минуя дополнительные действия.

Ветвление if-elif-else

Количество условий может быть различно. Если выполняется первое, то после выполнения действий, программа переходит к основной ветке, не проверяя дальнейшие условия. Если первое условие возвращает ложь, то проверяется второе условие. Если второе условие возвращает правду, то выполняются действия, включенные в вторую ветку конструкции. Последнее условие проверяется лишь в том случае, если ни одно до него не дало в результате true. Данную алгоритмическую конструкцию (if – elif – else) не следует путать с алгоритмической конструкцией «Выбор».

Цикл while

Пока условие выполняется (результат логического выражения дает true), будут выполняться действия тела цикла. После очередного выполнения вложенных действий условие снова проверяется. Для того чтобы выполнение алгоритма не зациклилось, в теле цикла (помимо прочих действий) должно быть выражение, в результате выполнения которого будет изменяться переменная, используемая в условии. Тело цикла может ни разу не выполнится, если условие с самого начала давало false.

Цикл do

В этом цикле первый раз условие проверяется лишь после выполнения действий тела цикла. Если условие возвращает true, то выражения-действия повторяются снова. Каким бы ни было условие, тело данного цикла хотя бы раз, но выполнится.

Цикл for

Данный цикл также называют циклом «Для» (for). В его заголовке указывается три параметра: начальное значение переменной (от), конечно значение (до) и ее изменение с помощью арифметической операции на каждом «обороте» цикла (шаг).

>> Типы алгоритмов

В алгоритмах команды записываются друг за другом в определенном порядке. Выполняются они не обязательно в записанной последовательности: в зависимости от порядка выполнения команд можно выделить три типа алгоритмов:

Линейные алгоритмы;
алгоритмы с ветвлениями;
алгоритмы с повторениями.

Линейные алгоритмы

В котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным.

Например, линейным является следующий алгоритм посадки дерева:

1) выкопать в земле ямку;
2) опустить в ямку саженец;
3) засыпать ямку с саженцем землей;
4) полить саженец водой.

С помощью блок-схемы данный алгоритм можно изобразить так:

Алгоритмы о ветвлениями

Ситуации, когда заранее известна последовательность требуемых действий, встречаются крайне редко. В жизни часто приходится принимать решение в зависимости от сложившейся обстановки. Если идет дождь, мы берем зонт и надеваем плащ; если жарко, надеваем легкую одежду. Встречаются и более сложные условия выбора. В некоторых случаях от выбранного решения зависит дальнейшая судьба человека.

Логику принятия решения можно описать так:

ЕСЛИ ТО ИНАЧЕ

Примеры:

ЕСЛИ хочешь бытьздоров
, ТО закаляйся, ИНАЧЕ валяйся весь день на диване;
ЕСЛИ низко ласточки летают, ТО будет дождь, ИНАЧЕ дождя не будет;
ЕСЛИ уроки выучены, ТО иди гулять, ИНАЧЕ учи уроки.

В некоторых случаях могут отсутствовать;

ЕСЛИ ТО

Пример
:

ЕСЛИ назвался груздем, ТО полезай в кузов.

Форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность
шагов, называется ветвлением.

Изобразим в виде блок-схемы последовательность действий ученика 6 класса Мухина Васи, которую он представляет себе так: «Если Павлик дома, будем решать задачи по математике. В противном случае следует позвонить Марине и вместе готовить доклад по биологии. Если же Марины нет дома, то надо сесть за сочинение.»

А вот так, с помощью блок-схемы можно очень наглядно представить рассуждения при решении следующей задачи.

Из трёх монет одинакового достоинства одна фальшивая (более легкая). Как ее найти с помощью одного взвешивания на чашечных весах без гирь?

Алгоритмы с повторениями

На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие.

Алгоритм, содержащий циклы
, называется циклическим алгоритмом или алгоритмом с повторениями.

Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием. Следует разрабатывать алгоритмы, не допускающие таких ситуаций.

Рассмотрим пример из математики.

Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число1.

2, 3, 5, 7 — простые числа; 4, 6, 8 — нет. В III веке до нашей эры греческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых чисел, меньших заданного числа n:

1) выписать все натуральные числа от 1 до n;
2) вычеркнуть 1;
3) подчеркнуть наименьшее из неотмеченных чисел;
4) вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге;
5) если в списке имеются неотмеченные числа, то перейти к шагу 3, в противном случае все подчеркнутые числа — простые.

Это циклический алгоритм. При его выполнении повторение шагов 3-5 происходит, пока в исходном списке остаются неотмеченные числа.

Вот так выглядит блок-схема действий школьника, которому перед вечерней прогулкой следует выполнить домашнее задание по математике:

Напомним, что число 1 не относят ни к составным (имеющим более двух делителей), ни к простым числам.

Самое главное

В зависимости от порядка выполнения команд можно выделить три типа алгоритмов:

> линейные алгоритмы;
> алгоритмы с ветвлениями;
> алгоритмы с повторениями.

Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным.

Форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов, называется ветвлением.

Форма организации действий, при которой выполнение одной и той же последовательности команд повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением).

Вопросы и задания

1. Какие алгоритмы называют линейными?
2. Приведите пример линейного алгоритма,
3. Исполнитель «Вычислитель» умеет выполнять только две команды: умножать на 2 и прибавлять Придумайте для него наиболее короткий план получения из О числа 50.
4. Какая форма организации действий называется ветвлением?
5. Какие условия должна была выполнить героиня скази «Гуси-лебеди»?
6. Приведите пример алгоритма, содержащего ветвление»
7. Прочитайте отрывок из стихотворения Дж. Родари «Чем пахнут ремесла?»:

У каждого дела запах особый:
В булочной пахнет тестом и сдобой.
Мимо столярной идешь мастерской —
Стружкою пахнет и свежей доской.
Пахнет маляр скипидаром и краской.
Пахнет стекольщик оконной замазкой.
Куртка шофера пахнет бензином,
Блуза рабочего — маслом машинным.

Перефразируйте
о профессиях с помощью слов «ЕСЛИ… ТО»/

8. Вспомните, герои каких русских народных сказок совершают выбор, определяющий их судьбу.
9. Из 9 монет одинакового достоинства одна фальшивая (более легкая). За сколько взвешиваний на чашечных весах без гирь вы можете ее определить?
10. Какая форма организации действий называется повторением?
11. Приведите пример алгоритма, содержащего повторение.
12. В каких известных вам литературных произведениях имеет место циклическая форма организации действий?
13. Где окажется исполнитель, выполнивший 16 раз подряд следующую группу команд?

пройти 10 метров вперед

повернуть на 90° по часовой стрелке

14. Какую группу действий и сколько раз следует повторить при решении следующей задачи?

Сорок солдат подошли к реке, по которой на лодке катаются двое мальчиков. Как солдатам переправиться на другой берег, если лодка вмещает только одного солдата либо двух мальчиков, а солдата и мальчика уже не вмещает?

15. Вспомните задачу о Вычислителе, умеющем только умножать на 2 и прибавлять 1. Разрабатывать для него рациональные алгоритмы будет значительно проще, если воспользоваться следующей блок-схемой:

Используя эту блок-схему, разработайте рациональные алгоритмы получения из числа 0 чисел 1024 и 500.

Босова Л. Л. Информатика: Учебник для 6 класса / Л. Л. Босова. — 3-е изд., испр. и доп. — М.: БИНОМ. Лаборатория знаний, 2005. — 208 с.: ил.

Содержание урока


конспект урока и опорный каркас
презентация урока
интерактивные технологии
акселеративные методы обучения
Практика


тесты, тестирование онлайн
задачи и упражнения
домашние задания
практикумы и тренинги
вопросы для дискуссий в классе
Иллюстрации


видео- и аудиоматериалы
фотографии, картинки
графики, таблицы, схемы
комиксы, притчи, поговорки, кроссворды, анекдоты, приколы, цитаты
Дополнения


рефераты
шпаргалки
фишки для любознательных
статьи (МАН)
литература основная и дополнительная
словарь терминов

Совершенствование учебников и уроков


исправление ошибок в учебнике
замена устаревших знаний новыми
Только для учителей


календарные планы
учебные программы
методические рекомендации

Для записи алгоритмов, наряду с естественным или математическим языком, удобно использовать язык блок-схем. Блок-схемой называется графическое изображение алгоритма, в котором каждый этап процесса обработки данных изображён в виде геометрической фигуры установленного вида, называемой символом. Символы соединяются линиями, указывающими направление потоков информации. Внутри каждого символа помещается описание соответствующего этапа обработки данных. Если описание громоздко, оно записывается отдельно в виде комментария. Основные символы приведены в таблице.

Символы соединяются линиями связи. В месте слияния символов ставится точка. Символы могут иметь номера для удобства показа соединений в местах разрыва схемы. Эти номера не определяют порядок выполнения алгоритма, зависящий только от соединяющих потоки линий.

Все алгоритмы по своей структуре делятся на
три группы:

Линейные;

Разветвляющиеся;

Циклические.

Линейным называется алгоритм, не содержащий условий. Этот алгоритм безусловно определяет процесс преобразования данных. Примером такого алгоритма является поэтапное вычисление математической формулы. Каждая элементарная операция выполняется в установленном правилами вычислений порядке без анализа полученного ранее результата. Блок-схема линейного алгоритма представляет собой последовательную цепочку символов «процесс»
, имеющих вид прямоугольника, дополненную символами «ввод-вывод»
и «начало-конец».

Рис. 8. Блок-схема линейного алгоритма

Разветвляющийся алгоритм
содержит, по крайней мере, одно условие. Для реализации разветвляющегося алгоритма используется типовая структура РАЗВЕТВЛЕНИЕ. Основой разветвляющегося алгоритма является логический элемент условия, изображаемый на схеме символом РОМБ. В логическом элементе производится проверка условия, которая даёт результат ДА или НЕТ. В зависимости от этого поток информации направляется по одному из двух выходных каналов логического элемента.

В таком алгоритме может быть два варианта:

1. Если условие выполняется, то информационный поток направляется в блок вычислительного процесса, для которого проводилась проверка условия; если условие не выполняется — информационный поток направляется к следующим элементам блок-схемы. Таким образом, логическая схема может быть записана как ЕСЛИ (условие) — ТО (формула).

2. Имеется ДВЕ ФОРМУЛЫ вычислений, и алгоритм работает по следующему логическому принципу: ЕСЛИ (условие) — ТО (формула 1), ИНАЧЕ (формула 2).

Если нужно проверить несколько условий, то алгоритм принимает форму «дерева» с разветвлениями в виде «веток». Количество логических элементов всегда на единицу меньше количества условий, т.к. каждый элемент имеет один вход и два выхода. Участок алгоритма до разветвления называется стволом
, условие — точкой разветвления
, альтернативные направления процесса вычисления после точки разветвления — ветвями.

Рис.9. Блок-схемы разветвляющихся алгоритмов

Циклическим называется такой алгоритм, часть действий в котором повторяется неоднократно. Такие повторяющиеся действия и носят название «цикл». Циклические алгоритмы содержат условия работы цикла, поэтому их можно считать разновидностью разветвляющихся алгоритмов, у которой одной из ветвей является часть ствола, которая неоднократно повторяется. Эти повторяющиеся действия и составляют цикл.

Циклические алгоритмы делятся на два вида:

С известным числом повторений (циклов)

Итерационные алгоритмы, в которых число циклов заранее неизвестно и окончание работы цикла определяется каким-либо условием (преимущественно заданной точностью вычислений).

Рассмотрим оба вида алгоритмов.

«Разветвляющийся алгоритм» — Информатика — Уроки

Дата:02.10.2017

Тема урока: «Разветвляющийся алгоритм»

Тип урока: изучение нового материала

Цели урока: расширить знания уч-ся об алгоритме;

Знать: базовую алгоритмическую структуры «Ветвление», полной и неполной формах;

Уметь: решать задачи разветвляющейся структуры на алгоритмическом языке, с помощью блок-схем; строить блок-схемы и делать ее отладку;

— развитие навыков самостоятельной работы уч-ся

Оборудование: презентация «Разветвляющийся алгоритм», -схема», проектор

Ход урока

I. ОРГМОМЕНТ

II. АКТУАЛИЗАЦИЯ ОПОРНЫХ ЗНАНИЙ

1. Практическое задание у доски (1 уч-ся)

Задание : Исправь ошибки.
Найдите площадь прямоугольного треугольника с катетами Х и Y.

АЛГ площадь (цел X , Y, вещ S)

АРГ X

РЕЗ Y

НАЧ

S = X * Y : 2

КОН

2. Фронтальный опрос теории

ВОПРОСЫ: 1) Что такое алгоритм?

2) Дайте определение величины

3) Что называют типом величины?

4) Какие типы величин вам известны?

5) Что такое команда?

6) На какие виды делятся команды?

7) Приведите пример простой команды. Составной команды.

8) В чем основное отличие простой команды от составной?

III. Сообщение темы , цели урока

1. Вступительное слово учителя.

Каждый день, совершая определенные действия, мы выполняем какой-либо алгоритм. Линейный алгоритм: заваривание чая, приготовление бутерброда и т.д.

К сожалению, в жизни линейные алгоритмы встречаются довольно редко. Всегда появляются какие-нибудь условия, которые изменяют алгоритм.

Например: вы умываетесь, чистите зубы и вдруг перестала идти вода или закончилась паста. Утром мы всегда смотрим в окно, наблюдаем за погодой: если идет дождь, то надо взять зонт, если столбик термометра опустился вниз, то нужно одеть куртку. И такие условия встречаются в нашей жизни довольно часто.

Находясь на развилке двух ( и более) дорог, русский богатырь выберет только одну в зависимости от своей цели и некоторого условия, написанного на камне.

Таким образом, появляется новый вид алгоритма, который называется разветвляющимся или проще говоря развилкой.

2. Сообщение темы и цели урока

IV. ИЗУЧЕНИЕ НОВОГО МАТЕРИАЛА

1. Понятие ветвления

Составной называется команда, содержащая условие. Одной из составных команд является команда ветвления

Ветвление — это такая форма организации действий, при которой в зависимости от выполнения (невыполнения) некоторого условия совершается либо одна, либо другая последовательность действий.

Команду ветвления называют также развилкой, так как в зависимости от условия исполнитель выполнит либо одну либо другую команду. (либо пойдет налево или направо)

2. Формы ветвления

Различают полную и неполную формы ветвления.

П

Пояснение: Если условие верно(истинно), то исполнитель выполнит команду серия 1 после служебного слова то.

Если условие неверно (ложно), то исполнитель выполнит команду серия 2 после служебного слова иначе

олное ветвление:

если

то серия 1

иначе серия 2

всё

НАПРИМЕР, найти значение функции У :

Решим задачу с помощью координатной прямой.

Вывод: условием является выражение X

Запись на алгоритмическом языке:

если х

то y := 3*x

иначе y :=1/ x

всё

Полной форме ветвления соответствует следующая блок-схема:

Пояснение:

Если условие верно, то исполнитель пойдет по ветви ДА и выполнит команду серия 1

Если условие неверно, то исполнитель пойдет по ветви НЕТ и выполнит команду серия 2

Н

Пояснение: Если условие верно(истинно), то исполнитель выполнит команду серия 1 после служебного слова то.

Если условие неверно (ложно), то исполнитель выполнит следующую команду алгоритма

еполное ветвление:

если

то серия 1

всё

НАПРИМЕР, y=3*x, при х

Запись на алгоритмическом языке:

если х

то y := 3*x

всё

Неполному ветвлению соответствует блок-схема

Пояснение:

Если условие верно, то исполнитель пойдет по ветви ДА и выполнит команду серия 1

Если условие неверно, то исполнитель пойдет по ветви НЕТ к следующей команде алгоритма

3. Вывод:

Структура «Ветвление» обеспечивает выполнение одной из серий команд в зависимости от результата проверки истинности условия.

4. Определение разветвляющегося алгоритма

В настоящее время существует несколько определений разветвляющегося алгоритма.

ОПРЕДЕЛЕНИЕ1. Алгоритм, содержащий структуру ветвления, называется разветвляющимся

ОПРЕДЕЛЕНИЕ 2. Разветвляющимся называется алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий

IV. ЗАКРЕПЛЕНИЕ ИЗУЧЕННОГО МАТЕРИАЛА

1.Устные задачи

Задача 1. Введено число 15.

Какое значение получится в результате выполнения алгоритма?

ОТВЕТ: 108

Задача 2. Введено число 1.

Какое значение получится в результате выполнения алгоритма?

ОТВЕТ : 40

2. Решение задач

Задача 1. Найдите наибольшее среди двух целых чисел а,b

1. Постановка задачи:

дано: a,b

найти: c

2. Условие задачи: ab

3. Алгоритмическая запись:

алг наибольшее(цел а, b, с)

арг а,b

рез с

нач

если аb

то c := a

иначе c :=b

всё

кон

Задача 2. Найдите значение функции

Постановка задачи:

дано: Х

найти: F

2. Условие задачи: X = 0

3. Алгоритмическая запись:

алг F (вещ x,F)

арг x

рез F

нач

если х0

то F := x*x-3

всё

кон

V. ПРАКТИЧЕСКАЯ ЧАСТЬ

1.Самостоятельная работа

Задание 1. Составить блок-схему к задаче № 1

1. Открыть программу Блок-схема

2. Блок-схема – новая блок-схема- разработка

3. Составление блок-схемы

4. Отладка блок-схемы

5. Запись в тетрадь

Задание 2. Составить блок-схему к задаче №2

2. Проверка самостоятельной работы

VI. ПОДВЕДЕНИЕ ИТОГОВ УРОКА

1.Устное задание:

Найди соответствие

АЛГ наименьшее ( вещ А,В,М)

АРГ А , В

РЕЗ М

НАЧ

ЕСЛИ А

ТО М : = А

ИНАЧЕ М : = В

ВСЕ

КОН

Ответ : схема 2

2. ВОПРОСЫ:

-Какой алгоритм называется разветвляющимся?

— Назовите формы ветвления.

— В чем отличие полного ветвления от неполного?

— В чем сходство?

VII. ДОМАШНЕЕ ЗАДАНИЕ

Ветвление полная и неполная формы

Задача :

4

Введение в метод ветвей и границ. Учебное пособие по структурам данных и алгоритмам

Алгоритмы ветвей и границ используются для нахождения оптимального решения комбинаторных, дискретных и общих задач математической оптимизации.

Алгоритм ветвей и границ обеспечивает оптимальное решение NP-сложной задачи путем исследования всего пространства поиска. Алгоритм ветвей и границ, исследуя все пространство поиска, шаг за шагом определяет возможные варианты решений.

В информатике существует множество задач оптимизации, многие из которых имеют конечное число допустимых кратчайших путей в графе или минимальном остовном дереве, которые можно решить за полиномиальное время. Как правило, эти проблемы требуют наихудшего сценария всех возможных перестановок. Алгоритм ветвей и границ создает ветви и границы для наилучшего решения.

В этом уроке мы подробно обсудим метод ветвей и границ.

Различные методы поиска по ветвям и границам:

Алгоритмы ветвления включают в себя различные методы поиска для обхода дерева пространства состояний. Различные методы поиска, используемые в B&B, перечислены ниже:

1. Поиск LC
2. BFS
3. DFS

1. Поиск LC (Поиск по наименьшей стоимости):

Он использует эвристическую функцию стоимости для вычисления границы значения в каждом узле. Узлы добавляются в список активных узлов сразу после их создания.
Узел с наименьшим значением функции стоимости, выбранный в качестве следующего E-узла.

2.BFS (поиск в ширину):
Также известен как поиск FIFO.
Он поддерживает список активных узлов в порядке «первым поступил — первым обслужен», т. е. в очереди. Активные узлы просматриваются в порядке FIFO, чтобы сделать их следующими E-узлами.

3. DFS (поиск в глубину):
Также известен как поиск LIFO.
Он поддерживает список активных узлов в порядке «последний пришел — первый вышел», т. е. в стеке.

Активные узлы просматриваются в порядке LIFO, чтобы сделать их следующими E-узлами.

Введение в алгоритм ветвей и границ

Когда применять алгоритм ветвей и границ?

Ветви и границы — эффективное решение некоторых проблем, о которых мы уже говорили. В этом разделе мы обсудим все такие случаи, когда ветвление и связывание уместны.

• Метод ветвей и границ целесообразно использовать, если данная задача является дискретной оптимизацией. Дискретная оптимизация относится к задачам, в которых переменные принадлежат дискретному набору. Примеры таких проблем включают целочисленное программирование 0-1 и проблемы с сетевым потоком.
• Когда дело доходит до задач комбинаторной оптимизации, методы ветвления и границы работают хорошо. Задача оптимизации оптимизируется с помощью комбинаторной оптимизации путем нахождения ее максимума или минимума на основе ее целевой функции. Задачи комбинаторной оптимизации включают логическую выполнимость и целочисленное линейное программирование.

Основные понятия ветвей и границ:

▸ Создание дерева пространства состояний:

Как и в случае поиска с возвратом, B&B создает дерево пространства состояний для эффективного поиска в пространстве решений данного экземпляра задачи.

В B&B все потомки E-узла в дереве пространства состояний создаются до того, как какой-либо активный узел преобразуется в E-узел. Таким образом, E-узел остается E-узлом до тех пор, пока i не станет мертвым узлом.

• Оценка решения-кандидата:

В отличие от поиска с возвратом, B&B требует дополнительных факторов для оценки решения-кандидата:

1. Способ присвоения границы наилучших значений заданных критериальных функций каждому узлу в состоянии космическое дерево: создается путем добавления дополнительных компонентов к частичному решению, заданному этим узлом.
2. Наилучшие значения данной целевой функции, полученные на данный момент: Она описывает верхнюю границу для задачи максимизации и нижнюю границу для задачи минимизации.

• Допустимое решение определяется состояниями задачи, которые удовлетворяют всем заданным ограничениям.
• оптимальное решение — это допустимое решение, которое дает наилучшее значение заданной целевой функции.
• Ограничивающая функция:

Оптимизирует поиск вектора решения в пространстве решений данного экземпляра задачи.

Это эвристическая функция, которая оценивает нижнюю и верхнюю границы возможных решений в каждом узле. Связанные значения используются для поиска частичных решений, ведущих к оптимальному решению. Если узел не дает решения лучше, чем лучшее решение, полученное на данный момент, то он отбрасывается без дальнейшего исследования.

Затем алгоритм переходит на другой путь, чтобы получить лучшее решение. Желаемое решение проблемы — это ценность наилучшего решения, полученного на данный момент.

▸ Причины отклонения пути поиска в текущем узле:

(i) Граничное значение узла ниже верхней границы в случае задачи максимизации и выше нижней границы в случай задачи минимизации. (т. е. связанное значение ade не лучше, чем значение наилучшего решения, полученного до этого узла).

(ii) Узел представляет невозможные решения, нарушающие ограничения задачи.

(iii) Узел представляет собой подмножество допустимого решения, содержащего одну точку. В этом случае, если последнее решение лучше, чем лучшее решение, полученное до сих пор, лучшее решение модифицируется до значения допустимого решения в этом узле.

Типы решений о ветвях и границах:

Решение задачи о ветвях и границах может быть представлено двумя способами:

• Решение переменного размера: Используя это решение, мы можем найти подмножество данного множества, которое дает оптимальное решение поставленной задачи. Например, если нам нужно выбрать комбинацию элементов из {А, В, С, D}, оптимизирующую данную задачу, и оказывается, что А и В вместе дают наилучшее решение, то решением будет {А, Б}.
• Решение фиксированного размера: В этом решении есть 0 и 1, а цифра в i-й позиции указывает, следует ли включать i-й элемент, для приведенного выше примера решение будет дано {1, 1, 0, 0}, здесь 1 означает, что мы выбрали элемент, который находится в i-й позиции, а 0 означает, что мы не выбираем элемент в i-й позиции.

Классификация задач ветвей и границ:

Метод ветвей и границ можно разделить на три типа в зависимости от порядка поиска в дереве пространства состояний.

1. FIFO Branch and Bound
2. LIFO Branch and Bound
3. Метод наименьших затрат

Теперь мы обсудим каждый из этих методов более подробно. Для обозначения решений в этих методах будем использовать метод переменных решений.

1. Ветви и границы FIFO

Метод «первым пришел — первым обслужен» — это подход к проблеме ветвей и границ, в котором для создания дерева в пространстве состояний используется подход очереди. В этом случае выполняется поиск в ширину, то есть перебираются все элементы на определенном уровне, а затем перебираются элементы на следующем уровне, начиная с первого потомка первого узла на предыдущем уровне.

Для заданного набора {A, B, C, D} дерево пространства состояний будет построено следующим образом:

Дерево пространства состояний для набора {A, B, C, D} сначала рассмотрим элемент A, затем элемент B, затем элемент C и, наконец, мы рассмотрим последний элемент, которым является D. Мы выполняем BFS, исследуя узлы.

Итак, раз пройден первый уровень. Мы рассмотрим первый элемент, затем мы можем рассмотреть либо B, C, либо D. Если мы будем следовать маршруту, то он говорит, что мы делаем элементы A и D, поэтому мы не будем рассматривать элементы B и C. Если мы выберем только элементы A и D, то это говорит о том, что мы выбираем элементы A и D и не рассматриваем элементы B и C.

Выбор элемента A

Теперь мы расширим узел 3, так как мы рассмотрели элемент B и не рассмотрели элемент A, поэтому у нас есть два варианта исследования, то есть элементы C и D. Давайте создадим узлы 9 и 10 для элементов С и D соответственно.

Рассматриваемый элемент B и не учитываемый элемент A

Теперь мы расширим узел 4, так как мы рассмотрели только элементы C и не рассмотрели элементы A и B, поэтому у нас есть только один вариант изучения элемента D. Давайте создадим узел 11 для д.

Рассмотрены элементы C и не рассмотрены элементы A и B

До узла 5 мы рассмотрели только элементы D, а не выбрали элементы A, B и C. Итак, у нас больше нет элементов для исследования, поэтому на узле 5 , расширения не будет.

Теперь мы расширим узел 6, так как мы рассмотрели элементы A и B, поэтому у нас есть только два варианта исследования: элемент C и D. Давайте создадим узлы 12 и 13 для C и D соответственно.

Расширить узел 6

Теперь мы расширим узел 7, так как мы рассмотрели элементы A и C и не рассмотрели элемент B, поэтому у нас есть только один вариант изучения элемента D. Давайте создадим узел 14 для D.

Расширить узел 7

До узла 8 мы рассмотрели элементы A и D, а не выбрали элементы B и C. Таким образом, у нас больше нет элементов для исследования, поэтому на узле 8 не будет никакого расширения.

Теперь мы расширим узел 9, так как мы рассмотрели элементы B и C и не рассмотрели элемент A, поэтому у нас есть только один вариант изучения, который является элементом D. Давайте создадим узел 15 для D.

Разверните узел 9

2. Ветвь и граница LIFO

Подход «последним пришел — первым обслужен» для этой задачи использует стек для создания дерева пространства состояний. Когда узлы добавляются в дерево пространства состояний, они добавляются в стек. После того, как все узлы уровня добавлены, мы извлекаем самый верхний элемент из стека и исследуем его.

Для данного набора {A, B, C, D} дерево пространства состояний будет построено следующим образом:

Дерево пространства состояний для элемента {A, B, C, D}

Теперь расширение будет основано на узле, который появляется на вершине стека. Поскольку узел 5 находится на вершине стека, мы расширим узел 5. Мы вытолкнем узел 5 из стека. Поскольку узел 5 находится в последнем элементе, т. е. D, дальнейшее расширение невозможно.

Следующий узел, который появляется на вершине стека, — это узел 4. Выдвиньте узел 4 и разверните его. При расширении будет учитываться элемент D, а узел 6 будет добавлен в стек, показанный ниже:

Расширить узел 4

Следующий узел 6, который необходимо расширить. Выдвиньте узел 6 и разверните его. Поскольку узел 6 находится в последнем элементе, т. е. D, дальнейшее расширение невозможно.

Следующим расширяемым узлом является узел 3. Поскольку узел 3 работает с элементом B, узел 3 будет расширен до двух узлов, т. е. 7 и 8, работающих с элементами C и D соответственно. Узлы 7 и 8 будут помещены в стек.

Следующий узел, который появляется на вершине стека, — это узел 8. Выдвиньте узел 8 и разверните его. Поскольку узел 8 работает с элементом D, дальнейшее расширение невозможно.

Разверните узел 3

Следующий узел, который появится на вершине стека, — это узел 7. Выдвиньте узел 7 и разверните его. Поскольку узел 7 работает с элементом C, узел 7 будет дополнительно расширен до узла 9, который работает с элементом D, а узел 9 будет помещен в стек.

Следующий узел 6, который необходимо расширить. Выдвиньте узел 6 и разверните его. Поскольку узел 6 находится в последнем элементе, т. е. D, дальнейшее расширение невозможно.

Развернуть узел 7

Следующий узел, который появляется на вершине стека, — это узел 9. Поскольку узел 9 работает с элементом D, дальнейшее расширение невозможно.

Следующим узлом, который появляется на вершине стека, является узел 2. Поскольку узел 2 работает с элементом A, это означает, что узел 2 может быть дополнительно расширен. Его можно расширить до трех узлов с именами 10, 11, 12, работающих с элементами B, C и D соответственно. Там новые узлы будут помещены в стек, как показано ниже:

Расширить узел 2

В приведенном выше методе мы исследовали все узлы, используя стек, который следует принципу LIFO.

3. Ветвь и граница с наименьшей стоимостью

Для исследования дерева пространства состояний этот метод использует функцию стоимости. Предыдущие два метода также вычисляют функцию стоимости в каждом узле, но стоимость не используется для дальнейшего исследования.

В этом методе узлы исследуются на основе их стоимости, стоимость узла может быть определена с помощью задачи, и с помощью данной задачи мы можем определить функцию стоимости. Как только функция стоимости определена, мы можем определить стоимость узла.
Теперь рассмотрим узел, стоимость которого определена. Если это значение больше, чем U0, этот узел или его потомки не смогут дать решение. В результате мы можем убить этот узел и не исследовать его дальнейшие ветки. В результате этот метод не позволяет нам исследовать случаи, которые того не стоят, что делает его более эффективным для нас.

Давайте сначала рассмотрим узел 1 с бесконечной стоимостью, как показано ниже:

На следующей диаграмме узел 1 разбит на четыре узла с именами 2, 3, 4 и 5.

Узел 1 расширяется до четырех узлов с именами 2, 3, 4 и 5

Предположим, что стоимость узлов 2, 3, 4 и 5 составляет 12, 16, 10 и 315 соответственно.
В этом методе мы исследуем узел с наименьшей стоимостью. На приведенном выше рисунке мы видим, что узел с минимальной стоимостью — это узел 4. Итак, мы исследуем узел 4 со стоимостью 10.

Во время исследования узла 4, являющегося элементом C, мы можем заметить, что один возможный элемент, который остается неисследованным, — это D (т. е. мы уже решили не выбирать элементы A и B). Таким образом, он будет расширен до одного элемента D, допустим, этот номер узла равен 6.

Исследование узла 4, который является элементом C

Теперь в узле 6 не осталось элементов для исследования. Так что возможности дальнейшего расширения нет. Следовательно, элемент {C, D} является оптимальным способом выбора с наименьшими затратами.

Задачи, которые можно решить с помощью алгоритма ветвей и границ:

Метод ветвей и границ можно использовать для решения большинства комбинаторных задач. Некоторые из этих задач приведены ниже:

Преимущества алгоритма ветвей и границ:

• Мы не исследуем все узлы в алгоритме ветвей и границ. Благодаря этому алгоритм ветвей и границ имеет меньшую временную сложность, чем другие алгоритмы.
• Всякий раз, когда проблема невелика и разветвление может быть завершено за разумное время, алгоритм находит оптимальное решение.
• Используя алгоритм ветвей и границ, оптимальное решение достигается за минимальное время. При исследовании дерева оно не повторяет узлы.

Недостатки алгоритма ветвей и границ:

• Запуск алгоритма ветвей и границ занимает много времени.
• В худшем случае количество узлов в дереве может быть слишком большим в зависимости от размера проблемы.

Заключение

Алгоритмы ветвей и границ являются одними из самых популярных алгоритмов, используемых в задачах оптимизации, которые мы обсуждали в нашем руководстве. Мы также объяснили, когда пользователю подходит алгоритм ветвей и границ. Кроме того, мы представили алгоритм, основанный на ветвях и границах для назначения заданий. Наконец, мы обсудили некоторые преимущества и недостатки алгоритмов ветвей и границ.

Ответвления и переплетения — javatpoint