Понятие полного перебора. Основные приемы его осуществления

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

К задачам, при решении которых используется перебор, относятся также задачи из области искусственного интеллекта, решения которых ищутся методом "проб и ошибок". Например, задача о расстановке n ферзей на доске n*n таким образом, чтобы они не били друг друга. К этой же группе относятся задачи, в которых требуется получить все возможные перестановки каких-то элементов, например, все перестановки букв от A до F.

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

Общий алгоритм решения задачи с использованием полного перебора по первой стратегии может быть представлен следующим образом:

цикл-пока еще есть варианты

генерировать вариант

 если вариант удовлетворяет условию,

        то обработать набор

все-если

Все-цикл

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

В качестве примера рассмотрим классическую "задачу о сдаче".

Пример 10. Разработать программу выдачи сдачи минимальным количеством монет при ограниченном количестве монет каждого достоинства в кассе.

Попытка использовать известный алгоритм, при котором сдача выдается, начиная с монет большего достоинства, и включает максимальное возможное количество монет каждого достоинства, в этом случае не дает оптимального решения. Например, если необходимо выдать сдачу 47 копеек, и в кассе имеется достаточное количество монет достоинством 1,2,3, 5,10,15,20 копеек, то алгоритм работает: 47=20*2+5*1+2*1 - 4 монеты. Но при отсутствии в кассе 5 копеечных монет вариант 47=15*3+2*1 (4 монеты) лучше варианта 47=20*2+3*2+1*1 (5 монет). При таких условиях для решения этой задачи используется метод перебора вариантов и программируемый счетчик.

Текст программы

#include "stdafx.h"

#include <stdio.h>

#include <string.h>

#include <locale.h>

#include <conio.h>

const int n=8;

int q[]={0,0,0,0,0,0,0,0}; // программный счетчик

int p[]={50,20,15,10,5,3,2,1}; // номиналы монет

int s[8]; //количество монет каждого достоинства

int s1[8];     // количество монет каждого достоинства с учетом сдачи

int qn[8]; // найденная комбинация, позволяющая выдать сдачу

int e,en,k,kn,mink,i;

long komb;

int imin(int a,int b)

{

if(a>b) return b;

else return a;

}

Void main()

{

setlocale(0,"russian");

puts("Введите количество монет каждого достоинства в кассе");

for(i=0;i<n;i++)

{

printf("%5d коп. - ",p[i]);

scanf("%d",&s[i]);

}

puts("Введите размер сдачи");

scanf("%d",&e);

for(i=0;i<n;i++)

   s1[i]=imin(s[i],e/p[i]);

mink=e+1;

while(q[0]<=s1[0])

{

     q[n-1]+=1;

     for (k = n -1; k >0; k --) // протряхивание счетчика

     if(q[k]>s1[k])

     {

              q[k]=0;

               q[k-1]+=1;

               }

     en=0;kn=0;

               for(i=0;i<n;i++)

     {

              en=en+q[i]*p[i];

       kn+=q[i];

              }

     komb++;

            if((en==e)&&(kn<mink))

              {

                        mink=kn;

                            for(i=0;i<n;i++)

                 qn[i]=q[i];

              }

}

if(mink!=e+1)

{  

  puts(" В сдаче:");

  for(i=0;i<n;i++)

    if(qn[i]!=0)

     printf(" Монет %5d коп. - %5d штук \n",p[i],qn[i]);

}

 else puts("Сдачу выдать невозможно");

 printf("Количество рассмотренных вариантов=%5d\n",komb);

getch();

}

 

Пример 11. Написать программу, которая генерирует следующие комбинации: 1111, 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211,..., 3333.

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

#include "stdafx.h"

#include <stdio.h>

short int a [4]={1,1,1,1}; // исходное значение счетчика

  void main()

{ int i;

while (a[0]<4) //условие "сброса" счетчика

   {

     for(i=0;i<4;i++)

     printf("%2d",a[i]);

     printf("\n"); //вывод комбинации

       a[3]=a[3]+1; // добавление 1 в последний разряд

      for(i=3;i>0;i--) // анализ и осуществление переносов

       if (a[i]>3)

     {

            a[i]=1;

     a[i-1]=a[i-1]+1;

     }

}

}

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

Еще одна задача полного перебора – это задача о ферзях.

Пример 12. Задача о расстановке ферзей.       

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

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

              Матрица                     Вектор

               Рисунок 10 – Представление доски вектором

2. Определим, что для векторного представления означает "бьет". Ферзь "бьет" другую фигуру, если она расположена на той же диагонали, вертикали или горизонтали, т.е. если

                  Pole [ j ]= Pole [ i ] – одна горизонталь;

                  | Pole [ j ]- Pole [ i ] | = | j - i | – одна диагональ

Равенство по вертикали исключается тем, что в одной ячейке массива может

располагаться только одно значение.

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

#include "stdafx.h"

#include <stdio.h>

#include <math.h>

bool new _ r (int n, int pole []) // проверка варианта на условие   ферзь "не бьет"

{ bool r=true;

for(int i=0;i<n-1;i++)

for(int j=i+1;j<n;j++)

     if((pole[i]==pole[j])||(abs(pole[j]-pole[i])==abs(j-i)))

      {r=false;return r;}

     return r;

}

bool variant (int m, int pole []) // генерация варианта

{

     int i;

pole[m-1]=pole[m-1]+1;

     for(i=m-1;i>0;i--)

              if(pole[i]>m)

              {

                        pole[i]=1;

                        pole[i-1]=pole[i-1]+1;

              }

              if (pole[0]<=m) return true;

              else return false;

}

int main(int argc, char* argv[])

{

  int pole[10],m,i;

  puts("Input N");

scanf("%d",&m);

for(i=0;i<m;i++)

pole[i]=1;

      while (variant (m, pole)) // пока есть варианты

{

     if (new _ r (m, pole)) // проверка варианта на условие    ферзь "не бьет"

     {

                for (i =0; i < m; i ++) // печать подходящего варианта

              printf("%2d",pole[i]);

                  printf("\n");

          }

}

     return 0;

}

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