Использование рекурсии при реализации ограниченного перебора

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

Пример 13. Написать программу, которая выводит все возможные комбинации цифр 1, 2, 3 без их повторения.

 1,2,3 Þ 123,132, 213, 231, 312, 321.

Схема формирования перестановок представлена на рисунке 11.

                  

 

Рисунок 11 – Схема формирования перестановок

Схема алгоритма рекурсивной подпрограммы приведена на рисунке 12.

 

Рисунок 12 – Схема алгоритма перестановок цифр 123

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

# include " stdafx. h "

# include < stdio. h >

void perest (int n, int m, const int r [], int pole [])

{

 int r1[3],k,i,j;

 if (n==m)

{

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

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

printf("\n");

}

Else

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

{

pole[n]=r[i];

k=0;

for(j=0;j<m-n;j++)

if (j!=i)

{

     r1[k]=r[j];

    k++;

    }

perest(n+1,m,r1,pole);

 }

}

//Основная программа

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

{

int a[3]={1,2,3 }, pole[3];

perest(0,3,a,pole);

return 0; }

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

Рисунок - 13  Дерево вариантов расстановок

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

Для реализации программы используем две подпрограммы (см. рисунок 14). Функция new_r используется для проверки уже сгенерированной комбинации (уровень n соответствует попытке установить n-го ферзя). Процедура ferz рекурсивна. На каждом уровне она может породить до m рекурсивных вызовов (в соответствии c деревом генерации вариантов). Однако общее количество рассматриваемых вариантов резко уменьшается, что можно наглядно видеть по таблице 1.

 

Рисунок 14 – Схемы алгоритмов программы задачи о ферзях

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

#include "stdafx.h"

#include <stdio.h>

#include <math.h>

// Функция проверки корректности варианта

int new_r(int n,int pole[])

{ int r=1;

  for(int j=0;j<n;j++)

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

    r =0;

return r;

}

// Функция расстановки ферзей 

void ferz (int n, int m, int pole [])

{ int i;

if (n==m){

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

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

printf("\n"); }

else

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

{pole[n]=i;

if(new_r(n,pole)==1) ferz(n+1,m,pole);

}

}

// Основная программа

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

{

  int pole [10], m;

  puts (" Input N ");

  scanf ("% d ",& m);

 ferz(0,m,pole);

return 0;

}

Таблица 1 – Зависимость рассматриваемых вариантов от размера доски

Размер доски	Всего вариантов	Рассмотрено вариантов	Количество решений
4*4	256	17	2
5*5	3125	54	10
6*6	46656	153	4
7*7	823543	552	40
8*8	16777216	2057	92

Задания для самопроверки

Задание 1. Разработайте рекурсивную подпрограмму, осуществляющую поиск выхода из лабиринта по методу перебора с отсечением неперспективных направлений. Лабиринт представляет собой двумерный массив, в котором наличие прохода отмечено единицей, а тупик – нулем.

Задание 2. Дан максимальный вес рюкзака, набор предметов (вес и стоимость). Разработайте рекурсивную подпрограмму, которая определяет,  какие предметы нужно взять, чтобы суммарный вес рюкзака не превышал заданного, а суммарная стоимость была бы максимальной.