ОБХОД ДЕРЕВА. ПЕРЕБОР С ВОЗВРАТАМИ

    •  
      •  
          1. Приведенная программа тратит довольно много времени на выполнение проверки есть_сверху (проверка, находится ли верхний ферзь под боем, требует числа действий порядка n). Изменить реализацию операций с деревом позиций так, чтобы все три проверки есть_сверху / справа / снизу и соответствующие команды требовали бы количества действий, ограниченного не зависящей от n константой.
          2. Использовать метод обхода дерева для решения задачи: дан массив из n целых положительных чисел a[1]...a[n] и число s; требуется узнать, может ли число s быть представлено как сумма некоторых из чисел массива. (Каждое число можно использовать не более чем по одному разу).
          3. Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд ( нет куска вида ХХ).
      • Упражнения:
  • В этой главе рассмотрим ещё один приём перечисления всех элементов некоторого множества. Его называют "поиск с возвратами", "метод ветвей и границ" или "обход дерева".

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

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

    Пример:

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




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

    Из пункта А мы попадаем в пункт В, из В - в С, из С - в D. Отсюда дороги нет. Мы снова возвращаемся на ближайший "перекресток" С и из него пробуем пройти по новой дороге в пункт Е. Здесь мы обнаруживаем выход. Задача решена. Её решение - путь АВСЕ.

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

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

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

    В подобных задачах полезно рассмотреть частный случай (с фиксированным малым количеством переменных). На основе частного случая составить алгоритм и обобщить его на n переменных.

    Задача о восьми ферзях - хорошо известный пример использования метода перебора с возвратом. В 1850 г. эту задачу исследовал К.Ф.Гаусс, однако полностью он ее так и не решил, т.к. для подобных задач характерно отсутствие аналитического решения. Они требуют огромного количества изнурительной работы.

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

    Решение:

    Очевидно, что на каждой из n горизонталей должно стоять по ферзю. Будем называть k-позицией (для k=0,1,...,n) произвольную расстановку k ферзей на k нижних горизонталях (ферзи могут бить друг друга).

    Нарисуем "дерево позиций": его корнем будет единственная 0-позиция, а из каждой k-позиции выходит n стрелок вверх в (k+1)-позиции. Эти n позиций отличаются положением ферзя на (k+1)-ой горизонтали. Будем считать, что расположение их на рисунке соответствует положению этого ферзя: левее та позиция, в которой ферзь расположен левее.

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

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

    Дерево допустимых позиций для n=3

    Разобьем задачу на две части: (1) обход произвольного дерева и (2) реализацию дерева допустимы позиций.

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

    (На рисунках стрелками показано, какие перемещения соответствуют этим командам.)

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

    (последняя проверка истинна всюду, кроме корня). Обратите внимание, что команда вправо позволяет перейти лишь к "родному брату", но не к "двоюродному".

    Так команда вправо не действует!

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

    Доказательство правильности приводимой далее программы использует такие определения. Пусть фиксировано положение Робота в одной из вершин дерева. Тогда все листья дерева разбиваются на три категории: над Роботом, левее Робота, и правее Робота. (Путь из корня в лист может проходить через вершину с Роботом, сворачивать влево, не доходя до нее и сворачивать вправо, не доходя до нее). Через (ОЛ) обозначим условие "обработаны все листья левее Робота", а через (ОЛН) - условие "обработаны все листья левее и над Роботом".

    Нам потребуется такая процедура:

    procedure вверх_до_упора_и_обработать
    {дано: (ОЛ), надо: (ОЛН) }
    begin
    {инвариант: ОЛ}
    while есть_сверху do вверх_налево;
    {ОЛ, Робот в листе}
    обработать;
    {ОЛН}
    end;

    Основной алгоритм:

    дано: Робот в корне, листья не обработаны
    надо: Робот в корне, листья обработаны
    {ОЛ}
    вверх_до_упора_и_обработать;
    {инвариант: ОЛН}
    while есть_снизу do
    if есть_справа then
    begin {ОЛН, есть справа}
    вправо; {ОЛ}
    вверх_до_упора_и_обработать;
    end
    else вниз; {ОЛН, не есть_справа, есть_снизу}

    {ОЛН, Робот в корне все листья обработаны}

    Осталось воспользоваться следующими свойствами команд Робота (в каждой строке в первой фигурной скобке записаны условия, в которых выполняется команда, во второй - утверждения о результате ее выполнения):
    (1) {ОЛ, не есть_сверху} обработать {ОЛН}
    (2) {ОЛ} вверх_налево{ОЛ}
    (3) {есть_справа, ОЛН} вправо {ОЛ}
    (4) {не есть_справа, ОЛН} вниз {ОЛН}

    Реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной k: 0..n (число ферзей) и массива c: array [1..n] of 1..n ( c[i] - координаты ферзя на i-ой горизонтали). Предполагается, что все позиции допустимы (если убрать верхнего ферзя, остальные не бьют друг друга).

    const n=...;
    var k:0..n;
    c:array[1..n] of 1..n;

    procedure begin_work;{начать работу}
    begin
    k:=0;
    end;

    function danger: boolean; {верхний ферзь под боем}
    var b: boolean;
    i: integer;
    begin
    if k<=1 then danger:=false
    else
    begin
    b:=false; i:=1;
    while i<>k do
    begin
    b:=b or (c[i]=c[k]) {вертикаль}
    or (abs(c[i]-c[k])=abs(i-k)); {горизонталь}
    i:=i+1;
    end;
    danger:=b;
    end;
    end;

    function is_up: boolean; {есть_сверху}
    begin
    is_up:=(k<n) and not danger;
    end;

    function is_right: boolean; {есть_справа}
    begin
    is_right:=(k>0) and (c[k]<n);
    end;

    function is_down: boolean; {есть_снизу}
    begin
    is_down:=(k>0);
    end;

    procedure up; {вверх_налево}
    begin {k<n, not danger}
    k:=k+1;
    c[k]:=1;
    end;

    procedure right; {вправо}
    begin {k>0, c[k]<n}
    c[k]:=c[k]+1;
    end;

    procedure down; {вниз}
    begin {k>0}
    k:=k-1;
    end;

    procedure work; {обработать}
    var i:integer;
    begin
    if (k=n) and not danger then
    begin
    for i:=1 to n do write('<',i,',',c[i],'> ');
    writeln;
    end;
    end;

    procedure uw; {вверх_до_упора_и_обработать}
    begin
    while is_up do up;
    work;
    end;

    BEGIN
    begin_work;
    uw;
    while is_down do
    if is_right then
    begin right; uw; end
    else down;
    End.

     

     

Другие записи

10.06.2016. Задачи без массивов
В данной теме предлагаются решения простых задач с наименьшим числом действий (выполяемых операторов присваивания). Задача 1. Дано число а и натуральное число n. Вычислить аn (a в степени n). Решение:…
10.06.2016. МАССИВЫ
  В этом разделе предлагаются задачи, в которых реализуются алгоритмы работы с массивами (упорядоченными и неупорядоченными). Для решения задач достаточно уметь пользоваться основными конструкциями…
10.06.2016. РАЗМЕЩЕНИЯ. ПЕРЕСТАНОВКИ. СОЧЕТАНИЯ
В этой теме рассматриваются элементы комбинаторики и алгоритмы решения комбинаторных задач. Имеется n различных предметов. Сколько из них можно составить k-расстановок? При этом две расстановки считаются…
10.06.2016. Cписок литературы
  1. Александров В.В. Рисунок, чертеж, картина на ЭВМ. - Л., Машиностроение, 1987г. 2. Аммерал Л. Принципы программирования в машинной графике. -М., Сол Систем, 1992г. 3. Арсак Ж. Программирование игр…