Перебор и его сокращение


Содержание

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

Рассмотрим использование перебора с возвратом при решении других задач. Если пространство перебора представляет собой X1  X2  Xn, то общую схему можно записать так:

procedure перебор_с_возвратом(m : integer); var i : integer;beginif m > n then elsefor i Xm do begin x[m] := i;if then перебор_с_возвратом(m+1);end;end;

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

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

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

Пространство перебора состоит из наборов (x1. xn), xi  <1, . k>. Условие совместимости m-го элемента с предыдущими: если Ci,m=1 (1  i n then elsefor i := 1 to k do begin цвет[m] := i; if then перебор_с_возвратом(m+1); end; end;

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

procedure перебор_с_возвратом(m : integer); var i : integer; beginif m > n then else beginfor i := 1 to кол_красок do begin цвет[m] := i; if then перебор_с_возвратом(m+1); end; if кол_красок

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

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

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

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

procedure перебор_с_возвратом(m : integer); var i : integer; beginif m > n then else begin x[m] := 0; ост_стоимость := ост_стоимость+стоимость[m]; if ост_стоимость

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

program signs1; var i, ii, kod : integer; t : string; op : char; s,r,m : longint; begin readln(m); for ii := 0 to 6560 do begin kod := ii; t := '1'; for i := 2 to 9 do begincase (kod mod 3) of 1: t := t+'+'; 2: t := t+'-'; end; t := t+chr(48+i); kod := kod div 3 end; t := t+'.'; s := 1; r := 0; op := '+'; for i := 2 to length(t) do begin if t[i] n- 1, где n – число строк в треугольнике. Это, конечно же, неприемлимо. Но как сократить перебор ? Трудно придумать условие, по которому мы могли бы отсекать частично построенные варианты.

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

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

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

s1,1 = a1,1, si,1 = ai,1 + si-1,1, si,i = ai,i + si-1,i-1,
si,j = ai,j + min <si-1,j,si-1,j-1>, 1 end;end;end;

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

Таким образом, пространство перебора всегда – параллелепипед. (В общем случае – множество наборов <(y1. yn) : y1  Y1, yn Yn>, Y1, . Yn Y.) Такое пространство можно задать, задав множества Y1, . Yn. В нашем случае это означает, что мы должны указать, какие значения разрешены для каждого из ферзей. Так мы приходим к компактному представлению пространства перебора, с которым и будем работать в дальнейшем.

На рисунках 4, 5, 6 показаны те же пространства перебора, что и на рисунках 1, 2, 3 соответственно. Там, где значение для ферзя запрещено – квадрат изображён чёрным цветом, где разрешено – белым. В дальнейшем мы будем вертикали, соответствующие ферзям изображать вплотную (у нас получится шахматная доска).

Проследим, какими будут первые полностью построенные позиции при приведённом алгоритме. Сначала будет рассмотрен вариант, когда все ферзи занимают положение 1, потом последний ферзь займёт положение 2 и т.д. Но постойте! Ведь уже когда первый ферзь занимает положение 1, то все позиции, в которых второй ферзь занимает положение 1 или 2 будут заведомо неприемлемы. Т.о. первые 2 · n n- 2 вариантов будут рассмотрены впустую. Но ведь это можно было заметить уже при расстановке второго ферзя.

Иначе говоря, из пространства перебора заведомо можно удалить варианты, когда второй ферзь занимает положение 1 или 2. Для случая n=3 сокращённое пространство перебора показано на рис. 3.

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

for i1 := 1 to n do begin ферзь[1] := i1;for i2 := 1 to n do begin ферзь[2] := i2; if then for i3 := 1 to n do begin ферзь[3] := i3; if then for i4 := 1 to n do begin . if then end;end;end;end;

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

При сокращении пространства перебора надо иметь в виду насколько сокращается пространство и соотносить размер этого сокращения с затратами на его реализацию. Если размер сокращения не велик по сравнению с общим объёмом перебора, то обычно не стоит ``городить огород'' и реализовывать такое сокращение, так как затраты на выполнение более сложной схемы перебора могут ``съесть'' весь выигрыш от сокращения. Кроме того, каждое усложнение алгоритма – лишняя возможность сделать ошибку.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Учись учиться, не учась! 10387 - | 7888 - или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Значение слова «перебор»

1. Действие по глаг. перебирать (во 2 знач.), а также звуки этого действия. От кормовой надстройки доносился глуховатый перебор струн: кто-то играл на гитаре. Лавренев, Сказка. Сейчас, еще около села, Сторожев услышал говорливые переборы гармоник. Вирта, Одиночество.

2. Излишек чего-л., взятый сверх надлежащего количества. Учет продолжался более пяти дней. При помощи сельских старост и проверки книг много обнаружилось лишних переборов в податях и недоимках. Наумов, Мирской учет. || В карточных играх: излишнее количество очков на взятых игроком картах. — Вы в двадцать одно играете? Если набрал двадцать — хорошо, двадцать один — отлично. А если двадцать два? Как это называется? Перебор! А. Васильев, Понедельник — день тяжелый.

Источник (печатная версия): Словарь русского языка: В 4-х т. / РАН, Ин-т лингвистич. исследований; Под ред. А. П. Евгеньевой. — 4-е изд., стер. — М.: Рус. яз.; Полиграфресурсы, 1999; (электронная версия): Фундаментальная электронная библиотека

Полный перебор — общий метод решения задач путём перебора всех возможных потенциальных решений.

В частности: Перебор делителей — алгоритм факторизации и тестирования простоты в вычислительной математике.

Метод перебора — простейший алгоритм минимизации.


Перебор — вид колокольного звона.

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

Перебор — способ игры на струнных щипковых музыкальных инструментах.

Перебор — деревня в Собинском районе Владимирской области.

Перебор — деревня в Никольском районе Вологодской области.

Перебор — деревня в Сланцевском районе Ленинградской области.

Перебор — посёлок в Маслянинском районе Новосибирской области.

Перебор — деревня в Берёзовском районе Пермского края.

Перебор — деревня в Каменском городском округе Свердловской области.

Перебор — железнодорожная станция в Каменском городском округе Свердловской области.

Перебор — река, приток Печоры

ПЕРЕБО'Р, а, м. (разг.). 1. Излишек чего-н., взятый сверх надлежащего количества. П. по текущему счету. 2. Излишнее количество очков на взятых игроком картах (карт. арго). 3. Механизм токарного станка, служащий для уменьшения скорости вращения шпинделя (тех.).

Источник: «Толковый словарь русского языка» под редакцией Д. Н. Ушакова (1935-1940); (электронная версия): Фундаментальная электронная библиотека

перебор

1. последовательный поиск

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

3. муз. перебор струн музыкального инструмента

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

5. церк. погребальный звон; звон всех колоколов от малого к большому

Делаем Карту слов лучше вместе

Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать Карту слов. Я отлично умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!

Спасибо! Когда-нибудь я тоже научусь различать смыслы слов.

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

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

Пакет 10. Перебор и способы его сокращения

В задачах, в которых выделены разделы «Входные данные» и «Выходные данные» предполагается, что данные считываются из текстового файла INPUT.TXT, а результат записывается в файл OUTPUT.TXT

1. Даны N целых чисел X1, X2, …, Xn. Расставить между ними знаки «+» и «-» так, чтобы значение получившегося выражения было равно заданному S.

2 ≤ N ≤ 24, 0 ≤ Xi ≤ 50 000 000, -1 000 000 000 ≤ S ≤ 1 000 000 000, время 3 с.

В первой строке находятся числа N и S. В следующей строке – N чисел через пробел

Если получить требуемый результат невозможно, вывести «No solution», если можно – то вывести равенство. Если решение не единственное, вывести любое

Оптимизация перебора

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

Введение

Наверняка вы сталкивались с задачами, которые приходилось решать перебором. А если вы занимались олимпиадным программированием, то точно видели NP-полные задачи, которые никто не умеет решать за полиномиальное время. Такими задачами, например, является поиск пути максимальной длины без самопересечений в графе и многим известная игра — судоку, обобщенная на размер . Полный перебор крайне долгий, ведь время его работы растёт экспоненциально относительно размера входных данных. Например, время поиска максимального пути в графе из 15 вершин наивным перебором становится заметным, а при 20 — очень долгим.

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

Поподробнее про перебор

Пример

Рассмотрим наивное решение задачи о нахождении пути максимальной длины без самопересечений в графе G.

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


Если посмотреть в это решение чуть глубже, то можно увидеть, что по-настоящему был запущен классический поиск в глубину, но на другом графе — графе состояний S. В этом графе вершины задаются маской вершин графа G, принадлежащих текущему пути, и номером последней вершины. Рёбра задаются наличием ребра в графе G между последними вершинами путей и равенством остальной маски.

Большинство переборов можно представить в виде поиска по графу состояний.

А что мы собственно ищем

Переборы бывают трёх типов:

1) Проверка существования.
2) Максимизация/Минимизация на не взвешенном графе.
3) Максимизация/Минимизация на взвешенном графе.

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

А теперь сами оптимизации.

Оптимизация №1: мемоизация, или ленивость

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

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

Обычно реализовать это не сложно. Нужно добавить 2 строчки: в начале проверять, что нас здесь ещё не было, а в конце записывать, что мы здесь были.

Оптимизация №2: отсечение по ответу

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

Хорошим примером для этой оптимизации является поиск пути максимальной длины без самопересечений в графе G. Эта задача NP-полная.

Допустим, мы находимся в каком-то состоянии s графа S. Если нам, как ни крути, не удастся улучшить результат, то стоит вернуться. Теперь надо научиться это проверять. Например, можно посчитать количество достижимых вершин графа G из последней вершины пути состояния s и прибавить длину уже полученного пути, то полученное число будет верхней границей максимального ответа, достижимого из s. Значит, если оно меньше текущего результата, то можно не запускать перебор из этого состояния.

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

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

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

Оптимизация №3: жадность

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

А теперь по порядку.

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

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

Пара слов про взвешенные графы

Обычно алгоритм Беллмана — Форда пишут примерно так:

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

Чем «плох» поиск в глубину и поиск в ширину

Красным выделены множества посещённых состояний графа S после некоторого времени работы поиска в глубину и в ширину соответственно.

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

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

Механизмы выбора области поиска

Жадность

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

Все помнят, что есть число 1 и есть число N, но многие забывают, что есть ещё и числа между ними. Жадность — это выбор одного ребра, а поиск в глубину — выбор N рёбер. Давайте напишем жадный поиск в глубину, который будет переходить по первым k рёбер.

Если использовать этот метод, то перебор будет обходить намного большие поддеревья графа S.

Проблема в том, что если взять слишком маленькое k, то ответ может оказаться неправильным, а если слишком большое, то времени может не хватить. Решение довольно простое: надо выбрать все возможные k. То есть написать внешний цикл, перебирающий k от 1 до бесконечности, пока время не кончилось, а в теле цикла запускать поиск решения.

Здесь стоит понять, что так как количество просмотренных состояний графа S растёт экспоненциально относительно роста k, то перебор этой переменной от 1 до k-1 не будет увеличивать асимптотическую сложность. В худшем случае время работы увеличится не более чем в константу раз, а на практике значительно уменьшится из-за отсечения по хорошему ответу.

Iterative deepening

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

Суть метода заключается в том, чтобы создать глобальную переменную — максимальная глубина, на которую должен спускаться поиск в глубину. Так же как и с k запускаем внешний цикл по этой глубине.

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


Ограничение размера очереди поиска в ширину

Это тоже жадность, но теперь для поиска в ширину. Из названия понятно, что мы будем ограничивать очередь. Для этого опять заведём глобальную переменную — размер очереди и переберём её от 2 до бесконечности. Но перебирать будем не по +1, а умножать на константу, например, на 2.

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

Что из всего этого теперь писать

Для наилучшего результата надо написать почти всё и почти сразу.

Вначале запускаем поиск в глубину на некоторое время с мемоизацией, отсечением по ответу, сортировкой рёбер, и перебором k, но без Iterative deepening.
Далее запускаем поиск в ширину с отсечением по ответу и ограничением размера очереди.

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

Теперь немного практики

Поиск максимального пути без самопересечений в графе

Случайный граф: 18 вершин, 54 ребра.
Время работы:
Нет оптимизаций

4 сек.
Мемоизация, отсечение по ответу

Случайный граф: 30 вершин, 90 рёбер.
Нет оптимизаций > 1 часа (не дождался).
Мемоизация, отсечение по ответу

0.5 с.
Мемоизация, отсечение по ответу, жадность

Перебор и методы его сокращения

Название Перебор и методы его сокращения
страница 1/9
Дата конвертации 20.05.2012
Размер 0.74 Mb.
Тип Документы
1. /chapter1.DOC
2. /chapter2.DOC
3. /chapter3.DOC
4. /chapter4.DOC
5. /chapter5.doc
6. /conclusion.DOC
Информатика ключевой предмет современной школы
Перебор и методы его сокращения
Алгоритмы на графах
Олимпиады по информатике
Алгоритмы решения задач
Заключение

Глава 2. ПЕРЕБОР И МЕТОДЫ ЕГО СОКРАЩЕНИЯ

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

2.1.1. Общая схема

Даны N упорядоченных множеств U1, U2, . UN (N - известно), и требуется построить вектор A=(a1, a2, . aN), где a1ОU1, a2ОU2, . aNОUN, удовлетворяющий заданному множеству условий и ограничений.

В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (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) выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим получить все такие узлы.

Рекурсивная схема реализации алгоритма.

for aОSi do Backtrack(векторккa,i+1);

Оценка временной сложности алгоритма. Данная схема реализации перебора приводит к экспоненциальным алгоритмам. Действительно, пусть все решения имеют длину N, тогда исследовать требуется порядка зS1з*зS2з*. *зSNз узлов дерева. Если значение Si ограничено некоторой константой С, то получаем порядка С N узлов.

2.1.2. Задача о расстановке ферзей

На шахматной доске N*N требуется расставить N ферзей таким образом, чтобы ни один ферзь не атаковал другого.

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

Отметим следующее. Все возможные способы расстановки ферзей - С N N^2 (около 4,4*10 9 для N=8). Каждый столбец содержит самое большее одного ферзя, что дает только N N расстановок (1,7*10 7 для N=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор (а1, а2, . aN) был решением, он должен быть перестановкой элементов (1, 2, . N), что дает только N! (4,0*10 4 для N=8) возможностей. Никакие два ферзя не могут находиться на одной диагонали, это сокращает число возможностей еще больше (для N=8 в дереве остается 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расстановок N ферзей на доске размером N*N. Использование подобного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем, что при этом удаляются поддеревья из дерева. Второе. Другим усовершенствованием является слияние, или склеивание, ветвей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или больше поддеревьев данного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склеивание, заметив, что если а1>йN/2щ, то найденное решение можно отразить и получить решение, для которого а1ЈйN/2щ. Следовательно, деревья, соответствующие, например, случаям а1=2 и а1=N-1, изоморфны.

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

Up:array[2..16] of boolean;

Down:array[-7..7] of boolean;

Vr:array[1..8] of boolean;

X:array[1..8] of integer;

Далее идет объяснение “кирпичиков”, из которых “складывается” решение (технология “снизу вверх”).

Основная процедура поиска одного варианта расстановки ферзей имеет вид:

procedure Solve(i:integer;var q:boolean);

if D_hod(i,j) then begin Hod(i,j);

if i о , 180 о и 270 о и зеркальных отражений относительно линий , разделяющих доску пополам (система координат фиксирована). Доказано, что в общем случае для доски N*N (N>1) для любой допустимой расстановки N ферзей возможны три ситуации:

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

Для отсечения симметричных решений на всем множестве решений требуется определить некоторое отношение порядка. Представим решение в виде вектора длиной N, координатами которого являются числа от 1 до N. Для ферзя, стоящего в i-й строке, координатой его столбца является i-я координата вектора. Для того, чтобы не учитывать симметричные решения, будем определять минимальный вектор среди всех векторов, получаемых в результате симметрий. Процедуры Sim1, Sim2, Sim3 выполняют зеркальные отображения вектора решения относительно горизонтальной, вертикальной и одной из диагональных осей. Известно (из геометрии), что композиция этих симметрий дает все определенные выше симметрии шахматной доски, причем не принципиально, в какой последовательности выполняются эти процедуры для каждой конкретной композиции. Проверка «на минимальность» решения производится функцией Cmp, которая возвращает значение true в том случае, когда одно из симметричных решений строго меньше текущего.

Окулов С.М. Решение сложных олимпиадных задач - файл n2.doc


Доступные файлы (6):

n1.doc 547kb. 16.11.2000 21:48 скачать
n2.doc 6930kb. 16.11.2000 21:51 скачать
n3.doc 6667kb. 16.11.2000 21:53 скачать
n4.doc 2327kb. 16.11.2000 21:53 скачать
n5.doc 3781kb. 16.11.2000 21:57 скачать
n6.doc 27kb. 16.11.2000 21:58 скачать

n2.doc

Глава 2. ПЕРЕБОР И МЕТОДЫ ЕГО СОКРАЩЕНИЯ

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

2.1.1. Общая схема

Даны N упорядоченных множеств U1, U2, . UN (N - известно), и требуется построить вектор A=(a1, a2, . aN), где a1ОU1, a2ОU2, . aNОUN, удовлетворяющий заданному множеству условий и ограничений.

В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (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) выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим получить все такие узлы.

Рекурсивная схема реализации алгоритма.

for aОSi do Backtrack(векторккa,i+1);

Оценка временной сложности алгоритма. Данная схема реализации перебора приводит к экспоненциальным алгоритмам. Действительно, пусть все решения имеют длину N, тогда исследовать требуется порядка зS1з*зS2з*. *зSNз узлов дерева. Если значение Si ограничено некоторой константой С, то получаем порядка С N узлов.

2.1.2. Задача о расстановке ферзей

На шахматной доске N*N требуется расставить N ферзей таким образом, чтобы ни один ферзь не атаковал другого.

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

Отметим следующее. Все возможные способы расстановки ферзей - С N N^2 (около 4,4*10 9 для N=8). Каждый столбец содержит самое большее одного ферзя, что дает только N N расстановок (1,7*10 7 для N=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор (а1, а2, . aN) был решением, он должен быть перестановкой элементов (1, 2, . N), что дает только N! (4,0*10 4 для N=8) возможностей. Никакие два ферзя не могут находиться на одной диагонали, это сокращает число возможностей еще больше (для N=8 в дереве остается 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расстановок N ферзей на доске размером N*N. Использование подобного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем, что при этом удаляются поддеревья из дерева. Второе. Другим усовершенствованием является слияние, или склеивание, ветвей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или больше поддеревьев данного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склеивание, заметив, что если а1>йN/2щ, то найденное решение можно отразить и получить решение, для которого а1ЈйN/2щ. Следовательно, деревья, соответствующие, например, случаям а1=2 и а1=N-1, изоморфны.

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

Up:array[2..16] of boolean;

Down:array[-7..7] of boolean;

Vr:array[1..8] of boolean;

X:array[1..8] of integer;

Далее идет объяснение “кирпичиков”, из которых “складывается” решение (технология “снизу вверх”).

end;
Основная процедура поиска одного варианта расстановки ферзей имеет вид:

procedure Solve(i:integer;var q:boolean);

if D_hod(i,j) then begin Hod(i,j);

if i о , 180 о и 270 о и зеркальных отражений относительно линий , разделяющих доску пополам (система координат фиксирована). Доказано, что в общем случае для доски N*N (N>1) для любой допустимой расстановки N ферзей возможны три ситуации:

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

Для отсечения симметричных решений на всем множестве решений требуется определить некоторое отношение порядка. Представим решение в виде вектора длиной N, координатами которого являются числа от 1 до N. Для ферзя, стоящего в i-й строке, координатой его столбца является i-я координата вектора. Для того, чтобы не учитывать симметричные решения, будем определять минимальный вектор среди всех векторов, получаемых в результате симметрий. Процедуры Sim1, Sim2, Sim3 выполняют зеркальные отображения вектора решения относительно горизонтальной, вертикальной и одной из диагональных осей. Известно (из геометрии), что композиция этих симметрий дает все определенные выше симметрии шахматной доски, причем не принципиально, в какой последовательности выполняются эти процедуры для каждой конкретной композиции. Проверка «на минимальность» решения производится функцией Cmp, которая возвращает значение true в том случае, когда одно из симметричных решений строго меньше текущего.

Новые книги

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

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

Вниманию читателей предлагается справочник по JavaScript.

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

Справочник создан на основе информации, предоставленной на сайте «Справочник Web-языков» www.spravkaweb.ru.

Дата выхода данной версии справочника: 12:33, 21 марта 2007.

Сокращение перебора

Сокращение перебора


2.1 Отсечение лишних вариантов

Рассмотрим задачу о расстановке n ферзей.

Задача 2 N ферзей. На шахматной доске размером n ґ n требуется расставить n ферзей, так, чтобы они не били друг друга.

Построим замкнутую формулировку этой задачи. Позицию будем записывать в виде набора, состоящего из координат x, y всех ферзей. Условие x i № x j ( y i № y j ) означает то, что i -ый и j -ый ферзи стоят на разных вертикалях (горизонталях). Условия x i +y i № x j +y j и x i -y i № x j -y j означают что i -ый и j -ый ферзи не стоят на одной диагонали. Получаем следующую замкнутую формулировку: Найти набор ( x 1 ,y 1 ,x 2 ,y 2 . x n ,y n ), x i , y i О <1 . n>, такой что: x i № x j , y i № y j , x i +y i № x j +y j , x i -y i № x j -y j для всех i, j О <1 . n>. Заметим, что среди координат x ферзей x 1 ,x 2 . x n ровно один раз встречается каждое из чисел 1,2 . n . Таким образом, достаточно перебирать только координаты y . Номера же ферзей можно рассматривать как координаты x . Итак, переформулируем задачу: Найти набор ( y 1 ,y 2 . y n ), y i О <1 . n>, такой что: y i № y j , i+y i № j+y j , i-y i № j-y j для всех i, j О <1 . n>.

Нарисуем пространство для n= 3 (это слишком небольшое число для данной задачи и в этом случае вообще нет решения, но нам важно понять, что представляет из себя пространство перебора). Пространство перебора – множество <( y 1 ,y 2 ,y 3 ) : y 1 ,y 2 ,y 3 О <1,2,3>>. На рисунке элементы пространства перебора отмечены точками.


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

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

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

Таким образом, пространство перебора всегда – параллелепипед. (В общем случае – множество наборов <( y 1 . y n ) : y 1 О Y 1 , y n О Y n >, Y 1 , . Y n Н Y .) Такое пространство можно задать, задав множества Y 1 , . Y n . В нашем случае это означает, что мы должны указать, какие значения разрешены для каждого из ферзей. Так мы приходим к компактному представлению пространства перебора, с которым и будем работать в дальнейшем.

На рисунках 4, 5, 6 показаны те же пространства перебора, что и на рисунках 1, 2, 3 соответственно. Там, где значение для ферзя запрещено – квадрат изображён чёрным цветом, где разрешено – белым. В дальнейшем мы будем вертикали, соответствующие ферзям изображать вплотную (у нас получится шахматная доска).

Проследим, какими будут первые полностью построенные позиции при приведённом алгоритме. Сначала будет рассмотрен вариант, когда все ферзи занимают положение 1, потом последний ферзь займёт положение 2 и т.д. Но постойте! Ведь уже когда первый ферзь занимает положение 1, то все позиции, в которых второй ферзь занимает положение 1 или 2 будут заведомо неприемлемы. Т.о. первые 2 · n n- 2 вариантов будут рассмотрены впустую. Но ведь это можно было заметить уже при расстановке второго ферзя.

Иначе говоря, из пространства перебора заведомо можно удалить варианты, когда второй ферзь занимает положение 1 или 2. Для случая n= 3 сокращённое пространство перебора показано на рис. 3.

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

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

При сокращении пространства перебора надо иметь в виду насколько сокращается пространство и соотносить размер этого сокращения с затратами на его реализацию. Если размер сокращения не велик по сравнению с общим объёмом перебора, то обычно не стоит ``городить огород'' и реализовывать такое сокращение, так как затраты на выполнение более сложной схемы перебора могут ``съесть'' весь выигрыш от сокращения. Кроме того, каждое усложнение алгоритма – лишняя возможность сделать ошибку.

2.2 Использование симметрии

Приём использования симметрии дал возможность в задаче о шашках несколько раз переформулировать задачу и предельно сократить пространство перебора. Действительно, сначала мы использовали симметрию различных последовательностей одних и тех же ходов, потом симметрию различных строк (столбцов) доски, потом центральную симметрию и поворот на 90 ° .

Симметрию часто удаётся использовать и в процессе перебора (а не только при переформулировке задачи). Так например, в задаче о ферзях за счёт симметрии можно считать, что первый ферзь находится на нижней половине доски. Это сократит перебор в два раза. Очень сильно сокращается перебор за счёт симметрии в рассматриваемой в следующем разделе задаче о раскраске карты.

2.3 Группирование элементов

Часто при проверке перебираемых вариантов многие операции повторяются для разных элементов пространства перебора. Напрашивается следующая идея оптимизации: выполнять эти операции сразу для групп элементов. Причём чем больше группы, тем лучше. По-существу, сокращение пространства перебора в последнем рассмотренном варианте задачи о ферзях осуществляется как раз за счёт отсечения сразу группы элементов. Кроме того, позиция тоже строится не для каждого варианта с самого начала, а насколько это возможно сразу для групп вариантов. Это делают операторы ферзь[1] := i1; . , которые виднуты на максимально верхний уровень.

В результате группирования алгоритм может существенно измениться. Выразительные примеры (5 и 6) приведены в следующем разделе. Следующая часть, Содержание

Перебор и его сокращение

Решение этой задачи на компьютере не представляет большой сложности. В принципе, можно тупо перебрать все возможные варианты расстановки ферзей на доске, а затем определить подходящие. Написать такую программу не сложно, но возникает вопрос: "Сколько существует вариантов и сколько времени нужно для их перебора?" Честно говоря, считать точное количество вариантов мне было лень, но, судя по всему, ждать придется долго.

Поэтому, нужно каким-то образом определить на какую клетку ставить следующего ферзя. Например, ставить несколько ферзей в одну линию бессмысленно (это противоречит условию). Если попробовать решить задача вручную, то становится понятно, что расставить 6 - 7 ферзей не сложно. Но после этого свободных клеток (которые не "бьются" ни одним из ферзей) нет. Следовательно, ферзей нужно расставлять так, чтобы они били как можно меньше клеток. Очень хорошо если несколько разных ферзей "бьют" одни и те же клетки, но при этом не "бьют" друг друга.

Дальше все очень просто. Нужно перебрать по очереди все свободные клетки доски (те, которые не "атакует" ни один ферзь) и посчитать, сколько свободных клеток "будет" бить ферзь из данной.

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

Для решения задачи нам понадобиться массив accessibility[8][8]. В нем мы будем хранить информацию о том, свободна данная клетка или нет. Таким образом, для того чтобы определить сколько клеток будет "бить" ферзь из заданной, нам нужно перемещать ферзя по всем возможным направлениям (их 8) и считать свободные клетки. Для перемещения ферзя удобно использовать два одномерных массива, элементы которых указывают на сколько клеток нужно сместить ферзя при движении в выбранном направлении. Я определил их таким образом:

Нулевой элемент соответствует перемещения вправо. Первый - по диагонали вправо и вверх, и т.д.

Для перемещения ферзя, например, на одну клетку вниз можно записать

Далее нужно выбрать клетку, которой соответствует наименьшее количество "выбитых" свободных клеток. Если таких клеток несколько, то выбираем одну из них случайным образом и ставим на неё ферзя (при этом нужно отметить в массиве accessibility, что соответствующие клетки заняты). Процесс повторяется до тех пор, пока не будут установлены все 8 ферзей.

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

Виды переборов на гитаре. 21 схема игры перебором.

Виды переборов

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

Легкие и простые переборы

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

Наиболее легкими из представленного списка однозначно являются «Шестерка» и «Четверка», поскольку не имеют в своем составе большое количество струн. Первым способом исполняется известная песня группы Сплин «Бог устал нас любить», а вторым – Yesterday группы «The Beatles».

Обозначения на схемах переборов

В левой части схемы вертикально расположенные цифры обозначают струны с 6-ой по 1-ую. Красными точками обозначена схема игры перебором.

Перебор 4 «Четверка» схемы

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

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

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

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

Еще один способ играть «Четверку» — это сначала дергать бас, а потом последовательно проигрывать все струны с первой по третью.

Обратная четверка


А это уже более сложный вариант перебора «Четверки». Для него потребуется некоторое время потренировать координацию и даже, возможно, играть его медленно. Играется он примерно таким образом: сначала дергайте одновременно басовую, первую и вторую струну – они должны зазвучать вместе. После этого дергайте третью струну – играть должна только она. На третий такт дергайте опять первую и вторую, без баса. И на четвертый – только третью.

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

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

Б3213

Немного модифицированный вариант привычного перебора, направленный на более богатое звучание. Его схема выглядит так: бас, потом третья, потом одновременно звучит вторая и первая, потом третья снова. Это делает звук аккорда более богатым и интересным.

Перебор 6 «Шестерка» схемы

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

Б32123

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

Б321321

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

Б12Б12 (612512)

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

Песни для отработки:

1. The Animals – House of the Rising Sun;
2. Сплин – Я хотел бы пройти;
3. Любэ – Там за туманами;
4. Петлюра – Солдат.

Перебор 8 «Восьмерка» схемы

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

Б3231323

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

Б3212323

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

Б3231232

Еще одна вариация перебора. Схема строится на следующем паттерне: бас, потом третья, вторая, третья, первая, вторая, третья и вторая струна.

Б313Б312 — для песни Костер

Данный вид перебора прекрасно иллюстрирует многообразие их видов – это специфичная манера игры, которая была придумана Андреем Макаревичем специально для песни «Костер», аккорды к которой можно найти на сайте. Схема выглядит так: сначала играется бас, потом последовательно третья, первая, третья – и потом опять бас, третья – первая и вторая струны. Это не очень простой рисунок, который, тем не менее, будет не очень сложно освоить при должной тренировке.

12312312

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

Первая, вторая, третья, первая, вторая, третья, первая, вторая.

В целом, ничего сложного – по факту, это повторение одного и того же мелодического рисунка несколько раз.

Длинная Восьмерка 6-4-3-2-1-2-3-4

Свое название этот вид перебора получил, потому что при его игре по факту надо пройтись почти по всем струнам. Выглядит схема так: Бас – четвертая – третья – вторая – первая – вторая – третья – четвертая. Таким образом, играются аккорды «Я верю».

Б1234123

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

6-4-3-4 и 5-4-3-4 — Вороны-ДДТ

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

Песни для отработки:

1. Машина Времени – Костер (аккорды);
2. ДДТ – Вороны;
3. Фактор 2 – Одинокая звезда;
4. Ляпис Трубецкой – Я верю;
5. Сектор Газа – Лирика;
6. Бременский Музыканты – Солнце Взойдет.

Вальсовые переборы

Специфичный тип переборов, характерный для размера 3/4. Именно в нем играются, например, аккорды «Прогулки по воде» — знаменитой песни группы Наутилус Помпилиус. Стоит сказать, что в данном случае играть надо с отчетом «Раз-два-три» — ритме вальса, откуда и пошло название манеры исполнения. То есть бас будет на счет «раз», а остальное – на «два» и, соответственно, «три».

Перебор Б(21)(21)

Схема выглядит таким образом: Бас – и дважды надо дернуть первую и вторую струну. Помните о ритме вальса – и тогда все будет звучать как надо.


Перебор Б(321)(321)

Модифицированный вариант первого способа. Схема следующая: бас – дважды надо дернуть одновременно три верхние струны.

Еще вальсовый Б3(21)

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

Песни для отработки:

1. Наутилус Помпилиус – Прогулки по воде;
2. Олег Митяев – Изгиб гитары желтой;
3. Булат Окуджава – Грузинская песня;
4. Крематорий – Мусорный Ветер;
5. Юрий Визбор – Милая моя.

Заключение

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

3. Перебор и методы его сокращения

    Павел Пушешников 1 лет назад Просмотров:

1 3. Перебор и методы его сокращения Обучение программированию, алгоритмизации сверхсложное дело*. Знание конструкций языка программирования, способов описания алгоритмов не решает проблемы. Требуется проделать огромную работу для того, чтобы сформировать стиль мышления, присущий специалисту по информатике. Этот стиль характеризуется, на наш: взгляд, двумя основополагающими моментами: язык информатики (он не зависит от конкретного языка программирования) должен стать естественным языком выражения своих мыслей (рассуждений); методология решения задач, присущая информатике, должна быть освоена не на фактографическом уровне. Тема «перебор и методы его сокращения» является одной из ключевых в этой системе обучения. Весь процесс обучения построен через решение задач, естественно, с использованием компьютера. 3.. Перебор с возвратом (общая схема) Даны N уопрядоченных множеств U v U 2. U N (N известно), и требуется построить вектор А=(а, а 2. a N ), где удовлетворяющий заданному множеству условий и ограничений. Может быть, это явилось одной из причин, по которой, после появления мощных персональных компьютеров, образовательная информатика с таким энтузиазмом «бросилась» в изучение так называемых информационных технологий.

3 3. Перебор и методы его сокращения Примеры задач для разбора общей схемы перебора Пример «Задача о расстановке ферзей». Для разбора общей схемы одной из лучших задач является задача о расстановке ферзей. На шахматной доске N*N требуется расставить N ферзей таким образом, чтобы ни один ферзь не атаковал другого. Отметим следующее. Все возможные способы расстановки ферзей С^2 (около 4,4* 9 для N=8). Каждый столбец содержит самое большее одного ферзя, что дает только N N расстановок (,7* 7 для iv=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор (a t, a 2. a N ) был решением, он должен быть перестановкой элементов (,2. N), что дает только N\ (4,* 4 для N==8) возможностей. Никакие два ферзя не могут находиться на одной диагонали, это сокращает число возможностей еще больше (для 2V=8 в дереве остается 26 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расстановок N ферзей на доске размером N*N. Использование подобного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем, что при этом удаляются поддеревья из дерева. Второе. Другим усовершенствованием является слияние, или склеивание, ветвей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или больше поддеревьев данного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склеивание, заметив, что если af^n/2], то найденное решение можно отразить и получить решение, для которого a^n/2]. Следовательно, деревья, соответствующие, например, случаям а 2 и UJ^ N, изоморфны. Следующие рисунки иллюстрируют сказанное и поясняют ввод используемых структур данных. Структуры данных. Up: Array [2..6] Of Boolean ; < *Признак занятости диагоналей первого типа. *>Down:Array[-7.. 7] Of Boolean; <*Признак занятости диагоналей второго типа. *>Vr:Array[I..8] Of Boolean; <*Признак занятости вертикали. *>X: Array [..8] Of Integer;

4 82 3. Перебор и методы его сокращения Далее идет объяснение «кирпичиков», из которых «складывается» решение (технология «снизу вверх»). Procedure Hod(i,j:Integer); <*Сделать ход.*>X[d] :=j;vr[j] : =False;Up [i+j] :=False; Down[i-j]:=False; Procedure O_hod (i,j:integer); <*отменить ход.*>Vr [j]:=true;up[i+j]:=true;down[i-j]:=true; Function D_hod(i,j:Integer):Boolean; <*Проверка допустимости хода в позицию (i,j). *>D_hod:=Vr[j] And Up[i+j] And Down [i-j] ; Основная процедура поиска одного варианта расстановки ферзей имеет вид: Procedure Solve(i:Integer;Var q:boolean); Var j:integer;

5 3. Перебор и методы его сокращения 83 j:=; Repeat Inc (j);q:=false; <*цикл по вертикали. *>If D_hod (i,j) Then Hod(i,j); If i 6 84 3. Перебор я методы его сокращения фиксирована). Доказано, что в общем случае для любой допустимой расстановки N ферзей возможны три ситуации: при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается; поворот на 9 и его отражение дают еще две расстановки ферзей; три поворота и четыре отражения дают новые расстановки., Для отсечения симметричных решений на всем множестве решений требуется определить некоторое отношение порядка. Представим решение в виде вектора длиной N, координатами которого являются числа от до N. Для ферзя, стоящего в -й строке, координатой его столбца является i-я. координата вектора. Для того, чтобы не учитывать симметричные решения, будем определять минимальный вектор среди всех векторов, получаемых в результате симметрии. Процедуры Siml, Sim2, Sim3 выполняют зеркальные отображения вектора решения относительно горизонтальной, вертикальной и одной из диагональных осей. Известно (из геометрии), что композиция этих симметрии дает все определенные выше симметрии шахматной доски, причем не принципиально, в какой последовательности выполняются эти процедуры для каждой конкретной композиции. Проверка «на минимальность» решения производится функцией Стр, которая возвращает значение True в том случае, когда одно из симметричных решений строго меньше текущего решения. Возможный вариант реализации (отсечение на выводе решений) приведен ниже по тексту. Type TArray=Array [I..N] Of 'Integer; Procedure Siml(Var X:TArray); Var i:integer; For i:=l To N Do X[i] : =N-X[i]+ ; Procedure Sim2 (Var X:TArray) ; Var i, r:integer; For i:=l To N Div 2 Do r:=x[i]; X[i]:=X[N-i+];X[N-i+]:=r; Procedure Sim3(Var X:TArray);

7 3. Перебор и методы его сокращения 8 Var YiTArray; i:integer; For i:=l To N Do Y[X[i]J:=i; X:=Y; Function Cmp (X,Y:TArray) -.Boolean; Var i:integer; i : = ; While (i n Then Cmp:=False Else If Y[i] 8 86 3. Перебор и методы его сокращения Примечание Программу решения задачи о шахматных ферзях можно написать по-разному. Ниже по тексту приведено одно из возможных решений. Решение очень компактное, по-своему изящное, но не будем комментировать его. Попробуйте разобраться с ним и ответить на вопрос: в чем заключается отличие в стилях при написании программ в этом примере и в целом в данном учебнике. Program Ferz; Uses Crt; Const N=8; Var B:Array[..N] Of Integers- Procedure Rf (i:integer) ; Var j,k,p,t:integer; For j:=l To N Do B[i]:=j;k:=l;p:=O; While (k 9 3. Перебор и методы его сокращения 87 да конем доски (решение в «лоб»). Затем оцениваем порядок сокращения перебора исходя из условия логика выбора очередного хода коня. Будем считать, что поля для хода выбираются по часовой стрелке. Объяснение иллюстрируется следующими рисунками. Структуры данных. Const N= ; M= ; Dx:Array[..8] Of Integer=(

2,-,,2,2,,--2); Dy:Array[..8] Of Integer=(,2,2,,-,-2,-2,-); Var A:Array[-l..N+2,-..M+2] Of Integer; t:integer; Основной фрагмент реализации процедура Solve. Procedure Solve(к,у,q:Integer); Var z,i,j:integer; A[x,y]:=q; If q=n*m Then Inc (t) Else For z:=l To 8 Do i:=x+dx[z];j :=y+dy[z]; If A[i,j]=O Then Solve (i, j,q+l) A[x,y]:=; Часть текста из основной программы имеет вид: For i:=-l To N+2 Do For j:=-l To M+2 Do A[i,j]:=-l; <*3аписываем "барьерные" элементы, тем самым исключая лишние операторы If, утяжеляющие текст программы. *>For i:=2 То N Do ' For j:=l To M Do A[i,j] : = / t:=; For i:= To N Do For j : = To M Do Solve (i,j,) ;

12 9 3. Перебор и методы его сокращения Procedure Print; <*'Вывод матрицы А - метками выделен путь выхода из лабиринта.*>; Procedure Solve(х,у,k:Integer); <*k - номер шага, х,у - координаты клетки. *>Var i:integer; A[x r y]:=k; If (x=xk) And (y=yk) Then Print Else For i:=l To 4 Do IfA[x+Dx[±],y+Dy[i]]=O Then Solve (x+dx[i],y+dy[i],k+l) ; A[x r y]:=; Init; Solve(xn,yn,); End. С помощью данной схемы находятся все возможные варианты выхода из лабиринта. Их очередность определяется правилом (задается массивами констант Dx, Dy) просмотра соседних клеток. Если требуется найти один выход из лабиринта, то требуется, естественно, изменить решение. Проделайте работу, сохранив при этом структурный вид программного кода. Второй способ решения задачи о лабиринте (поиск кратчайшего по количеству перемещений пути) называют «методом волны». Его суть. Начальную клетку помечают, например, меткой со значением, а затем значение метки увеличивается на единицу на каждом шаге. Очередное значение метки записывается в свободные клетки, соседние с клетками, имеющими предыдущую метку. В любой момент времени множество клеток, не занятых препятствиями, разбивается на три класса: помеченные и изученные; помеченные и неизученные и непомеченные. Для хранения клеток второго класса лучше всего использовать структуру данных «очередь» (мы предполагаем, что она изучена ранее, например, по книге автора «Основы программирования»). Процесс заканчивается при достижении клетки выхода из лабиринта (есть путь)

13 3. Перебор и методы его сокращения 9 или при невозможности записать очередное значение метки (тупик). На рисунке иллюстрируется этот процесс. Темные клетки означают препятствия. Начальная клетка находится вверху слева, конечная внизу справа. Кроме того, из рассмотрения примеров должно следовать понимание того факта, что выход из лабиринта имеет кратчайшую длину. Program Labirint; Const NMax=. ; MMax=. ; Dx:Array[..4] Of Integer^(-. ) ; Dy-.Array [..4] Of Integer^ (. -) ; Type MyArray=Array[O..NMax+. MMax+] Of Integer; Var A:MyArray; <*Глобальные переменные. *>N,M: Integer; xn,yn,xk,ук:integer; Function Solve:Boolean; Type Och=Array[l..Шах*ММах. 2] Of Integer; Var tfi,j,ykr,ykw:integer; О:Och; <*Очередь. *>Y-.Boolean; A[xn,yn]:=/ ykr:=<*указатель чтения из очереди. *>; ykw:=l; <*Указатель записи в очередь.*>Y:=False; <*Начальное присвоение. *>О[ykw,]:=хл;[ykw,2]:=уп; <*3аносим координаты начальной клетки в очередь. *>While (ykr 14 92 3. Перебор и методы его сокращения Inc(ykw) ;O[ykw,l] :=i+dx[t] ; О[ykw,2]:=j+Dy[t]; <*'Записываем координаты клетки в очередь. *>Solve:=Y; <*'Результат работы функции Solve. *>Основная программа имеет вид. Init; <*Ввод лабиринта, координат начальной и конечной клеток. Текст процедуры не приводится. *>Assign (Output,'Output.txt' );Rewrite(Output); <*'Выводим результат (массив А) в файл.*>If Solve Then Print <*Текст процедуры Print в силу её очевидности не приводится. *>Else WriteLn ('Нет пути'>; Close (Output); End. Модифицировать предыдущее решение так, чтобы находился не один путь, а, например, t путей, если они существуют. Пример 4 «Задача о рюкзаке (перебор вариантов)». В рюкзак загружаются предметы N различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака W. Каждый предмет типа I имеет вес w t и стоимость v t ( =,2. N). Требуется определить максимальную стоимость груза, вес которого равен W. Обозначим количество предметов типа i через k t, тогда требуется максимизировать v *k +v 2 *k v N *k N при ограничениях w *k +w 2 *k w N *k N =W, где k i целые (O^k^lW/wJ), квадратные скобки означают целую часть числа. Рассмотрим простой переборный вариант решения задачи, работоспособный только для небольших значений N (определить, для каких?). Итак, данные: Const MaxN=. ; Var N,N:Integer; <^Количество предметов, максимальный вес. *>Weight,Price:Array[..MaxN] Of Integer;

15 3. Перебор и методы его сокращения 93 Best,Now:Array[I..MaxN] Of Integer; <* Наилучшее г текущее решения. *>MaxPrice:Longlnt; <^Наибольшая стоимость. *>Решение, его основная часть процедура перебора: Procedure Solve(k,w:Integer;st:Longlnt); <*k - порядковый номер группы предметов, w - вес, который следует набрать из оставшихся предметов, st - стоимость текущего решения. *>Var i:integer; If (k>n) And (st>maxprice) Then <*Найдено решение. *>Best:=Now;MaxPrice:-st; End Else If k 16 94 3. Перебор и методы его сокращения В:Array[..Мах. Max] Of Byte; <^Вспомогательный массив, элементы каждой строки матрицы сортируются в порядке возрастания, но сами элементы не переставляются, а изменяются в матрице В номера столбцов матрицы А.*>Пример. Ниже приведены матрицы Аи В (после сортировки элементов каждой строки матрицы А). Примечание обозначено бесконечное расстояние. Way,BestWay:Array[..Max] Of Byte; <*Хранится текущее решение и лучшее решение. *>Nnew:Array[I..Max] Of Boolean; <*3начение элемента массива False говорит о том, что в соответствующем городе коммивояжер уже побывал. *>BestCost:Integer; <*Стоимость лучшего решения. *>Идея решения. Пусть мы находимся в городе с номером v. Наши действия. Шаг. Если расстояние (стоимость), пройденное коммивояжером до города с номером и, не меньше стоимости найденного ранее наилучшего решения (BestCost), то следует выйти из данной ветви дерева перебора. Шаг 2. Если рассматривается последний город маршрута (осталось только вернуться в первый город), то следует сравнить стоимость найденного нового решения со стоимостью лучшего из ранее найденных решений. Если результат сравнения положительный, то значения BestCost и BestWay следует изменить и выйти из этой ветви дерева перебора. Шаг 3. Пометить город с номером v как рассмотренный, записать этот номер по значению Count в массив Way. Шаг 4. Рассмотреть пути коммивояжера из города v в ранее не рассмотренные города. Если такие города есть, то перейти на эту же логику с измененными значениями v, Count, Cost, иначе на следующий шаг.

17 3. Перебор и методы его сокращения 9 Шаг. Пометить город v как нерассмотренный и выйти из данной ветви дерева перебора. Прежде чем перейти к обсуждению логики, целесообразно разобрать этот перебор на примере. На рисунке приведен пример и порядок просмотра городов. В кружках указаны номера городов, рядом с кружками суммарная стоимость проезда до этого города из первого. Итак, запись логики. Procedure Solve(v,Count:Byte;Cost:Integer); <*v - номер текущего города; Count - счетчик числа пройденных городов; Cost - стоимость текущего решения. *>Var i:integer; If Cost>BestCost Then Exit; <*Стоимость текущего решения превышает стоимость лучшего из ранее полученных. *>If Count=N Then Cost:=Cost+A[v,]/Way[N]:=v; <*Последний город пути. Добавляем к решению стоимость перемещения в первый город и сравниваем его с лучшим из ранее полученных. *>If Cost 18 96 3. Перебор и методы его сокращения Nnew[v]:=False/Way[Count]:=v; <*Город с номером v пройден, записываем его номер в путь коммивояжера. *>For i:= То N Do If Nnew[B[v,i]] Then Solve (B[v,i], Count+,Cost+A[v r B[v,i]]); <*Поиск города, в который коммивояжер может пойти из города, с номером v.*>Nnew[v] : =True; <^Возвращаем город с номером v в число непройденных. *>Первый вызов Solve(l,l,). Разработка по данному «шаблону» работоспособной программы техническая работа. Если вы решитесь на это, то есть смысл проверить ее работоспособность на следующем примере (матрица А приведена ниже). Решение имеет вид , его стоимость Оцените время работы программы. Если у вас мощный компьютер, то создайте матрицу А[. ] и попытайтесь найти наилучшее решение с помощью разобранного метода. Заметим, что набор 2 чисел утомительное занятие и разумная лень «двигатель прогресса» Динамическое программирование Идея метода. Это важнейший раздел изучаемой темы, поэтому вполне применим принцип: чем больше разнообразных задач, тем лучше. Разбор основной идеи метода и ее обсуждение можно сделать на классической задаче о Черепашке. Черепашке необходимо попасть из пункта А в пункт В. На каждом углу она может поворачивать только на север или только на восток. Время движения по каждой улице указано на рисунке. Требу-

19 3. Перебор и методы его сокращения 97 ется найти минимальное время, за которое Черепашка может попасть из пункта А. в пункт В. Путь, показанный на рисунке линиями со стрелкой, требует 2 единицу времени. Отметим, что каждый путь состоит из 6 шагов: трех на север и трех на восток. Количество возможных путей Черепашки 2 (С 3 в). Мы можем перебрать все пути и выбрать самый быстрый. Это метод полного перебора (ответ 2). Для вычисления каждого времени требуется пять операций сложения, а для нахождения ответа операций сложения и 9 операций сравнения. Задача решается вручную. Однако при N, равном 8, у Черепашки уже 287 путей. Подсчет времени для каждого пути требует операций сложения, а в целом 93 сложений и 2869 сравнений, то есть порядка 2 операций. Компьютер при быстродействии операций в секунду найдет решение за.2 секунды, а человек? Предположим, что N равно 3, тогда количество различных путей 6!*(3!*3!). Это очень большое число, его порядок 7. Количество операций, необходимых для поиска решения, равно 6* 7. Компьютер с быстродействием операций в секунду выполнит за год порядка 3.2* 3 операций (подсчитайте). А сейчас нетрудно прикинуть количество лет, требуемых для решения задачи. Вернемся к исходной задаче. Начнем строить путь Черепашки от пункта В. Каждому углу присвоим вес, равный минимальному времени движения Черепашки от этого угла до пункта В. Как его находить? От углов X, Y решение очевидно. Для угла Z время движения Черепашки в пункт В через угол X равно единицам, а через угол Y единицам. Берем минимальное значение, т. е. вес угла будет равен. Продолжим вычисления. Их результаты приведены на рисунке. Путь, отмеченный стрелками, является ответом задачи. Оценим количество вычислений. Для каждого угла необходимо выполнить не более двух операций сложения и одной операции сравнения, т. е. три операции. При N, равном 3, количество операций 3*3*3, это меньше, и компьютеру потребуется ме-

20 98 3. Перебор и методы его сокращения ныне одной секунды. Итак, много лет при N=3 и секунда при iv=3. Идея второго способа решения задачи основана на методе динамического программирования. Заслуга его открытия принадлежит американскому математику Ричарду Беллману. Выделим особенность задачи, которая позволяет решить ее описанным способом. Мы начинаем с угла В, и для каждого угла найденное число является решением задачи меньшей размерности. Поясним эту мысль. Если бы мы решали задачу поиска пути Черепашки из пункта Т в пункт В, то найденное число 7 решение задачи. Для каждого угла найденное значение времени не изменяется и может быть использовано на следующих этапах Примеры задач для разбора идеи метода динамического программирования Пример «Треугольник». На рисунке изображен треугольник из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающемся на основании треугольника. Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо. Число строк в треугольнике > и 21 3. Перебор и методы его сокращения 99 For j:=l То i Do R[i,j ]=max(d[i,j ]+R[i-l,j ], D[±,j]+R[i-l,j-l]); где шах функция вычисления максимального из двух чисел. Осталось найти наибольшее значение в последней строке матрицы R, оно равно 3. Пример 2 «Степень числа». Даны два натуральных числа N и k. Требуется определить выражение, которое вычисляет k N. Разрешается использовать операции умножения и возведения в степень, круглые скобки и переменную с именем k. Умножение считается одной операцией, возведению в степень q соответствует q операция. Найти минимальное количество операций, необходимое для возведения в степень N. Желательно сделать это для как можно больших значений N. Так, при N= требуются три операции (k*k) 2 *k. Определим массив Ор, его элемент Op[i] предназначен для хранения минимального количества операций при возведении в степень i (Op[l]=). Для вычисления выражения, дающего N-ю степень числа k, арифметические операции применяют в некоторой последовательности, согласно приоритетам и расставленным скобкам. Рассмотрим последнюю примененную операцию. Если это было умножение, тогда сомножителями являются натуральные степени числа h, которые в сумме дают N. Степень каждого из сомножителей меньше N, и ранее вычислено, за какое минимальное число операций ее можно получить. Итак: opnl: =Min <по всем р: l

22 3. Перебор и методы его сокращения Op[i] :=Min(Op[i], Op [j ]+Ор [i-j ]+) ; If i Mod j= Then Op[i] :=Min (Op[i], Op[i Div j]+j-l) / Пример 3 «Алгоритм Нудельмана-Вунша» (из молекулярной биологии). Молекулы ДНК содержат генетическую информацию. Моделью ДНК можно считать длинное слово из четырех букв (А, Г, Ц, Т). Даны два слова (длины М и N), состоящие из букв А, Г, Ц, Т. Найти подпоследовательность наибольшей длины, входящую в то и другое слово. Пусть есть слова ГЦА- ТАГГТЦ и АГЦААТГГТ. Схема решения иллюстрируется следующим рисунком. На рисунке закрашены клетки, находящиеся на пересечении строки и столбца с одинаковыми буквами. Принцип заполнения таблицы W следующий: элемент W[i,j] равен наибольшему из чисел W[i-l,j], W[i,j-], а если клетка закрашена, то и W[i-l,j-l]+l. Формирование первой строки и первого столбца выполняется до заполнения таблицы и осуществляется так: единицей отмечается первое совпадение, затем эта единица автоматически заносится во все оставшиеся клетки. Например, W[3,l] первое совпадение в столбце, затем эта единица идет по первому столбцу. Подпоследовательность формируется при обратном просмотре заполненной таблицы от клетки, помеченной максимальным значением. Путь это клетки с метками, отличающимися на единицу, буквы выписываются из закрашенных клеток. Последовательность этих букв ответ задачи. Для нашего примера две подпоследовательности: ГЦААГГТ и ГЦАТГГТ. Фрагмент основной логики. For i:=l To Length (SI) Do For j:=l To Length (S2) Do A[i,j] :=Max(A[i-l,j],A[i,j-l]) ;

23 3. Перебор и методы его сокращения If SI [i]=s2 [j] Then A[i, j] :=Max (A[i, j], A[i-l,j-l]+l) ; WriteLnfОтвет: ', A [Length (SI), Length (S2) ]) ; Пример 4 «Разбиение выпуклого N-угольника». Дан выпуклый JV-угольник, заданный координатами своих вершин в порядке обхода. Он разрезается N-2 диагоналями на треугольники. Стоимость разрезания определяется суммой длин всех использованных диагоналей. Найти разрез минимальной стоимости. Идея решения разбирается с использованием следующего рисунка. Обозначим через S[k,l] стоимость разрезания многоугольника A[k,l] диагоналями на треугольники. При l=k+l или k+2 S[k,l]=O, следовательно, l>k+2. Вершина с номером i, i изменяется от k+ до, определяет какое-то разрезание многоугольника A[k,l]. Стоимость разрезания определим как: S[k,l]

min. При этом следует учитывать, что при i=k+l диагональ является стороной многоугольника и ее длина считается равной нулю. Аналогично при i=l l. Пример «Задача о камнях». Из камней весом р,р 2. p N набрать вес W или, если это невозможно, максимально близкий к W снизу вес. Рассмотрим идею решения на следующих данных: N равно, Pj=, Р 2 =Ч, Р 3 =9, р 4 =, р =3, W=9. Сформируем матрицу А (A:Array[l..N. W] Of Integer), в которой номер строки соответствует номеру камня, а номер столбца набираемому весу. В нулевой столбец запишем нули, в первую строку (по столбцам) до веса первого камня нули, а затем вес первого камня (пытаемся набрать требуемый вес одним камнем). Во второй строке фиксируем результат набора веса с помощью двух камней и т. д. После заполнения А имеет вид, показанный на рисунке. Вес 9 набрать нельзя, ближайший снизу вес 8.

24 2 3. Перебор и методы его сокращения Для заполнения текущей строки достаточно знать только предыдущую строку (результат решения задачи меньшей на единицу размерности), а в элементе массива A[i,j] записывается решение задачи о камнях при N i и W=j. Программный код решения компактен и не требует пояснений. Procedure Solve; Var i,j:integer; For i:=2 To N Do For j:= To W Do If j-p[i]>= Then A[i,j]:= Max (A[i-l,j], A[i-l,j-P[i]]+P[i]) Else A[i,j]:=A[i-l,j]; Для ответа на вопрос, «из каких камней набирается вес», решение необходимо дополнить простой рекурсивной процедурой. В таблице курсивом выделена часть элементов, задействованных при работе процедуры, а жирным шрифтом те значения i и /', при которых осуществляется вывод веса камня P[i] Procedure Way(i,j:Integer); If (i=l) And (A[i,j]=O) Then Exit Else If i=l Then Way (i,j-p[i] ) ; Write(P[i],' ');End Else If A[i,j]OA[i-l,j] Then Way(i,j-P[i]) ;Write(P[i],' ') ;End Else Way(i-l,j) ; Пример 6 «Задача о рюкзаке (к весу камней добавляется и их стоимость)». Напомним формулировку задачи. В рюкзак загружаются предметы N различных типов (количество предметов каждого типа не ограничено). Вес рюкзака должен быть меньше или равен W. Каждый предмет типа i имеет вес w i и

25 3. Перебор и методы его сокращения 3 стоимость v t ( =,2. N). Требуется определить максимальную стоимость груза, вес которого не превышает W. Рассмотрим случай, когда вес рюкзака в точности равен W. Обозначим количество предметов типа i через k p тогда требуется максимизировать v *k +v 2 *k 2 + +v N *k N при ограничениях u> *k +w 2 *k w N *k N =W, где k t целые ( 26 4 3. Перебор и методы его сокращения формализацией) на каждом шаге. В круглых скобках указаны стоимости соответствующих выборов, в квадратных скобках максимальная стоимость данного заполнения рюкзака. «Жирными» линиями выделен способ наилучшей загрузки рюкзака. Текст решения. Const MaxN=. ; МахК=. ; Type Thing=Record W,V:Nord; Var A:Array[..MaxN. MaxK] Of Word; P:Array[..MaxN] of Thing; Old,NewA:Array[..MaxK] Of Longlnt; N,W: Integers- Procedure Solve; Var k,i,j:integer; FillChar(Old,SizeOf(Old),) ; For k:=l To N Do < *Цикл по шагам. *>FillChar(NewA,SizeOf(NewA),); For i:= To N Do <*Цикл по состояниям шага. *>For j := To i Div P[k].W Do <*Цикл по вариантам решения - количеству предметов каждого вида.*>If j*p[k].v+d[i-j*p[k].w]>=newa[i] Then NewA[i] :=j*p[k].v+old [i-j *P [k].n] ; A[k,i]:=j; <*3десь j количество предметов?*>Old:=NewA; Вывод наилучшего решения. Procedure OutWay(k,l:Integer); If k= Then Exit Else OutWay(k-l,l-A[k,l]*P[k].W) ; <*A здесь вес. *>Write (A[k r ],' '); Первый вызов OutWay(N,W). Эту схему реализации принято называть «прямой прогонкой». Ее можно изменить. Пусть

27 3. Перебор и методы его сокращения пункт два формализации задачи звучит следующим образом. Состояние y L на шаге I выражает суммарный вес предметов, решение о загрузке которых принято на шагах i, i+. N при этом j/ i =W j/.=,i. w при =2,3. N. В этой формулировке схему реализации называют «обратной прогонкой». 3.. Метод ветвей и границ Идея метода ветвей и границ обычно излагается по работе Дж. Литтла. Не отступим и мы от этой традиции. Суть идеи проста. Все перебираемые варианты следует разбить на классы (блоки), сделать оценку снизу (при минимизации) для всех решений из одного класса, и если она больше ранее полученной, то отбросить все варианты из этого класса. Весь вопрос в том, как разделять на классы. Пусть решается задача о коммивояжере (дана матрица расстояний полный граф). Например, Если мы будем вычитать одно и то же число из всех элементов строки или столбца, то суммарная стоимость пути коммивояжера не изменится. При вычитании константы из элемен- Литтл Дж., Мурти К., Суини Д., Кэрел Е. Я. Алгоритм решения задачи коммивояжера.//экономика и математические методы С.3-22.

28 6 3. Перебор и методы его сокращения тов строки стоимость любого пути уменьшится на эту константу, ибо числа в строке соответствуют выезду из города, а выезд из этого города обязательно присутствует в пути. Точно так же и вычитание из элементов столбца въезд в город. Вычитаемая константа входит в оценку пути, но не рассматривается дальше, после изменения матрицы. Найдем минимум в каждой строке и вычтем его. Получается матрица: Сумма вычитаемых констант равна 24. Аналогичную операцию выполним со столбцами: из элементов первого вычитаем 2, а из элементов четвертого. Итоговая сумма 27. Все пути коммивояжера уменьшились на это значение. Если получается выбор по одному нулю в каждом столбце и строке (они выделены курсивом в матрице), то тем самым мы получаем путь коммивояжера со стоимостью 27. Это путь (-»3-»2-Н>4->-»6->) С минимальной стоимостью, любой другой путь имеет большую стоимость. Значение 27 это оценка снизу всех маршрутов коммивояжера. В данном случае она достигается на конкретном маршруте. Очевидно, что мы просто очень удачно подобрали пример. Не обязательно после приведения существование пути по ребрам с нулевой стоимостью. Продолжим рассмотрение. Пусть дана другая матрица расстояний.

29 3. Перебор и методы его сокращения 7 После приведения по строкам и столбцам (сумма констант приведения равна 4) получаем следующую матрицу: Выделенные курсивом нули дают путь, но это не путь коммивояжера. Его вид показан на рисунке. Наши дальнейшие действия (шаг ветвления). Рассмотрим нули в приведенной матрице, именно нуль в позиции (, 2). Он, естественно, означает, что стоимость переезда из первого во второй город равна нулю. Однако если исключить (запретить) переезд из первого во второй город, то въезжать во второй город все равно придется. Цены въезда указаны во втором столбце въезжать из третьего города дешевле всего. Так как выезжать из первого города нам когда-либо придется, то дешевле всего выехать в третий город нулевая стоимость. Вычисляем сумму этих минимумов, она равна +=. Суть этой единицы в том, что если не ехать из первого города во второй, то придется заплатить не менее. Эта оценка нуля указана в матрице верхним индексом. Сделаем оценки всех нулей и выберем элемент с максимальной оценкой. Если таких нулей несколько, то выбираем любой. Итак, в чем суть ветвления. Все маршруты коммивояжера разбиваются на два класса, содержащих ребро (,2) и не содержащих ребро (,2). Для последнего класса оценка снизу увеличивается на единицу, т. е. равна. Для маршрутов из первого класса продолжаем работать с матрицей. Исключаем (вычеркиваем) первую строку и второй столбец. Кроме того, в уменьшенной матрице на место (2,) следует поставить прочерк, означающий невозможность соответствующего переезда. После этих манипуляций матрица примет следующий вид

30 8 3. Перебор и методы его сокращения Продолжим наши действия по оценке маршрутов из первого класса. Сокращенную матрицу, к сожалению, приводить нельзя минимальные элементы во всех строках и столбцах равны нулю. Таким образом, оценка снизу для класса маршрутов, содержащих (,2), остается равной 4. С сокращенной матрицей выполним аналогичные действия оценим нули, выберем нуль, соответствующий переезду из третьего города в первый. Суть действий в разбивке этого класса маршрутов на подклассы по той же самой схеме с (3,) и без (3,). Для второго подкласса оценка снизу 4+=9. С первым подклассом аналогичные действия исключаем столбец и строку, на место (2,3) в таблице пишем запрет на перемещение. Матрица допускает операцию приведения. Вычитаем единицу из элементов первой строки и первого столбца. Нижняя оценка маршрутов этого подкласса возрастает на два, итого 4+2=6. Следующий шаг приводит к матрице еще меньшего размера. Весь процесс работы по рассматриваемой схеме представлен на рисунке. Вершины этого дерева представляют классы решений. Черта над цифрами означает, что соответствующий класс не содержит какой-то конкретный переезд из города в город. Числа у вершин дерева означают оценки снизу для маршрутов из данного класса. Итак, получена первая оценка 6 для маршрута»2»4»6 >»3». Все подклассы решений, у которых оценка снизу больше или равна 6, исключаются из рассмотрения очевидный факт после изложения схемы решения. Остался только подкласс без переезда из первого города во второй, его оценка равна. Однако после первого же ветвления получаются подклассы с оценками 6 и 7. Обработку можно заканчивать. Найден наилучший маршрут коммивояжера, стоимость проезда по этому маршруту равна 6. Программная реализация метода ветвей и границ хорошая проверка техники программирования (структурного стиля самого процесса написания программы). Что лучше? Или работать с матрицами различной размерности, или вводить допол-

31 3. Перебор и методы его сокращения 9 нительные структуры для хранения исключенных номеров строк и столбцов. Вопросы можно продолжить. Ответ даст эксперимент с различными версиями программ реализации логики. В п рассмотрена одна схема решения задачи коммивояжера, в данном пункте другая. В чем их отличие для различных значений размерности задачи N? По некоторым оценкам, с помощью метода ветвей и границ можно решать задачи с iv 32 3. Перебор и методы его сокращения Procedure Search (Var S:Number); Var i,j:2..n; S: = [2..N] ; For i:=2 To N Div 2 Do If i In S Then j : =i +i ; Nhile j 33 3. Перебор и методы его сокращения cnt:integer; <*счетчик числа ходов.*>ok:boolean; <*признак - решение найдено. *>Procedure Init; Var i,j,k,:integer; For i:=2 To 6 Do For j:= To 6 Do For k:=l To 6 Do For := To 6 Do A[ (i-) *26+(j-l) *36+(k-l) *6+l] ; = Chr (i +Ord С ')) +Chr (j +Ord ('' ')) + +Chr(k+Ord(''))+Chr(+Ord('') ) ; For i:=l To Ртах Do В [i ] :=True; ent:=;ok:=false; Поясним на примере идею решета. Пусть длина последовательности равна двум, а количество цветов четырем. Ребенок загадал 32, а компьютер спросил 24. Ответ ребенка, фиксируем его в переменных kr () и bk(o). А В True True True True True True True True True True True True True True True True В (после анализа Ьк) False False False False False False False В (после анализа kr) False False False False False Результат False True False False False False False False False True False False True False True False Итак, было 6 возможных вариантов, после первого осталось четыре работа решета. Функция, реализующая анализ элемента массива А по значениям переменных kr и bk, имеет вид:

34 2 3. Перебор и методы его сокращения Function Pr (a,b:post;kr,bk:integer) -.Boolean; Var i,x:integer; <*Проверка по "быкам".*>x:=; For i:=l To 4 Do If a[i]=b[i] Then Inc(x) ; If xobk Then Pr:=False;Exit; <*Проверка по "коровам". *>x:=; For i:=l To 4 Do If (a[i]ob[i]) And (Pos (b[i],a) <>) Then Inc(x) ; If xokr Then Pr:=False;Exit; Pr:=True; Логика «сделать отсечение» по значению хода h. Procedure Hod(h:Post); Var i,kr r bk:integer; Inc(cnt) ;Write(cnt:2,'. ',h,'-'); ReadLn(kr,bk); If bk=4 Then ok: ='rue/ ;end Else For i:=l To Pmax Do If B[i] And Not Pr(A[i] r h,kr,bk) Then B[i]:=False; Общая логика. ClrScr; Init; Hod('223'); While Not ok Do Hod(h); End. \ выбор очередного хода из А " Дальнейшая работа с задачей требует ответа на следующие вопросы: Зависит ли значение cnt от выбора первого хода? Установить экспериментальным путем. Как логика выбора очередного хода влияет на результат игры? Исследовать. Например, выбрать тот элемент А (со-

35 3. Перебор и методы его сокращения 3 ответствующий элемент -В должен быть равен True), в котором количество несовпадающих цифр максимально. Примечание Рассмотренные задачи носят учебный характер. Обычно идеи метода решета используются в совокупности с другими методами Задачи. Задача о парламенте*. На острове Новой Демократии каждый из жителей организовал партию, которую сам и возглавил. Любой из жителей острова может состоять не только в своей партии, но и в других партиях. К всеобщему удивлению, даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предполагалось по Конституции острова, президенты всех партий. Посовещавшись, островитяне решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии. Помогите островитянам организовать такой, как можно более малочисленный парламент, в котором будут представлены все партии. Исходные данные: каждая партия и ее президент имеют один и тот же порядковый номер от до N (4 36 4 3. Перебор и методы его сокращения является номер партии, номером столбца номер жителя. Для примера из формулировки задачи она имеет вид: Тогда задачу можно переформулировать следующим образом. Найти минимальное число столбцов, таких, что множество единиц из них «покрывает» множество всех строк. Очевидно, что для примера это один столбец второй. Рассмотрим еще один пример. Из первоначальной таблицы можно исключить третий столбец, соответствующий третьему жителю, множество партий, в которых он состоит, содержится в множестве партий, в которых состоит второй житель. После сокращения таблицы могут появиться строки с одной единицей (партия представлена одним жителем). Таких жителей необходимо включать в парламент. Включаем второго жителя. После этого останется представить в парламенте только четвертую партию. Итак: во-первых, требуется проверять, есть ли житель, представляющий все множество не представленных в парламенте партий; во-вторых, исключать часть жителей из рассмотрения, если есть жители, представляющие большее количество партий, и это множество партий содержит партии исключаемого жителя; в-третьих, если в результате предыдущей операции появляются партии, представленные одним жителем, то этих жителей обязательно требуется включать в парламент. Вывод: перебор следует выполнять не по всем жителям и не для всех партий. Второе и третье действия необходимо выполнить до момента начала перебора вариантов (предварительная обработка) и только затем выполнять схему перебора. Первое действие должно выполняться как на стадии предварительной обработки, так и в процессе перебора. Общая схема перебора реализуется как обычно. Приведем часть описания данных для того, чтобы она была понятна.

37 3. Перебор и методы его сокращения Const Nmax=; Type Nint=..Nmax+l; Sset=Set of..nmax; Var A:Array[Nint] Of ; N:Integer; <*Число жителей на острове*.>Один из вариантов решения. Procedure Solve(k:Nint;Res,Rt:Sset); <*k- номер элемента массива A; Res - множество партий, которые представлены в текущем решении; Rt - множество партий, которые следует "покрыть" решением; min - минимальное количество членов в парламенте; mn - число членов парламента в текущем решении; Rbest - минимальный парламент; Rwork - текущий парламент; первый вызов - Solved, [], [..N]).*>Var i:nint; блок общих отсечений If Rt=[] Then If nm 38 6 3. Перебор и методы его сокращения Пример отсечений по i если при включении элемента с номером i в решение значение величины Ш не изменяется, то это включение жителя, информация по которому записана на месте i в массиве А, бессмысленно. 2. Какое наименьшее число ферзей можно расставить на доске так, чтобы они держали под боем все ее свободные поля? Модификация задачи. Найти расстановку ферзей, которая одновременно решает задачу для досок 9*9, * и *. Указание. Задачу можно решать как обычным перебором, так и, представив доску как граф, путем поиска минимального доминирующего множества вершин. 3. Расставить на доске N*N(N 39 3. Перебор и методы его сокращения 7 Написать программу, которая определяет: количество комнат в замке; площадь наибольшей комнаты; какую стену в замке следует удалить, чтобы получить комнату наибольшей площади. Замок условно разделен на M*N клеток (М ). Каждая такая клетка может иметь от до 4 стен. План замка содержится во входном файле в виде последовательности чисел, по одному числу, характеризующему каждую клетку. В начале файла расположено число клеток в направлении с севера на юг и число клеток в направлении с запада на восток. В последующих строках каждая клетка описывается числом р ( 40 8 3. Перебор и методы его сокращения мость C[i] проезда по дороге, соединяющей i-й и (i+l)-u города, С[М] стоимость проезда между первым и М-ш городами. Для жителей каждого города определить город, в который им необходимо съездить, чтобы заправиться самым дешевым образом, и направление «по часовой стрелке» или «против часовой стрелки», города пронумерованы по часовой стрелке. Указание. Переборный вариант решения задачи сводится к проверке всех 2*М вариантов для жителей каждого города, итого 2*М*М проверок. Введем два дополнительных массива On, Ag: Array[..M] Of Record wh, pr:integer;. On[i] означает, где следует заправляться (wh) и стоимость заправки (jpr) жителям i-ro города, если движение разрешено только по часовой стрелке. В этом случае жители города i имеют две альтернативы: либо заправляться у себя в городе, либо ехать по часовой стрелке. Во втором случае жителям города i надо заправляться там же, где и жителям города г+, или в первом, если i=m. Итак, On[i]=min. Откуда известно значение On[i+lJ.pr? Необходимо найти город ; с минимальной стоимостью заправки On[j]:=(j,Z[j]). После этого можно последовательно вычислять значения On[j ], On[j-2]. On[j+]. Аналогичные действия необходимо выполнить при формировании массива Ag[i], после этого для жителей каждого города i следует выбрать лучший из On[i].pr и Ag[i].pr вариант заправки.. В массивеа (Array [..N. M] Of Byte), заполненном и, найти квадратный блок максимального размера, состоящий из одних. Указание. Пусть N=, М=6 и массив А заполнен следующим образом (см. верхнюю таблицу). Определим массив В (Array[l..N,l..M] Of Byte) следующим образом. Элементы первой строки и первого столбца инвертируются относительно соответствующих (B[i,j]=l A[i,j]) элементов массива А. И далее, при i=2..n и j=2..m B[i,j]=O, если A[i,j]=l, и B[i,j]=Min(B[i-l,j],B[i,j-l],B[i-l,j-l]) +, если A[i,j]=O. Для нашего примера В представлен в нижней таблице. Ответ задачи 3. Как изменится решение, если потребовать нахождение прямоугольного блока максимального размера? Решает ли следующий фрагмент программного кода задачу?

41 3. Перебор и методы его сокращения 9 Procedure Solve; Var i, j, к, nx: Integer; sqa:=; <*результат. *>For i:= To N Do For j:= To M Do If A[i, j]= Then B[i, j]:=b[i, j-l]+l Else B[i, j]:=; <*b массиве А исходные данные, в В - результаты подсчета. *>For i:= То N Do For j := To M Do nx:=b[i, j]; For k:=i DownTo Do nx:=min(nx, B[k, j]); If nx* (i-k+) >sqa Then sqa:=nx* (i-k+) ;. Задача о паркете*. Комнату размером N*M единиц требуется покрыть одинаковыми плитками паркета размером 2* единиц без пропусков и наложений (М 42 2 3. Перебор и методы его сокращения шаге либо обходим справа выступающую клетку, либо нет. При других укладках паркета могут получиться другие сечения. Все варианты сечений легко пронумеровываются, ибо это не что иное, как двоичное число: обход справа плитки соответствует, отсутствие обхода. На рисунке сечение выделено «жирной» линией, ему соответствует двоичное число (3). Количество различных сечений 2' (пронумеруем их от до 2'-), где i длина комнаты. Не будем пока учитывать то, что некоторые из сечений не могут быть получены. Обозначим парой (Jk,j) комнату с фиксированной длиной i, правый край которой не ровный, а представляет собой сечение с номером k. B[k,j] количество вариантов укладки паркета в такой комнате. Задача в такой постановке сводится к нахождению B[O,j] количества укладок паркета в комнате размером (i,j) с ровным правым краем. Считаем, что В[,]= при любом i, ибо комната нулевой ширины, нулевого сечения и любой длины укладывается паркетом, при этом не используется ни одной плитки. Кроме этого считаем B[k,]= для всех сечений с номерами k<>, так как ненулевые сечения при нулевой ширине нельзя реализовать. Попытаемся найти B[k,j] для фиксированного i. Предположим, что нам известны значения B[l,j ] для всех сечений с номерами I ( 43 3. Перебор и методы его сокращения 2 For j:=l То 2 Do <*Цикл по значению ширины комнаты. *>For к:-о То max Do <*Сечение с номером к. *>For l:= To max Do <*Сечение с номером.*>If Can(k,l,i) Then В[k,j] ;=S[k,j] +B[,j-l] ; <*'Совместимость сечений "зарыта" в функции Can (k,l,i). *>A[i,j]:=B[O,j]; При решении вопроса о совместимости сечений следует различать понятия совместимость сечений в целом и совместимость в отдельном разряде. При анализе последнего входными данными являются значения разрядов сечений и информация о предыстории процесса (до текущего разряда) целое или нецелое количество плиток уложено. Выходными данными признак целое, нецелое количество плиток, требуемых для перевода сечения I в сечение k, или решение о том, что анализ продолжать не следует сечения несовместимы. Оставим эту часть работы и доведение схемы решения до работающего варианта на самостоятельное выполнение. Еще несколько замечаний. Во-первых, если произведение N на М нечетно (размеры комнаты), то количество укладок паркетом такой комнаты равно. Во-вторых, при М= и четном Л^ ответ равен. В-третьих, результирующая таблица симметрична относительно главной диагонали. В-четвертых, для комнат размером 2* достаточно просто выводится следующая рекуррентная формула: A[2,t]=A[2,t-l]+A[2,t-2] (ряд Фибоначчи). Эти замечания реализуются на этапе предварительной обработки и приводят к незначительной модификации логики процедуры Solve. Еще одно замечание касается точности результата. Для больших значений N и М необходимо организовать вычисления с использованием «длинной» арифметики (t=8, y'=2), ибо результат равен «Канадские авиалинии»*. Вы победили в соревновании, организованном канадскими авиалиниями. Приз бесплатное путешествие по Канаде. Путешествие начинается с самого западного города, в который летают самолеты, проходит с запада на восток, пока не достигнет самого восточного города, в кото- Задача с Пятой Международной олимпиады школьников по информатике 993 года.

44 22 3. Перебор и методы его сокращения рый летают самолеты. Затем путешествие продолжается обратно с востока на запад, пока не достигнет начального города. Ни один из городов нельзя посещать более одного раза за исключением начального города, который надо посетить ровно дважды (в начале и в конце путешествия). Вам также нельзя пользоваться авиалиниями других компаний или другими способами передвижения. Задача состоит в следующем: дан список городов и список прямых рейсов между парами городов; найти маршрут, включающий максимальное количество городов и удовлетворяющий вышеназванным условиям. Указание. Пусть нам необходимо попасть из самого западного города в самый восточный, посетив при этом максимальное количество городов. Связи между городами будем записывать с помощью массива West: Пусть мы каким-то образом решили задачу для всех городов, которые находятся западнее города с номером i, т. е. для городов с номерами..( ). Что значит решили? У нас есть маршруты для каждого из этих городов, и нам известно, через сколько городов они проходят. Обозначим через Q t множество городов, находящихся западнее i и связанных с городом i авиалиниями. Для этих городов задача решена, т. е. известны значения d[j] (jeq t ) количество городов в наилучшем маршруте, заканчивающемся в городе с номером у. Итак: Остается открытым вопрос, а где же маршрут? Ибо значение d дает только количество городов, через которые он проходит. А для этого необходимо запомнить не только значение d[i], но и номер города /', дающего это значение. Возможно использование следующей структуры данных: A:Array [I..max] Of Record d, l:byte;. В данной схеме мы видим не что иное, как метод динамического программирования в действии. Как обобщить этот набросок решения для первоначальной формулировки задачи? Для удобства перенумеруем города в обратном порядке с востока на запад. Изменим массив А (Аг-

45 3. Перебор и методы его сокращения 23 ray[..max,i..max] Of Record d,l:byte;). Под элементом A[i,j].d (путь из города i в город j) понимается максимальное число городов в маршруте, состоящем из двух частей: от i до (на восток) и от до / (на запад). По условию задачи нам необходимо найти наилучший по числу городов путь из N-ro города в N-&. Считаем, что A[l,l].d=l ua[i,j] A[j,i]- Через Q t обозначим множество городов, из которых можно попасть в город i. Верны следующие соотношения: A[i,j]. d=max (A[k,j].d+), при keqi, koj, если j<>; A[i,i].d=max (A[k,i].d), при i>l и keqi. 3. Решить предыдущую задачу методом полного перебора вариантов. Указание. Определим структуры данных, а именно: New.Arгау[..тах] Of Boolean; way, way_r:array[l..2*max] Of Byte; Первый массив необходим для хранения признака посещался или нет город (New[i]=True города с номером i нет в маршруте). Во втором и третьем массивах запоминаются по принципу стека текущий и наилучший маршруты соответственно. Для работы со стеками необходимы указатели переменные ук и ук_ргах. Логика перебора поясняется на нижеприведенном рисунке. Ищем путь из города с номером I. Фрагмент основной части логики. FillChar(New,SizeOf(New),True); yk:=;way[yk]:=2;pp:=true;yk_max:=; Solve () ; End. И процедура поиска решения. Procedure Solve(i:Byte); Var j,pn r pv:byte;

46 24 3. Перебор и методы его сокращения If i=n Then pp:=false; <*Меняем направление. *>If (i=l) And Not pp Then <*Вернулись в первый город. *>If yk>yk max Then <* Запоминаем решение.*>ук max:=yk ; way_r:=way; pp:=true; <*Продолжаем перебор. *>(*По направлению определяем номера, просматриваемых городов. *> If pp Then pn:=i+l; pv:=n; End Else pn:

l; pv:=i-l; For j:=pn To pv Do If West [i,j] And New[j] Then < *B город с номером j летают самолеты из города i, и город j еще не посещался. *>Inc (ук);way[yk]:=j;new[j]:=false; <*Включаем город j в маршрут. *>Solve (j) ; New[j]:=True;Way[yk]:=;Dec (yk); <*Исключаем город j из маршрута. *>If j=n Then pp: =True ; <*Если исключается самый восточный город (N), то меняем направление движения. *>4. Ресторан. В ресторане собираются N посетителей. Посетитель с номером i подходит во время Т. и имеет благосостояние Р г Входная дверь ресторана имеет К состояний открытости. Состояние открытости двери может изменяться на одну единицу за одну единицу времени, т. е. она или открывается на единицу, или закрывается, или остается в том же состоянии. В начальный момент времени дверь закрыта (состояние ). Посетитель с номером i входит в ресторан только в том случае, если дверь открыта специально для него, то есть когда состояние открытости двери совпадает с его степенью полноты S t. Если в момент прихода посетителя состояние двери не совпадает с его степенью полноты, то посетитель уходит и больше не возвращается. Ресторан работает в течение времени Т. Цель состоит в том, чтобы, правильно открывая и закрывая дверь, добиться того, чтобы за время работы ресторана в нем собрались посетители с максимальным суммарным благосостоянием.

47 3. Перебор и методы его совращения 2 Входные данные. В первой строке находятся значения N, К и Т, разделенные пробелами (l 48 26 3. Перебор и методы его сокращения 7. Черепашка находится в городе, все кварталы которого имеют прямоугольную форму, и ей необходимо попасть с крайнего северо-западного перекрестка на крайний юго-восточный. Пример. На некоторых улицах проводится ремонт, и по ним запрещено движение (например, между перекрестками 3 и 7, и 6, и ), длина, а значит и стоимость проезда по остальным улицам задается. Кроме того, для каждого перекрестка определена стоимость поворота. Так, если Черепашка пришла на 7-й перекресток и поворачивает к -му, то она платит штраф, а если идет в направлении 8-го, то платить ей не приходится. Найти для Черепашки маршрут минимальной стоимости. Исходные данные: N количество перекрестков, определяется через два числа I, m и N=l*m ( 49 3. Перебор и методы его сокращения Задано прямоугольное клеточное поле N*M (2 50 28 3. Перебор и методы его сокращения 2. «Американские кубики». Даны четыре кубика на рисунке изображены их развертки. Требуется сложить из них башню **4 так, чтобы на каждой боковой грани встречались все четыре цифры. Определить форматы входных и выходных данных. Написать программу поиска всех вариантов (если они есть) раскладки кубиков, удовлетворяющих условию задачи. 22. Клетки доски 8*8 раскрашены в два цвета: белый и черный. Необходимо пройти из левого нижнего угла в правый верхний так, чтобы цвета клеток перемежались. За один ход разрешается перемещаться на одну клетку по вертикали или горизонтали. Программа должна (если путь существует): находить хотя бы один путь; находить путь минимальной длины. Указание. Для решения задачи применим метод «волны» с учетом условия задачи чередования клеток разного цвета. 23. Дана матрица N*N (N 51 3. Перебор и методы его сокращения 29 За один ход разрешается взять любые две подряд идущие буквы и перенести их в пустые сектора, сохранив порядок. При этом сектора, которые занимали перенесенные буквы до хода, становятся пустыми. Номером хода назовем номер первого из секторов в порядке обхода по часовой стрелке (ЧС), содержимое которого переносится. Состояние круга назовем правильным, если начиная с сектора по ЧС можно прочесть слово «РОССИЯ». При этом местоположение пустых секторов может быть произвольным. Состояние круга можно закодировать строкой из 8 символов, получающихся при чтении круга по ЧС, начиная с сектора, если пустому сектору поставить в соответствие символ подчеркивания '_' Эту строку из 8 символов будем называть кодом круга. По заданному коду найти кратчайшую последовательность ходов, переводящую круг в правильное состояние. Если решений несколько, то необходимо выдать только один вариант. Указание. Задача решается перебором вариантов. Из каждого состояния круга генерируются все состояния, в которые можно попасть из него. Запоминаем состояния в структуре данных типа очередь. Повторяющиеся состояния в очередь не записываются. Процесс перебора заканчивается при достижении состояния, эквивалентного состоянию «РОССИЯ». 2. Заданы две символьные строки А и Б, не содержащие пробелов. Требуется вычислить, сколькими способами можно получить строку В из строки А, вычеркивая некоторые символы. Например, если строки А и В имеют соответственно вид СамаринаИрина и Сара, то искомое число равно 7, для строк аааввввссс и авс это число равно 36. а а а 2 а 3 b 3 Ь 3 b 3 b 3 с 3 с 3 с 3 b с Написать программу, находящую требуемое число способов. Указание. Рассмотрим идею решения на примере. Для клеток, у которых символы на горизонтали и вертикали не совпадают, значение переписывается из соседней по горизонтали

Илон Маск рекомендует:  Java Script. Примеры скриптов.
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL