Алгоритмы перебора

И.И.Данилина

 

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

1. Волновой алгоритм

  Для иллюстрации идеи рассмотрим задачу поиска по карте местности кратчайшего маршрута, соединяющего две заданные точки ("компьютерный штурман"). Если бы все участки были проходимы, то оптимальный маршрут строился бы легко — это отрезок прямой, соединяющий указанные точки. К сожалению, в жизни имеется множество непреодолимых для выбранного способа передвижения (например, пешком) преград (чащи, болота, строения и т.п.). Поэтому задача о выборе оптимального маршрута не столь проста. Более того, она существенно зависит от того, кто ее решает. Если решающий — человек, то, выбирая маршрут, он может обозревать карту местности всю целиком (говорят еще, что человек обладает интегральным зрением). Компьютеру же для анализа в каждый конкретный момент доступен лишь некий элемент карты (у компьютера — локальное зрение). В этом различии между интегральным и локальным зрением и кроется одна из причин затруднения, а иногда и невозможности переформулирования алгоритма, используемого человеком, в компьютерный алгоритм.
  Прежде всего построим модель задачи. Здесь мы должны решить, что означают слова: "карта местности", "непроходимый участок", "кратчайший маршрут".
  Одна из возможных моделей такова; карта местности разбивается на мелкие квадраты, размером которых можно пренебречь, и координаты точки пересечения диагоналей квадрата примем за координаты этого квадрата. Тогда всю карту можно представить в виде двухмерного целочисленного массива Map, индексы которого — координаты соответствующих точек, а значения — признак возможности прохождения точки с координатами х и у. Map [х, у] = 0, если участок проходим, и равно —1, если нет. Две точки будем называть соседними, если они имеют только одну различную координату (например, точки Map [5, 4] и Map [6, 4] — соседние, а точки Map [5, 4] и Map [6, 3] — нет). Маршрутом будем считать последовательность соседних точек карты. Длиной маршрута будем считать число клеток в нем (это определение соответствует случаю равнинной местности, когда при преодолении любого квадрата проходится примерно одинаковый путь).
  В терминах этой модели исходная задача формулируется так: даны двухмерный числовой массив Map с элементами, равными 0 и —1, и две пары индексов (две точки): x_begin, y_begin и x_end, y_end. Требуется построить последовательность соседних элементов с нулевыми значениями такую, чтобы первым элементом в ней был Map [x_begin, y_begin] , а последним — Map [x_end, y_end], причем число элементов в ней было бы минимальным из всех возможных.
  Таким образом, объектами перебора являются все маршруты, соединяющие указанные точки. Эти маршруты, во-первых, надо построить (они заданы лишь потенциально), что само по себе непросто, во-вторых, их может быть очень много (существенно больше, чем число точек на карте), и из множества построенных маршрутов выбрать маршрут минимальной длины.
  Волновой алгоритм позволяет обойти эти трудности путем построения сразу оптимального маршрута. При этом, если поставленная задача неразрешима (нет ни одного маршрута, соединяющего указанные точки), то это становится известно на некотором этапе. Основная часть этого алгоритма — построение множества точек, до которых можно добраться за К шагов и нельзя быстрее (этот процесс аналогичен процессу распространения волны, откуда и произошло название алгоритма).
  Содержательное описание волнового алгоритма таково:
  1. Начальный этап. Пометим начальную точку числом 1 (в эту точку ведет маршрут длины 0).
  2. Распространение волны. Если рассматриваемая точка помечена числом К > 0 (в нее можно попасть за К—1 шагов), то все соседние точки, помеченные нулем, надо пометить числом К + 1 (в них можно попасть за К шагов). Распространение волны осуществляется до тех пор, пока это возможно (есть еще соседние, помеченные нулем, точки) и целесообразно (еще не дошли до конечной точки).
  3. Проверка возможности построения пути. Если после распространения волны конечная точка помечена некоторым числом К > 0, то в нее можно попасть за К— 1 шаг. В противном случае эта точка недостижима из начальной.
  4. Построение пути. Для того чтобы построить оптимальный маршрут, необходимо, начиная с конечной точки, выбирать соседнюю с ней, помеченную числом на единицу меньше. Затем проделать это же с новой точкой. И так далее, пока не доберемся до начальной.
  Из описания алгоритма видно, что он распадается на два этапа: распространение волны (включая начальный этап) и построение пути. Такая структура позволяет естественным образом разбить исходный алгоритм на две процедуры.
  Прежде чем приступить к реализации этих процедур, отметим, что в них нам придется просматривать точки, соседние с заданной. И здесь нас подстерегает одна техническая трудность: не у всех точек одинаковое число соседей — у точек на границе карты соседей меньше. Чтобы избежать лишних проверок, расширим массив Map и пометим всю границу как непроходимые точки. Тогда все рассматриваемые точки будут не на границе и поэтому будут иметь одинаковое число соседей — 4.
  Начнем с процедуры распространения волны. Основное действие — построение очередного фронта волны. Действие нужно повторить, если очередной фронт волны был построен и до конечной точки еще не дошли. Процесс построения фронта — просмотр в цикле элементов двухмерного массива. Таким образом, в реализации построения фронта волны будем использовать двойной цикл, а процедура распространения волны содержит тройной цикл.

Procedure Wave (x_begin, y_begin, x_end, y_end : integer);
                               { координаты начала и конца пути )
var
    k      : integer; { номер "фронта волны" }
   х, у  : integer; { координаты текущей точки }
    flag : boolean; { признак необходимости строить очередной фронт }
begin
        Map[x_begin, y_begin] := 1; { начальный этап }
        k := 1; (в точку, помеченную числом k, можно попасть за k-1 шаг }
        flag := true; { нужно строить фронт }
        while flag do { строим очередной фронт }
        begin
               flag := false;
               { возможно, что волне продвинуться не удастся }
               for х := 1 to Length_Map do { Length_Map - максимальное значение индекса х}
                   for у := 1 to Width_Map do { Width_Map - максимальное значение индекса у}
                        if Map [х, у] = k then
                        begin
                        { просмотреть -соседей и пометить очередной фронт)
                            if Мар [х+1, у] = 0 then
                            begin
                                Мар [х+1, у] := k+1; flag := true
                            end;
                            if Map [x, y-l] = 0 then
                            begin
                                Map [x, y-l] := k+1; flag := true
                            end;
                            if Map [x, y+l] = 0 then
                            begin
                                Map [x, y+l] := k+1; flag := true
                            end;
                            if Map [x-l, y] = 0 then
                            begin
                              Map [x-l, y] := k+1; flag := true
                            end;
                   end;
                         if Map[x_end, y_end] > 0 then flag := false
                                                                       else k := k+1
                         { переходим к следующему фронту волны}
        end
end;

  Процедура формирования пути использует заполненный массив Map и формирует на его основе массив Way,. начиная от конечной точки.

Procedure Track (x_end, у_end : integer); { построение пути''}
var
     k      : integer;  { номер фронта волны             }
     step : integer; { номер шага пути                     }
     х, у   : integer; { координаты текущей точки }
Procedure Way_Step; { присоединение очередной точки к маршруту}
begin
     Way [step, 1] := x; Way [step, 2] := у;
     step := step+1; k := k-1 { метка следующей точки }
end;
begin
       step := 1
       Way [l, l] := x_end; Way[l, 2] := y_end;
       k := Map [x_end, y_end] - 1; { число, которым должна быть помечена следующая точка }
       х := x_end; у := у_end;
       while k > 0 do { найти следующую точку }
       begin
              if Map [x+l, y] = k
               then begin x := x+1; Way_Step end
               else if Map [x, y-l] = k
                        then begin у := y-l; Way_Step end
                  else if Map [x, y+1] = k
                                 then begin у := y+1; Way_Step end
                                 else if Map [x-l, y] = k
                                          then begin x := x-l; Way_Step end
       end
end;

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

Program Short_Way;
const Length_Map = 10; Width_Map = 8; {размеры карты }
var
    x_begin, y_begin, x_end, y_end : integer;
    (начало и конец пути }
    Map : array [0..Length_Map+l, 0..Width_Map+l] of integer;
    { карта с добавленными границами }
    Way : array [1..Length_Map * Width_Map,1.. 2] of integer;
    { маршрут }
    i, j, k : integer;
{ описание процедур приведено выше}
begin
      { перед началом нужно задать концы маршрута и карту }
      Wave (x_begin, y_begin, x_end, y_end); { волна }
      if Map [x_end, y_end] > 0 { если до конечной точки можно добраться }
       then Track (x_end, y_end) { координаты точек пути в массиве Way }
       else writeln ( ' Маршрут непроходим! ' )
end.

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

Упражнение

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

2. Волна на графе

  Вновь рассмотрим задачу нахождения оптимального маршрута из одного населенного пункта в другой, но при других предположениях.
  Чтобы достигнуть конечного пункта быстрее, будем использовать самолет, а следовательно, строить авиационный маршрут. А поскольку самое неприятное в полете — это взлет и посадка, будем минимизировать их число. Таким образом, маршрут — это последовательность населенных пунктов А1, А2, ..., Аn, таких что из Аk в Ak+1 можно долететь без промежуточных посадок. Мы имеем набор точек, ряд из которых являются "соседними" (в смысле беспосадочного перелета). Но в отличие от предыдущего случая, когда каждая точка имела ровно четырех соседей, здесь число соседей может быть различным у разных точек. Поэтому представить их массивом, аналогично массиву Map, нам не удастся.
  Задачи обработки некоторого набора объектов, относительно любой пары которых можно сказать, находятся они в некотором отношении друг к другу ( "соседи") или нет, встречаются довольно часто. Такие структуры носят специальное название —  графы, при этом сами объекты (точки) называются вершинами, а пары вершин, непосредственно связанных между собой (соседние), — ребрами.
 
Маршрутом на графе называется последовательность вершин A1, А2 ..., Аn такая, что для всех k = 1,..., n—1 вершины Аk и Аk+1 связаны ребром.
  В этих терминах рассматриваемая задача об авиационном маршруте формулируется так: задан граф, в котором выделены две вершины, требуется найти маршрут, соединяющий их и содержащий наименьшее число вершин.
  К поиску маршрута на графе приводят и задачи "трассировки печатных плат" — соединение радиодеталей (здесь вершины — точки на плате, между которыми можно проводить соединения, а ребра — возможные пути проведения), и задачи поиска выигрышных стратегий в играх (здесь вершины — это всевозможные позиции или ситуации, которые возникают в игре, а ребра — это соседние позиции, то есть такие, что одна переходит в другую после очередного хода), и многие другие.
  При изображении графа его вершины обозначаются точками, а ребра — отрезками или линиями, соединяющими вершины. Например, граф с пятью вершинами a, b, с, d, e и ребрами (a, b), (a, c), (b, c), (с, d) и (d, е) можно изображать так:
                                                         wpe2.jpg (3047 bytes)
                                                                                                                       Рис. 1

  Простейшим способом описания графа, содержащего п вершин, является таблица смежности размера n х n. Она строится так: вершины графа перенумеровываются, и на пересечении i-й строки с j-й столбцом записывается 1, если вершины с номерами i и j связаны между собой ребром, и 0 в противном случае. Так, таблица смежности для графа, изображенного на рис. 1 с нумерацией вершин в алфавитном порядке, имеет вид:

0  1  1  0  0
1  0  1  0  0
1  1  0  1  0
0  0  1  0  1
0  0  0  1  0

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

wpe2.jpg (14118 bytes)

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

                                              Рис. 2

  Ниже приведены описание данных и процедура создания списковой структуры для представления графа:
{ . . . }
const max_graf = 100; { максимальное число вершин графа}
type        list = ^elem;
                elem = record
                                  num : integer;
                                  next : list;
                            end;
var
                Graf : array[1..max_graf] of elem;
{ . . . }
Procedure CreateGraf(n:integer) ;
(n - число вершин графа)
var a:integer;
       sosed,sosed1 : list;
begin
     for i:=1 to n do { для каждой вершины }
     begin
          new(sosed); { выделили память для нового элемента }
          graf[i].next := sosed; { ссылка на новый элемент }
          Writeln ('Для элемента ' , i , ' введите номер очередного соседа или 0 ') ;
          repeat
             Readln(a);
             sosed^.num := а; { указатель на очередного соседа }
             if а<>0 then
             begin
                   new(sosed1);
                   sosed^. next := sosed1
                   sosed := sosed1
             end;
          until a=0 { больше соседей нет}
     end
end;

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

Procedure Wave (num_begin, num_end : integer) ;
                               { номера вершин начала и конца пути }
var
      k       : integer;    { номер "фронта волны"    }
      num : integer;   { номер текущей вершины }
      flag  : boolean; { признак необходимости строить очередной фронт }
      beg_qu, end_qu, elem_qu : list;
{ начало, конец и элемент очереди }

Procedure Add (num : integer; var end_qu : list );
{ добавление элемента к очереди }
var
          elem_qu : list;
begin
     end_qu^ .num:=num; { поместили элемент в конец очереди }
     new(elem_qu); { выделили память под следующий элемент }
     end_qu^.next:=elem_qu; {присоединили новый элемент }
     end qu:=elem_qu
end;

Procedure Extract (var num : integer; var begin_qu : list );
{ извлечь элемент из списка }
var
    elem_qu : list;
begin
     num:=beg_qu^.num; { считали первый элемент очереди }
     elem_qu:=beg_qu; { запомнили ссылку на первый элемент для последующего уничтожения }
     beg_qu:=beg_qu^.next; { переносим указатель начала очереди на второй элемент}
     Dispose(elem_qu) { освобождаем память, уничтожив первый элемент }
end;
begin
     new(elem_qu);{ инициализация очереди и размещение в ней первого элемента }
     beg_qu:=elem_qu; { очередь пока пуста }
     end_qu:=elem_qu;
     Graf [ num_begin] .nurn := 1; {начальный этап }
     Add(num_begin, end_qu); {поместили начало пути в очередь }
     flag := true; {нужно строить фронт }
     while flag and (not goal) do { строим очередной фронт }
     begin
          Extract (nurn, beg_qu) ;
&