Глава 3 обход дерева перебор с возвратами


Содержание

Последовательность обхода дерева в обратном порядке такова:B,I,E,F,C,J,G,K,H,D,A.

Перебор с возвратами. Метод отсечения.

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

Рассмотрим один из методов для организованного поиска решения, исчерпывающего все варианты — перебор с возвратом (бэктрекинг, поиск с отходом назад). Далее будет показано, как применение дополнительных приемов, таких как отсечение позволяет существенно сократить объем операций поиска.

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

Построим дерево игры. Каждый узел представляет определенную позицию в игре. Если узел n представляет позицию x,то все потомки узла n соответствуют совокупности допустимых ходов из позиции x.

Пример 1:

Часть дерева игры в крестики-нолики. Указана цена игры для игрока №1,ставящего крестик:

x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Ход игрока №1 (x)
Ход игрока №2 (0)
Ход игрока №1 (x)
Цена = 1
Цена = 1
Цена = 0
Цена = -1
Цена = 0
Цена = -1
Цена = 0
Цена = 1
Цена = 0
Цена = 0
Цена = 1
A
H
G
F
E
D
C
B
K
J
I
* * * * * * * * * * * * * * * * * *

Замечание: аналогично можно построить дерево, узлы которого представляют этапы развития некоторой неигровой ситуации (см. §11).

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

Узлу n присваивается некоторое значение, исходя из следующих правил:

1. Если узел n соответствует позиции x, из которой делает ход игрок №1, тогда узлу n присваивается значение, равное максимуму из цен его сыновей. Т.е. из позиции x игрок №1 сделает ход, который принесет ему максимальный выигрыш.

2. Если из узла n (позиции x) делает ход игрок №2, то узлу n присваивается значение, равное минимуму из цен его сыновей. Т.е. из позиции x игрок №2 сделает ход, который принесет минимальный выигрыш игроку №1.

Пример2. Оценим все узлы, части дерева игры из примера 1.

А
С
F
E
B
I
D
G
J
H
K
Режим min
Режим max
1
1
-1
1
-1
1
Режим max
Режим min

B: цена = 1 известна.

E: последует ход игрока №1. Цена Е = максимуму из цен сыновей: I, т.е.max<0>=0.

F: цена = -1 известна.

C: последует ход игрока №2. Цене С = минимуму из цен сыновей E и F, т.е.
min<0,-1>=-1.

J: цена = 0 известна.

G: последует ход игрока №1. Цена G = максимуму из цен сыновей: J, т.е. max<0>=0.

K: цена = 0 известна.

H: последует ход игрока №1. Цена H = максимуму из цен сыновей: K, т.е. max<1>=1.

D: последует ход игрока №2. Цена D = минимуму из цен сыновей G, H; min<0,1>=0.

A: последует ход игрока №1. ЦенаA = максимуму из цен сыновей B,C,D,
max<1,-1,0>=1.

Таким образом цена узла A перед ходом игрока №1 равна 1, следовательно, на этапе A игрок №1 имеет стратегию, следуя которой, он получит 1 очко (т.е. победит). А именно, стратегию AB.

Аналогично, если игра дошла до этапа D, цена которого = 0, то игрок №1 имеет стратегию, которая обеспечит ему 0 очков (т.е. ничью). А именно DGJ.

При этом, считаем, что из любой позиции игрок №2 делает ход, наиболее невыгодный для №1.

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

Пусть, например, рассматривается узел С находящийся в режиме max (ход игрока №1). Известна цена сына C1 = 20. Оценивается сын C2.

С
С1
С2
С3
D1
max
min
15
≤15
20

Допустим, найдена цена одного из сыновей D1 узла C2, равная 15. Так как С2 в режиме min, то цена С2 не может быть больше 15, т.е. она заведомо меньше цены С1.

Т.к С в режиме max, а цена С2 меньше цены С1, то цена С2 не повлияет на цену С, рассмотрение С2 можно не продолжать – отсечь С2.

Пример 3. Оценить корень А дерева игры, применить бэктрекинг и метод отсечения. Цены узлов K-V заданы по условию.

5
2
4
5
2
6
8
5
4
2
1
6
1
8
3
5
2
3
4
6
2
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
T
U
V
max
min
S
max
≥6
≤4

Решение порядок обхода:

K L E M N F B O P G Q R H C S T I U V J D A.

Рассмотрим отсечение узла J.

Вычислена цена I = 4, значит, цена Р, который находится в режиме min будет .

Дана цена U = 6, тогда цена J, который находится в режиме max будет . Какова бы она не была, она не может стать ценой D, которая . Поэтому далее узел J и его сыновья не рассматриваются (отсекаются).

Таким образом цена D равна цене I и равна 4.

Оценка корня дерева говорит о том, что на этапе А игрок №1 имеет стратегию, при которой он получает 5 очков, а именно: A→C→H→Q.

Перебор с возвратом рекурсивно

Здравствуйте, помогите с небольшой задачкой:
1. Имеется список(типа массив) 5х5, заполненный нулями
2. нужно заполнить это массив цифрами от одного до 5 так, чтобы цифры в столбце и строке этого массива не повторялись
3. найти по возможности все варианты решения
4. использовать рекурсию
Например;
b= [[0,0,0,0,0], ===>>> [[1, 2, 3, 4, 5],
[0,0,0,0,0], ===>>> [5, 1, 2, 3, 4],
[0,0,0,0,0], ===>>> [4, 5, 1, 2, 3],
[0,0,0,0,0], ===>>> [3, 4, 5, 1, 2],
[0,0,0,0,0]] ===>>> [2, 3, 4, 5, 1],

Или хотя бы просьба объяснить в двух словах, как здесь применить рекурсию, а дальше я сам.
Заранее спасибо!

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

16.02.2015, 23:36

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

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

Перебор/поиск с возвратом в графе
Подскажите пожалуйста где я могу найти пример такой программы? Уже пару часов гуглю и нигде не.

Спуск с горы (перебор с возвратом, backtracking)
Есть такое задание: Решение задачи должно быть представлено в виде функции Matlab (если кто.

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

Новые книги

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

Независимо от того, кто вы – новичок, который делает первые шаги в бизнесе, или опытный предприниматель, Одностраничный маркетинговый план обеспечит вам рост и развитие.

Эта книга ломает все стереотипы! Вы узнаете:

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

• Почему копирование маркетинговой стратегии крупного бизнеса может уничтожить вас и какие стратегии действительно работают в малом и среднем бизнесе.

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

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

• Как избавиться от конкурентов и превратить ваше предложение в единственный разумный выбор для клиента.

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

• Как установить высокие цены на ваши продукты и услуги – чтобы клиенты еще и благодарили вас за это.

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

В книге описаны 20 блоков маркетинговой системы «Дело для Денег и Души». Создайте их хотя бы в «минимальной комплектации» и получайте доход от 15 000 рублей в неделю, не работая в офисе, занимаясь своим любимым делом. Свое дело – это альтернатива работе по найму, с одной стороны, и бизнесу в привычном его понимании – с другой. Система, изложенная в книге, подходит для людей творческих профессий, фрилансеров, специалистов, работающих дома, хендмейдеров… Не гадайте, подойдет ли она вам. Просто идите блок за блоком – вам понравится легкость, простота и эффективность этой системы построения своего дела. И доход на счете, который вы обязательно получите, если в точности выполните все рекомендации авторов.

Перебор с возвратом

Перебор с возвратом

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

3.1 Использование рекурсии для записи алгоритма

Приведенная нами в подразделе 2.1 схема алгоритма довольно проста, однако она обычно неприемлема для реализации. Действительно, вложенные друг в друга циклы – очень жесткая структура и если нам надо решать задачу для 100 ферзей, то нам придется писать 100 вложенных друг в друга циклов. Более того, для каждого n нам придётся писать свой вариант алгоритма, отличающийся количеством вложенных циклов. Поэтому вариант с вложенными циклами обычно бывает неприемлемым для реализации перебора с возвратом. В книге [2] приведён алгоритм перебора с возвратом основанный на интерпретации перебора как последовательности переходов вперед-назад. Мы сейчас приведем схему алгоритма перебора с возвратом, построенную на принципах структурного программирования (т.е. без переходов) с использованием рекурсии.

Посмотрим на текст алгоритма. Сам текст алгоритма рекурсивен! Текст для n=k состоит из текста для n=k- 1, помещённого в цикл. Таким образом, алгоритм легко переписать в рекурсивном виде. Снача ла мы приведём рекурсивный вариант алгоритма полного перебора.


Теперь – рекурсивный вариант алгоритма перебора с возвратом.

Чем отличаются данные алгоритмы ? Тем, что в первом проверка позиции происходит на самом позднем («глубоком») этапе перебора, а во втором на каждом этапе перебора происходит частичная проверка. (Если же все частичные проверки завершились успешно, получившуюся позицию уже можно не проверять.) Таким образом, перебор с возвратом исключает из перебора большое количество вариантов по сравнению с полным перебором.

3.2 Примеры решения задач при помощи перебора с возвратом

Первая задача – очень известная задача о раскраске карты (математики предпочитают обычно говорить о раскраске вершин графа).

Задача 3 Раскраска карты. Имеется географическая карта, на которой расположено n стран. Каждую страну надо раскрасить в один из k цветов так, чтобы соседние страны были раскрашены в разные цвета.

Географическую карту будем задавать в виде матрицы C размером n ґ n . Элемент C i,j равен 1, если страны i и j – соседние и равен 0 иначе.

Пространство перебора состоит из наборов ( x 1 . x n ), x i О <1, . k >. Условие совместимости m -го элемента с предыдущими: если C i,m = 1 (1 Ј i ), то x i № x m .

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

Однако в отличие от задачи о ферзях, в данной задаче перебор можно сократить ещё больше за счёт симметрии решений задачи. Предположим, мы нашли решение задачи. Если мы теперь в этом решении у всех вершин поменяем местами i -ую и j -ую краску, то получившаяся раскраска тоже будет решением. Из таких симметричных решений нам достаточно найти одно. Таким образом, при выборе краски для очередной страны нам достаточно перебрать все уже используемые краски и всего одну (первую) из новых.

Илон Маск рекомендует:  Можно ли отключить определенный элемент в radiogroup

Задача 4 Укладка рюкзака. Из заданных n предметов выбрать такие, чтобы их суммарная стоимость была не менее чем S , а суммарный объём не превосходил V .

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

Стоимости предметов будут храниться в массиве стоимость , а объёмы – в массиве объём . Пространством перебора в данном случае будут все подмножества множества <1 . n>. Каждое подмножество можно задавать набором ( x 1 . x n ), x i О <0,1>. Теперь задачу можно переформулировать в следующем виде: Найти набор ( x 1 . x n ), x i О <0,1>, такой что:
S i= 1 . n x i · стоимость i і S, S i= 1 . n x i · объём i Ј V .

Условия, которые можно проверять при выборе:

  • суммарный объём уже выбранных предметов не превосходит V ;
  • суммарная стоимость выбранных предметов и тех, которые мы можем выбрать не меньше S .

Второе условие удобнее переписать в виде: суммарная стоимость невзятых предметов не превосходит стоимости всех предметов минус S . Cтоимость всех предметов минус S будем хранить в переменной доп_ост . Получаем следующий алгоритм:

Задача 5 Расстановка знаков. Дано целое число m . Вставить между некоторыми цифрами 1, 2, 3, 4, 5, 6, 7, 8, 9, записанными именно в таком порядке, знаки «+» и «-» так, чтобы значением получившегося выражение было число m . Например, если m= 122, то подойдёт выражение: 12+34-5-6+78+9. Если расставить знаки требуемым образом невозможно, сообщить об этом.

Решение. Приводимая в [3] программа осуществляет полный перебор вариантов. Причём даже построение выражения осуществляется для каждого варианта отдельно – т.е. самым неэффективным способом. Приведём такой вариант решения (немного улучшенный по сравнению с версией в [3]).

Если основной цикл представить несколькими вложенными циклами – каждый для отдельной позиции знака в строке, то получится 8 вложенных циклов. Тогда уже можно начинать строить выражение сразу для группы вариантов. На самом нижнем (и наиболее часто исполняемом, а значит и наиболее дорогом) уровне перебора уже нет операций построения строки – они делаются раньше – сразу для групп элементов. Получим следующий текст (строка на первом уровне – t1 , на втором – t2 и т.д.): И так 8 циклов. Довольно длинно, но более эффективно. Причём рекурсивный вариант этого алгоритма устраняет громоздкость текста: (Вызов данной процедуры заменяет в программе signs1 весь основной цикл.)

Теперь цикл, перебирающий три варианта расстановки знаков, проще расписать напрямую следующим образом:

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

И, наконец, последнее, уже не столь существенное улучшение. Раз построенное выражение (символьную строчку t ) мы не используем для вычисления результата, то можно её вообще не строить (правда, запоминать расставленные знаки всё же придётся, чтобы можно было выдать результат).

Итак, мы пришли всё к той же схеме перебора с возвратом. Правда в этой задаче не удаётся отсечь варианты на ранних этапах перебора (поэтому перед рекурсивным вызовом нет оператора if ) и есть еще одно непринципиальное отличие – цикл заменён на три последовательных рекурсивных вызова.

Время выполнения программы, приведенной в [3] – 2.42 сек., программы signs1 – 2.20 сек., программы с процедурой sign_choice2 – 0.96 сек., программы с процедурой sign_choice3 – 0.22 сек., программы signs4 – 0.11 сек. Таким образом, нам удалось значительно сократить перебор. Да и текст программы стал короче.

Задача 6 Минимальный путь. На рисунке изображен треугольник из чисел: 7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 Требуется вычислить наименьшую сумму чисел на пути от верхней точки треугольника до основания. При этом:

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

Решение. При решении задачи полным перебором число вариантов равно 2 n- 1 , где n – число строк в треугольнике. Это, конечно же, неприемлимо. Но как сократить перебор ? Трудно придумать условие, по которому мы могли бы отсекать частично построенные варианты.

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

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

Пусть a i,j означает j -ое число в i -ой строке, s i,j – наименьшую сумму чисел от вершины до числа a i,j . Для s i,j выполняются следующие соотношения:

s 1,1 = a 1,1 , s i, 1 = a i, 1 + s i- 1,1 , s i,i = a i,i + s i- 1 ,i- 1 ,
s i,j = a i,j + min < s i- 1 ,j ,s i- 1 ,j- 1 >, 1 Ј n

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

Приведём еще один пример – задачу, в которой удаётся полностью избежать перебора.

Задача 7 Бал. Во время бала в зале, имеющем форму M -угольника A 1 A 2 . A M , этикетом предписано размещаться N придворным дамам вдоль стен и в углах так, чтобы у всех стен стояло равное число дам. Если дама находится в углу, то она считается стоящей у обеих стен этого угла. Вдоль стены может размещаться любое количество дам, а в углу не больше одной. Найти требуемое расположение дам.

Решение. Первый приходящий в голову способ решения для данной задачи – перебор. Однако легко догадаться, что по-существу важно получить какую-либо расстановку дам с суммарным количеством дам, стоящих вдоль стен, кратным количеству стен. Распредилить же потом их поровну не составит труда. А суммарное количество дам, стоящих вдоль стен, (при фиксированных количестве стен и дам) зависит только от того, сколько дам стоит в углах. Оно минимально, если в каждом углу стоит по даме и максимально, если вообще ни в одном углу не стоят дамы. Точнее (обозначим это число через s ): N Ј s Ј N+M . Нам требуется так подобрать s , чтобы оно было кратно M . Среди чисел от N до N+M хотя бы одно такое число обязательно найдётся. Это N+M — ( N mod M ). В углах будет стоять M- ( N mod M ) дам. Остаётся только выбрать углы и распределить оставшихся дам по сторонам.

3.3 Возврат

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

Однако, если при «движении вперёд» производятся ещё какие-нибудь изменения, их необходимо отменять при возврате.

В задаче о раскраске карты есть такие изменения – это пересчёт количества использованных красок – операторы: кол_красок := кол_красок+1; и восстановление – кол_красок := кол_красок-1;

В более сложных задачах (или менее удачных алгоритмах) изменений, которые надо восстанавливать, может быть значительно больше. За восстановлением таких изменений надо внимательно проследить (и, возможно, будет неочевидно как эти восстановления организовать). Поэтому проблема возврата обычно – одна из самых сложных.

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

Алгоритмы. Обход дерева

Давно я не писал, как то все времени не находилось. Мы говорили про деревья, давайте теперь поговорим про обход деревьев. Обходы деревьев нужны собственно для того чтоб оптимально быстрой найти необходимый элемент в дереве.

Собственно обход дерева, как и все обходы графов ( а дерево это обычный неориентированный граф ) делается двумя методами: в глубину (Depth-first) и в ширину (Breadth-first).

Какой из методов использовать?

На самом деле споров достаточно много, и если зайти на различные форумы — то вы получите огромное количество ответов, каждый из которых не факт что будет полезен для вас. Потому, для себя я решил таким образом( взято кстати с треда на stackoverflow):

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

Собственно, как я уже и писал, правильного ответа нет — потому надо пробовать разные варианты:) Эксперементировать всегда весело!

Так как мы будем пробовать на созданном бинарном дереве все алгоритмы, они редко бывают широкими, потому обсудим в начале поиск в глубь.

DFS. Алгоритмы в глубь имеют три типа обходов:

Pre-order стоит использовать именно тогда, когда вы знаете что вам нужно проверить руты перед тем как проверять их листья.

В результате Pre-order обхода мы получим такой порядок :

In-order обход используется как раз когда нам надо проверять в начале детей и только потом подыматься к родительским узлам.

В таком случае мы получаем просто: A,B,C,D,E,F,G,H,I

Post-order самый забавный случай — это случай когда нам нужно начать-так сказать с листов и завершить главным узлом — тоесть разложить дерево на то, как оно строилось.

В таком случае мы полчаем: A, C, E, D, B, H, I, G,F

Как видим — код очень похож:) просто разный порядок вызовов.

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

Собственно на этом пока все:)

Как обычно: исходники примеров вы можете найти тут.

Обход двоичного дерева

Обход дерева в глубину

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

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

Существует три основных способа обхода в глубину.

    Прямой (pre-order)
    Посетить корень
    Обойти левое поддерево
    Обойти правое поддерево

Рекурсивное решение полностью соответствует описанию алгоритма

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

В качестве функции visit можно передавать, например, такую функцию

Рассмотрим теперь результат каждого из обходов.

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

выведет дерево в обратном порядке.

postOrderTraversal выводит узлы слева направо, снизу вверх. Это имеет ряд применений, сейчас рассмотрим только одно – удаление дерева. Обход дерева начинается снизу, с узлов, у которых нет родителей. Их можно безболезненно удалять, так как обращение root->left и root->right происходят до удаления объекта.

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


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

Реализовывать стек будем с помощью массива, который при переполнении будет изменять свой размер. Напомню, что реализация стека требует двух функций — push, которая кладёт значение на вершину стека и pop, которая снимает значение с вершины стека и возвращает его. Кроме того, будем использовать функцию peek, которая возвращает значение с вершины, но не удаляет его.

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

Обход в ширину

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

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

Реализация на си

Заменим очередь на стек

Теперь функция обходит узлы как Post-Order, только задом наперёд.

Обход бесконечных деревьев

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

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

Если дерево растёт бесконечно в ширину, но при этом имеет конечную глубину (то есть, у узла не два наследника, а из бесконечно много), то можно использовать поиск в глубину.

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

Пусть робот «шмугл» индексирует страницы на сайте. Количество ссылок на странице конечно. (т.к. страница конечна). То есть можно рассматривать страницы как узел, ссылки с которой ведут к другим узлам. Конечно, есть ссылки, которые ведут на предыдущие страницы, есть кросс-ссылки между страницами на одном уровне вложенности и т.д., сейчас всех тонкостей рассматривать не будем. То есть, есть дерево, у каждого узла которого конечное число наследников. В лучшем случае количество ссылок конечно и охватывает весь сайт. Однако, может попасться страница, на которой есть календарь, ссылки с которого генерируются автоматически. Программист забыл, что ссылки в будущее надо запретить, поэтому в глубину мы получаем бесконечно дерево, каждый новый узел которого генерируется автоматически. Обход этого дерева закончится, например, когда будет забит канал или превышен лимит по ссылкам.

Перебор с возвратом (Общая схема)

В алгоритме перебора векторА строится покомпонентно слева направо. Предположим, что уже найдены значения первых
(k-1) компонент, А=(а1, а2, . а(k-1), ?, . ?), тогда заданное множество условий ограничивает выбор следующей компоненты аk некоторым множеством SkÌUk.

Если Sk<>[ ](пустое), мы вправе выбрать в качестве аk наименьший элемент Sk и перейти к выбору (k+1)компоненты и так далее.

Однако если условия таковы, что Sk оказалось пустым, то мы возвращаемся к выбору (k-1)компоненты, отбрасываем а(k-1) и выбираем в качестве нового а(k-1) тот элемент S(k-1),который непосредственно следует за только что отброшенным.

Может оказаться, что для нового а(k-1)условия задачи допускают непустое Sk, и тогда мы пытаемся снова выбрать элемент аk. Если невозможно выбрать а(k-1),мы возвращаемся еще на шаг назад и выбираем новый элемент а(k-2)и так далее.

Графическое изображение — дерево поиска. Корень дерева
(0 уровень) есть пустой вектор.

Его сыновья суть множество кандидатов для выбора а1, и, в общем случае, узлы k-го уровня являются кандидатами на выбор аk при условии, что а1, а2, . а(k-1) выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим получить все такие узлы.

Задача о лабиринте

Классическая задача. Дано клеточное поле, часть клеток занята препятствиями. Необходимо попасть из некоторой заданной клетки в другую заданную клетку путем последовательного перемещения по клеткам. Изложение задачи опирается на рисунок произвольного лабиринта и две «прорисовки» с использованием простого перебора и метода «волны».

Классический перебор выполняется по правилам, предложенным в 1891 г. Э. Люка в “Математических досугах”:

· в каждой клетке выбирается еще не исследованный путь;

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

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

· поиск одного пути;

· поиск одного пути кратчайшей длины методом «волны».

Решение первой задачи.

intxn, yn, xk, yk, N;

Solve(A, xn,yn,xk, yk,1);

//Функция output (intA[][Nmax+1], … );

void Solve(int A[][Nmax+1], int x, int y, intxk, intyk, int k)

//x, y — координатыклетки

Тогда задачу можно переформулировать следующим образом. Найти минимальное число столбцов, таких, что множество единиц из них “покрывают” множество всех строк. Очевидно, что для примера это один столбец — второй. Поговорим о структурах данных.

Sset=Set of 0..Nmax;

intman; // 0..Nint_1 //номержителя

intnumber; // числопартий, которыеонпредставляет

struct Person A[Nint];

Логикаформирования исходных данных (фрагмент реализации).

for i:=1 to N do if i in S then Inc(ch);

for i:=1 to N do with A[i] do begin man:=i; part:=[i]; end;

for i:=1 to N do begin

whileNot eoln do begin read(t);A[t].part:=A[t].part+[i];

for i:=1 to N do A[i].number:=Num(A[i].part);

Следующим очевидным шагом является сортировка массива А по значению поля number. Становится понятным и необходимость ввода поля man в структуру записи — после сортировки номер элемента массива А не соответствует номеру жителя острова.

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

блокобщихотсечений

ifRt=[] then begin if nm Q) do Inc(i);

Заметим, что необходимо исключить партии, “покрытые” жителями, представляющими карликовые партии из А[i].partоставшихся жителей. Это может привести к тому, что возможно появление жителей, представляющих все оставшиеся партии. Совместим проверку наличия вхождений, исключение части жителей и сжатие массива A в одной функции. Ее вид.

for i:=1 to t-1 do

for j:=i+1 to t do if A[j].part j then v:=v+A[j].part;

if A[i].part*v<>A[i].Part then r:=r+[A[i].man];

for i:=1 to t do if A[i].man in r then p:=p+A[i].part;

Итак, фрагмент предварительной обработки (до перебора).

while Come(t) and (Rt<>[]) do begin Rg:=[];Rp:=[];

ifRp<>[] then begin

for i:=1 to t do begin

if (j in Rp) and (j in A[i].part) then A[i]part:=A[i].part-[j];

if (Rt<>[]) then One(t,Rt);

Блок общих отсечений. Подсчитаем для каждого значения i (1£i£t) множество партий, представляемых жителями, номера которых записаны в элементах массива с i по t (массив С:array[1..N] ofSset). Тогда, если Res — текущее решение, а Rt — множество партий, требующих представления, то при Res+C[i]£Rt решение не может быть получено и эту ветку перебора следует “отсечь”.

C[t]:=A[t].part; for i:=t-1 downto 1 do begin

Блок отсечений по i. Если при включении элемента с номером i в решение, значение величины Rt не изменяется, то это включение бессмысленно (A[i].part*Rt=[]).

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

Примечание. Графовая модель задачи (двудольный граф). Каждому жителю соответствует вершина в множестве X, каждой партии — вершина в множестве Y. Ребро (i,j)существует, если житель с номером iпредставляет партию с номером j. Требуется найти минимальное по мощности множество вершинS, такое, что SÍXи для любой вершины jÎY существует вершина iÎS, из которой выходит ребро в вершину j. Модификация задачи о нахождении минимального доминирующего множества.

2.1.7. Задача о коммивояжере (перебор вариантов)

Постановка задачи. Классическая формулировка задачи известна уже более 200 лет : имеются n городов, расстояния между которыми заданы ; коммивояжеру необходимо выйти из какого-то города, посетить остальные n-1 городов точно по одному разу и вернуться в исходный город. При этом маршрут коммивояжера должен быть минимальной длины (стоимости).

Задача коммивояжера принадлежит классу NP-полных, то есть неизвестны полиномиальные алгоритмы ее решения. В задаче с n городами необходимо рассмотреть (n-1)! маршрутов, чтобы выбрать маршрут минимальной длины. Итак, при больших значениях n невозможно за разумное время получить результат.

Перебор вариантов. Оказывается, что и при простом переборе не обязательно просматривать все варианты. Это реализуется в данном классическом методе.

Var A:array[1..Max,1..Max] ofinteger;


Way, BestWay:array[1..Max] ofbyte;

Идея решения. Пусть мы находимся в городе с номером v. Наши действия.

Шаг 1. Если расстояние (стоимость), пройденное коммивояжером до города с номером v, не меньше стоимости найденного ранее наилучшего решения (BestCost), то следует выйти из данной ветви дерева перебора.

Шаг 2. Если рассматривается последний город маршрута (осталось только вернуться в первый город), то следует сравнить стоимость найденного нового решения со стоимостью лучшего из ранее найденных. Если результат сравнения положительный, то значения BestCostи BestWayследует изменитьи выйти из этой ветви дерева перебора .

Шаг 3. Пометить город с номером v как рассмотренный,записать этот номер по значению Countв массив Way .

Шаг 4. Рассмотреть пути коммивояжера из города v в ранее не рассмотренные города. Если такие города есть, то перейти на эту же логику с измененными значениями v, Count, Cost,иначе на следующий шаг.

Шаг 5. Пометить город v как нерассмотренный и выйти из данной ветви дерева перебора.

Пример. Ниже приведены матрицы А и В (после сортировки элементов каждой строки матрицы А).

Примечание. Можно использовать любой из методов сортировки, но авторы предпочитают использовать метод Хоара[1] из-за определенного изящества в его реализации. Рекурсивная логика плюс смена направления изменения индекса в одной циклической конструкции.

Примечание. Символом @ обозначено бесконечное расстояние.

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

if Count=N then begin Cost:=Cost+A[v,1];Way[N]:=v;

Использование метода перебора последовательностей, как раскраски вершин графа при обходе в ширину, на системах с SMP-архитектурой для решения переборных задач Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Трещев Иван Андреевич

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

Похожие темы научных работ по математике , автор научной работы — Трещев Иван Андреевич,

Текст научной работы на тему «Использование метода перебора последовательностей, как раскраски вершин графа при обходе в ширину, на системах с SMP-архитектурой для решения переборных задач»

УДК 681.3.06 И.А. Трещёв

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

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

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

Введение. Криптостойкость популярного алгоритма Диффи-Хеллмана основана на вычислительной сложности обращения функции в некоторой конечной мультипликативной абелевой группе [1]. Перебор возможных решений в данной группе можно осуществлять с помощью метода ветвей и границ. Опишем данный метод и пути его распараллеливания для систем с SMP-архитектурой. Пусть заданы конечные множества А>, А^,—. Для произвольного целого п>0 под п-местным предикатом будем понимать функцию Р: А> х А2х. х Ап ^ <0,1>, принимающую значения 1 (истина) или 0 (ложь). Предикатом

будем называть произвольную функцию Q: У А1 х А2 х—х Ап ^ <0,1>.

Формулировка задачи. Даны конечные множества А1, А2,— и для каждого целого Ь задан ¿-местный предикат Р\ (х!,х2. хг). Предполагается, что для всех ¿>1 справедливы импликации Р\ (х1,х2. хг) = 1 ^ Рь_1(х1,х2. хг_1) = 1. Требуется построить последовательности (Х1,Х2. ХП), где XI е Ац при 1 i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Результаты тестирования многопоточных приложений [4] для классических задач представлены в таблице (время указано в миллисекундах). Тестирование разработанных многопоточных приложений производилось на системе под управлением Microsoft Windows Server 2003, оснащенной двумя четырехъядерным микропроцессорами Intel Pentium 4 Xeon 5320, объем оперативной памяти 8 Gb.

Результаты тестирования многопоточных приложений

Количество Перебор гамильто- Задача Перебор раз- Перебор возрастаю- Генерация раз-

потоков новых циклов в Гаусса о ложений числа щих последователь- биений задан-

графе ферзях в сумму ностей ного множества

Перебор с возвратом, последовательная реализация

13469 23906 5453 18324 18390

Многопоточные приложения, реализующие поиск в ширину как раскраску вершин графа

1 16172 26953 6297 21125 21344

2 14953 25657 6266 16297 18969

3 13781 24062 6079 15484 18793

4 12640 22219 5625 15188 15188

5 11594 20829 5406 14813 13734

6 10328 18922 5296 13953 12625

7 9453 17047 5235 12578 12422

8 8265 15422 5234 13922 12266

9 7844 14266 5219 14485 12032

10 8297 13078 5187 14875 13500

11 8500 12375 4891 14937 13609

12 12041 12986 4797 15378 17437

13 12437 15187 4735 16225 19422

14 12923 15829 4703 16984 20204

15 13964 16922 4266 17937 22672

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

1. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с.

2. Хусаинов А.А. Архитектура вычислительных систем: Учеб. пособие / А.А. Ху-саинов, Н.Н. Михайлова // Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2004. — 123 с.

3. Беляев В.А. Распараллеливание обхода дерева поиска для решения задачи о рюкзаке на кластерной системе / В.А. Беляев, Н.Е. Тимошевская // Высокопроизводительные параллельные вычисления на кластерных системах: Матер. междунар. науч.-практ. семинара / под ред. проф. Р.Г. Стронгина. — Нижний Новгород: Изд-во Нижегор. гос. унта, 2001. — С. 16-20.

4. Трещев И.А. Построение многопоточных приложений для распараллеливания алгоритмов перебора // Информатика и системы управления. — 2008. — №1 (15). — С. 151-159.

Трещев Иван Андреевич

ГОУВПО «Комсомольский-на-Амуре государственный технический университет», ст. преподаватель кафедры Математическое обеспечение и применение ЭВМ Эл. адрес: kalkt@yandex.ru

Using of parallel backtracking, as graph marking in wide tree traverse, on systems with SMP-architecture for solving search problems

Methods of constructing parallel algorithms for tasks,which could be solved with backtrack algorithm, oriented on the SMP-architecture, are proposed in this paper. These methods are used for building multithreaded applications. Experimental results concerning the methods for classic tasks on backtrack are given.

Key words: cryptography, reboric problems, recourse, multithreading.

Перебор дерева значений

Необходимо совершить перебор дерева значений и вывести это на макет.

С макетом проблемы нет, зато есть проблема с перебором дерева значений, как его правильно перебирать?

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

Я пытался организовать перебор при помощи выборки, но для Дерева значений это не подходит.

Есть такой вариант:

Процедура СохранитьПравила()
Диалог = Новый ДиалогВыбораФайла(РежимДиалогаВыбораФайла.Сохранение);
Диалог.Заголовок = «Выберите имя файла для сохранения»;
Диалог.МножественныйВыбор = Ложь;
Диалог.Фильтр = «Текстовый файл(*.rul)|*.rul»;
Если Диалог.Выбрать() Тогда
ИмяФайла = Диалог.ПолноеИмяФайла;
Иначе
Возврат;
КонецЕсли;

Файл = Новый ЗаписьТекста(ИмяФайла);
Файл.ЗаписатьСтроку(«fsin:»+СокрЛП(ДокОбразецОтправителя)+»=>»+СокрЛП(ДокОбразецПолучателя));

ОбходУровня(Неопределено, Файл); // Начинаем перебор ДЗ
Файл.Закрыть();
Сообщить(«Готово!»);
КонецПроцедуры

Процедура ОбходУровня(СтрУ, Файл)
Если СтрУ = Неопределено Тогда
СтрУ = ЭлементыФормы.ТППолучательД.Значение; // Получаем строки нулевого уровня из деревазначений
КонецЕсли;

Строки = СтрУ.Строки;
Для Каждого Стр Из Строки Цикл // перебор строк подчиненного узла
Если Стр.Строки.Количество()>0 Тогда ОбходУровня(Стр, Файл); Продолжить; КонецЕсли; // Перебираем дочерний узел
// здесь любые операции со строкой дерева значений
Если Стр.Пропускать Тогда Продолжить; КонецЕсли;
СтрСлева = СокрЛП(Стр.Соответствие);
СтрСправа = СокрЛП(Стр.Реквизит)+»||»+?(Стр.Пропускать,1,0);
Файл.ЗаписатьСтроку(СтрСлева+»=>»+СтрСправа);
КонецЦикла;
КонецПроцедуры

Дерево

Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.

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

Способ представления бинарного дерева:


  • A — корень дерева
  • В — корень левого поддерева
  • С — корень правого поддерева

Корень дерева расположен на уровне с минимальным значением.

Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .

Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .

Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.

Остальные элементы – внутренние узлы (узлы ветвления).

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

Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .

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

Имеется много задач, которые можно выполнять на дереве.

Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.

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

Способы обхода дерева

Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.

Существует три способа обхода дерева:

  • Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
  • Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
  • Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
Реализация дерева

Узел дерева можно описать как структуру:

При этом обход дерева в префиксной форме будет иметь вид

Обход дерева в инфиксной форме будет иметь вид

Обход дерева в постфиксной форме будет иметь вид

Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

  • оба поддерева – левое и правое, являются двоичными деревьями поиска;
  • у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X ;
  • у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X .

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

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

Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.

Решение задач обхода лабиринта с помощью перебора с возвратом

Цель урока: изучить метод перебора с возвратом на примере задачи обхода лабиринта

Задачи:

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

План урока

Изучение нового материала.

Практическая работа на компьютере.

Подведение итогов урока.

Ход урока

1. Организационный момент

Учитель приветствует учащихся, отмечает отсутствующих, проверяет готовность учащихся.

2. Изучение нового материала

Задача обхода лабиринта. Постановка задачи. (Слайд 4).

Имеется лабиринт прямоугольной формы. Нужно найти путь из заданной клетки (вход) в другую заданную клетку (выход). Ходы разрешается делать только по горизонтали и вертикали, и только по проходам. Гарантируется, что путь существует. Найти решение.

Учитель задает вопрос: Каким способом можно решить задачу? Учащиеся предлагают варианты решения, учитель их подводит к мысли о необходимости изучить метод Перебора с возвратом (backtrack) , общего метода упорядоченного перебора.

Метод перебора с возвратом использует два правила:

  • В каждой клетке выбирать еще не исследованный путь.
  • Если из исследуемой клетки не ведут неисследованные пути, вернуться на одну клетку назад по последнему пройденному пути.

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

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

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

Далее учитель объясняет суть метода поиска решения на примере (Слайд 6), знакомит с общей схемой рекурсивного перебора (Слайд 7).

Итак, метод решения задачи выбран.

Начинается следующий этап решения задачи.

Учитель задает вопросы ученикам «Что нужно задать, чтобы решить задачу?», «Какие еще нужны данные для решения задачи?», «Как представить результат?». Учитель и ученики обсуждают возможные варианты ответов.

Учитель задает вопросы учащимся «Как представить лабиринт?», «Как обозначить стены и проходы?», «Как оградить лабиринт внешними стенами?», «Как организовать смещение по лабиринту?» и др. Учащиеся самостоятельно или при помощи наводящих вопросов отвечают на поставленные вопросы. (Слайды 8-10).

Далее учащиеся составляют словесный алгоритм решения задачи.

Следующий слайд знакомит их с рекурсивным алгоритмом решения задачи. Учащиеся читают готовую программу и комментируют ее. (Слайды 11-15).

В заключении учитель предлагает следующие задания:

  • Назовите достоинства и недостатки метода перебора с возвратом
  • Назовите недостатки рассмотренного решения
  • Как можно их исправить?
  • Как можно переформулировать задачу?

Учащиеся отвечают на вопросы.

Учитель предлагает задания для самостоятельной работы:

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

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

3. Практическая работа на компьютере

Учащиеся должны выполнить первое и второе задание для самостоятельной работы. (Второе задание не является обязательным и по желанию учащихся может быть выполнено дома).

4. Подведение итогов

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

5. Домашнее задание

Выполнить третье задание для самостоятельной работы.

Илон Маск рекомендует:  AnsiUpperCase - Функция Delphi
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL