Бектрекинг (енгл. backtracking) или исцрпна претрага је стратегија за решавање проблема која се заснива на систематичном испитивању свих могућих опција како би се пронашло решење. Бектрекинг је суштински заснован на индуктивно-рекурзивној техници за конструкцију алгоритама и гради решење део по део.
Алгоритам у сваком кораку доноси одлуку о наставку претраге и прелази на следећи ниво. Ако приликом доношења одлуке, алгоритам схвати да тај пут или грана не може да доведе до валидног решења, алгоритам одустаје и враћа се назад на претходни ниво, тј. ради бектрек.
Најлакше га можемо замислити као истраживање лавиринта. Све време идемо једним путем док не ударимо у зид, тј. не наиђемо на ћорсокак. Када ударимо у зид, враћамо се назад до последње раскрснице и настављамо претрагу неким другим путем. Јасно је да овакав приступ врло лако може да нас заглави у циклусу, па је уобичајена тактика за разбијање циклуса да током претраге остављамо трагове, слично Ивици и Марици, да бисмо знали које смо путеве већ посетили и/или одбацили.
Концептуално у сваком кораку алгоритма радимо следеће:
Прелазак у наредно стање, једнак је рекурзивном позиву. Враћање у претходно стање, једнако је одмотавању рекурзије. С обзиром да се ради о рекурзивним имплементацијама, сва међустања имплицитно чувамо на системском стеку. Псеудокод описаног поступка је следећи:
Бектрекинг се разликује од грубе силе зато што одмах одсеца све оне путање за које закључи да не могу довести до решења проблема. Са друге стране, груба сила слепо иде до краја сваке могуће комбинације потеза.
Главна предност бектрекинга огледа се у томе што ће решење сигурно пронаћи, ако оно постоји. Мане бектрекинга су спорост, јер ипак проверава сва могућа решења, па је простор претраге експоненцијалан. Друга мана је меморијска захтевност, јер користи рекурзију, па дубина стабла израчунавања може бити изузетно велика.
Бектрекинг се користи за проблеме који имају огроман простор претраге, али постоје јасна правила која нам дозвољавају да рано одбацимо лоше путеве. Карактеристични проблеми су:
Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.
Напиши програм који одређује све положаје дама на шаховској табли димензије такве да се никоје две даме међусобно не нападају. Да се даме не би нападале у свакој врсти мора бити тачно једна дама, при чему никоје две даме нису у истој колони. Распоред је зато одређен низом од различитих бројева од до који редом представљају бројеве колона у којима се даме налазе у врстама од до .
Улаз: Са стандардног улаза се уноси број ().
Излаз: На стандардни излаз исписати све могуће распореде дама (у произвољном редоследу).
Задатак можемо лако решити грубом силом. Један (наиван) начин да се одреде сви могући распореди је да се грубом силом наброје сви могући распореди, да се испита који од њих представљају исправан распоред (у ком се даме не нападају) и да се испишу само они који тај критеријум задовољавају. Важно питање је репрезентација позиција. Најбоље решење се добија ако се распореди представе пермутацијама елемената скупа . Наиме ако се даме не нападају, у свакој врсти и у свакој колони се налази по тачно једна дама. Ако и врсте и колоне обележимо бројевима од до , тада је свакој колони једнозначно придружена врста у којој се налази дама у тој колони и распоред можемо представити низом тих бројева. Свакој колони је придружена различита врста (јер даме не смеју да се нападају), тако да је заиста у питању пермутација. Овај распоред у старту гарантује да се даме неће нападати ни хоризонтално, ни вертикално и једино је потребно одредити да ли се нападају по дијагонали. Две даме се налазе на истој дијагонали ако и само ако је хоризонтални размак између колона у којима се налазе једнак вертикалном размаку врста. За сваки пар дама проверавамо да ли се нападају дијагонално. Све пермутације можемо набројати на било који од начина описаних у задатку Све пермутације.
static void swap(int[] niz, int i, int j)
{
int tmp = niz[i];
niz[i] = niz[j];
niz[j] = tmp;
}
static bool konflikt(int[] permutacija)
{
// даме се нападају ако им је хоризонатлни размак једнак вертикалном
for (int i = 0; i < permutacija.Length; i++)
{
for (int j = i + 1; j < permutacija.Length; j++)
{
if (Math.Abs(i - j) == Math.Abs(permutacija[i] - permutacija[j]))
return true;
}
}
// ако провера прође, онда се не нападају
return false;
}
static void generisi_sve_permutacije(int[] permutacija, int i)
{
// ако смо распоредили све даме
if (i == 1)
{
// ако се даме не нападају, онда приказујемо распоред
if (!konflikt(permutacija))
{
for (int j = 0; j < permutacija.Length; i++)
Console.Write("{0} ", permutacija[j]);
Console.WriteLine();
}
}
// ако нисмо генерисали цео распоред
else
{
// онда примењујемо поступак за генерисање свих пермутација
for (int j = 0; j < i; j++)
{
swap(permutacija, i, j);
generisi_sve_permutacije(permutacija, i - 1);
swap(permutacija, i, j);
}
}
}
static void generisi_sve_permutacije(int n)
{
// помоћни низ у којем чувамо распоред
int[] permutacija = new int[n];
// дефинишемо почетни распоред
for (int i = 0; i < n; i++)
permutacija[i] = i + 1;
// рекурзивно генеришемо све могуће распореде
generisi_sve_permutacije(permutacija, n);
}Задатак можемо значајно елегантније да решимо применом претраге са одсецањем. Основна разлика овог у односу на претходно решење биће то што се коректност пермутација неће проверавати тек након што су генерисане у целости, већ ће бити проверавана коректност и сваке делимично попуњене пермутације. У многим случајевима веома рано ће бити откривено да су постављене даме на истој дијагонали и цела та грана претраге биће напуштена, што даје потенцијално велике добитке у ефикасности. Основна рекурзивна функција примаће вектор у коме се на позицијама из интервала налазе даме које су постављене у првих колона и задатак функције ће бити да испише све могуће распореде који проширују тај (додајући преостале даме у преостале колоне). Важна инваријанта ће бити да се даме које су постављене у тих првих k колона не нападају. Ако је , тада су све даме већ постављене, на основу инваријанте знамо да се не нападају и можемо да испишемо то решење (оно је јединствено и не може се проширити). У супротном, разматрамо све опције за постављање даме на позицију , тако да се даме у тако проширеном скупу не нападају. Пошто се зна да се даме на позицијама не нападају потребно је само проверити да ли се дама на позицији k напада са неком од дама постављених у првих колона. Размотримо шта су кандидати за вредности на позицији . Пошто не смемо имати два иста елемента низа тј. две исте врсте на којима се налазе даме, могли бисмо у делу низа на позицијама одржавати скуп елемената који су потенцијални кандидати за позицију . Међутим, пошто за проверу дијагонала морамо упоредити даму са свим претходно постављеним дамама, имплементацију можемо олакшати тако што на позицију стављамо шири скуп могућих кандидата (скуп свих врста од до ) а онда за сваки од тих бројева проверавамо да ли се јавио у претходном делу низа чиме би се даме нападале по хоризонтали и да ли би се постављањем даме у ту врсту она по дијагонали нападала са неком претходно постављеном дамом. Ако се установи да то није случај, тј. да се постављањем даме у ту врсту она не напада ни са једном од претходно постављених дама, онда је инваријанта задовољена и рекурзивно прелазимо на попуњавање наредних дама. Нема потребе за експлицитним поништавањем одлука које донесемо, јер ће се у свакој новој итерацији допуштена вредност уписати на позицију , аутоматски поништавајући вредност коју смо ту раније уписали.
// помоћна функција која проверава да ли се дама на позицији
// k напада са неком од дама на позицијама испред
static bool konflikt(int[] permutacija, int k)
{
// проверавамо све даме које су већ постављене
for (int i = 0; i < k; i++)
{
// ако се налазе у истој колони, нападају се
if (permutacija[i] == permutacija[k])
return true;
// ако су на истој дијагонали, нападају се
if (Math.Abs(k - i) == Math.Abs(permutacija[k] - permutacija[i]))
return true;
}
// ако прођу све провере, онда се не нападају
return false;
}
static void rasporedi_dame(int[] permutacija, int k)
{
// ако смо распоредили све даме, сигурно нема конфликта
if (k == permutacija.Length)
{
// и штампамо распоред
for (int j = 0; j < permutacija.Length; i++)
Console.Write("{0} ", permutacija[j]);
Console.WriteLine();
}
// ако нисмо распоредили све даме
else
{
// текућу даму покушавамо да поставимо на свако поље у реду
for (int i = 0; i < permutacija.Length; i++)
{
// постављамо даму
permutacija[k] = i;
// ако положај не прави конфликт
if (!konflikt(permutacija, k))
// рекурзивно постављамо наредну даму
rasporedi_dame(k + 1);
}
}
}
// пермутацију попуњавамо унапред, почевши од првог поља
static void rasporedi_dame(int n)
{
int[] permutacija = new int[n];
rasporedi_dame(permutacija, 0);
}Напиши програм који одређује све могуће збирове бројева који се могу добити тако што се обилазе поља квадратне матрице од горњег-левог угла, у сваком кораку се прелази доле или десно све док се не стигне до поља у доњем-десном углу.
Улаз: Са стандардног улаза се уноси број (), а затим у наредних редова врсте матрице (елементи сваке врсте су раздвојени размацима).
Излаз: На стандардни излаз исписати све могуће збирове, раздвојене размацима, сваки у посебном реду.
Задатак можемо решити исцрпним испитивањем свих путања. По узору на листање свих варијација градимо рекурзивну функцију која прима позицију тренутног поља и збир бројева на свим пољима којима се прошло док се није стигло до тренутног поља. Збир увећавамо за број на тренутном пољу. Ако је тренутно поље оно у доњем десном углу, онда смо стигли до краја и тренутни збир додајемо у скуп свих збирова. У супротном, вршимо рекурзивни позив у ком прелазимо на десно поље (ако већ нисмо у последњој колони) и рекурзивни позив у ком прелазимо на доње поље (ако већ нисмо у последњој врсти). У језику C# скуп можемо представити помоћу библиотечке колекције SortedSet, јер нам не требају дупликати вредности.
static void odredi_sve_zbirove(int[,] mat, int i, int j, int zbir, SortedSet<int> zbirovi)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// на збир додајемо вредности текућег поља
zbir += mat[i,j];
// ако смо стигли до излаза
if (i == m - 1 && j == n - 1)
{
// збир додајемо у скуп
zbirovi.Add(zbir);
}
// ако нисмо стигли до краја
else
{
// ако можемо, спуштамо се једно поље на доле и претрагу
// настављамо рекурзивно
if (i < m-1)
odredi_sve_zbirove(mat, i + 1, j, zbir, zbirovi);
// ако можемо, померамо се једно поље на десно и претрагу
// настављамо рекурзивно
if (j < n-1)
odredi_odredi_sve_zbirove(mat, i, j+1, zbir, zbirovi);
}
}
static int[] odredi_sve_zbirove(int[,] mat)
{
// помоћна колекција у којој чувамо збирове
SortedSet<int> zbirovi = new SortedSet<int>();
// рекурзивно одређујемо све збирове на траженом путу
odredi_sve_zbirove(mat, 0, 0, 0, zbirovi);
// на крају враћамо низ збирова
return zbirovi.ToArray();
}Приметимо да је у задатку смер кретања дефинисан као десно и доле, што значи да не постоји начин да се вратимо на већ посећено поље. Због тога, није нам потребна помоћна матрица у којој чемо чувати индикаторе посећених поља.
Напиши програм који одређује колико поднизова (не обавезно узастопних елемената) датог низа позитивних бројева има збир једнак датом броју .
Улаз: Са стандардног улаза се учитава број (), а затим у наредном реду позитивних реалних бројева раздвојених размацима. На крају се у новом реду учитава реалан број .
Излаз: На стандардни излаз исписати тражени број поднизова (два реална броја се могу сматрати једнакима ако се разликују за мање од ).
Једна могућност је да се задатак реши грубом силом, тј. да се наброје сви поднизови и да се за сваки од њих провери да ли му је збир једнак траженом. Набрајање поднизова се може постићи са било којом од техника за генерисање свих подскупова које су приказане до сада. Једна могућност имплементације подразумева да чувамо елементе подниза, тренутни број елемената подниза и параметар који одређује који део скупа је још потребно обрадити (то може бити дужина префикса низа који још није обрађен). Када се тај префикс испразни, проверавамо текући подниз. У супротном рекурзивно разматрамо могућност да последњи елемент префикса није или јесте укључен у подниз, уклањајући у оба случаја тај последњи елемент из префикса (тако што се смањује његова дужина).
static int broj_podnizova_datog_zbira(double[] niz, int n, double s, double[] podniz, int k)
{
// ако смо потрошили све елементе скупа
if (n == 0)
{
// рачунамо збир подниза дужине k
double zbirPodniza = 0;
for (int i = 0; i < k i++)
zbirPodniza += podniz[i];
// и враћамо 1 ако је збир подниза једнак траженом, иначе 0
if (Math.Abs(zbirPodniza - s) < 10e-5)
return 1;
else
return 0;
}
// ако нисмо потрошили све елементе низа
else
{
// рачунамо број поднизова датог збира
int broj = 0;
// који не укључују текући елемент низа (искључи)
broj += broj_podnizova_datog_zbira(niz, n-1, s, podniz, k);
// и који укључују текући елемент низа
podniz[k] = niz[n-1];
// и додајемо збир таквих на бројач (укључи)
broj += broj_podnizova_datog_zbira(niz, n-1, s, podniz, k+1);
// враћамо бројач
return broj;
}
}
static int broj_podnizova_datog_zbira(double[] niz, double s)
{
// одређујемо дужину низа
int n = niz.Length;
// помоћни низ у којем чувамо текући подскуп
double[] podniz = new double[niz.Length];
// рекурзивно одређујемо број подскупова збира s
return broj_podnizova_datog_zbira(niz, n-1, s, podniz, 0);
}Друга могућност имплементације претраге грубом силом је да као параметар рекурзивне функције просле- ђујемо тренутни циљни збир тј. разлику између траженог збира и збира елемената тренутно укључених у подниз. Сам подниз није неопходно одржавати. Ако је циљни збир једнак нули, то значи да је збир тренутног подниза једнак траженом и да смо нашли један задовољавајући подниз. У супротном, ако у скупу нема преосталих елемената, тада знамо да није могуће направити подниз траженог збира. У супротном уклањамо тренутни елемент из низа и разматрамо могућност да се он укључи и могућност да се не укључи у подниз. У првом случају умањујемо циљни збир за вредност тог елемента, а у другом циљни збир остаје непромењен.
static int broj_podnizova_datog_zbira(double[] niz, double s, int k)
{
// ако је преостали збир једнак 0, тада смо нашли подниз
if (Math.Abs(s) < 10e-5)
return 1;
// ако смо потрошили све елементе низа, онда подниз не постоји
if (k == niz.Length)
return 0;
// ако нисмо потрошили све елементе имамо две опције
// 1, да текући елемент укључимо у подниз, тиме и у рачунање збира
// 2, да текући елемент искључимо из подниза, тиме и из рачунања збира
// коначан број поднизова добијамо као збир ова два случаја
return broj_podnizova_datog_zbira(niz, s - niz[k], k + 1) // укључи
+ broj_podnizova_datog_zbira(niz, s, k + 1); // искључи
}
static int broj_podnizova_datog_zbira(double[] niz, double s)
{
// позивамо рекурзивну функцију која одређује број поднизова збира s
// почевши од елемента на индексу 0
return broj_podnizova_datog_zbira(niz, s, 0);
}Ефикаснија решења од решења грубом силом се могу добити применом различитих одсецања. Кључна ствар је да одредимо интервал у коме могу лежати збирови свих поднизова преосталих елемената низа. Пошто су сви елементи позитивни, најмања могућа вредност збира подниза је нула (у случају празног низа), док је највећа могућа вредност збира подниза једнака збиру свих елемената низа. Дакле, ако је циљни збир строго мањи од нуле или строго већи од збира свих елемената преосталог дела низа, тада не постоји ни један подниз чији је збир једнак циљном. Уместо да збир свих елемената низа рачунамо изнова у сваком рекурзивном позиву, можемо приметити да се у сваком наредном рекурзивном позиву низ само може смањити за један елемент, па се збир може рачунати инкрементално, умањивањем током рекурзије збира полазног низа за елементе уклоњене из низа.
static int broj_podnizova_datog_zbira(double[] niz, double s, double zbirPreostalih, int k)
{
// ако је преостали збир једнак 0, тада смо нашли подниз
if (Math.Abs(s) < 10e-5)
return 1;
// ако смо потрошили све елементе низа, онда подниз не постоји
if (k == niz.Length)
return 0;
// ако је тражени збир постао негативан, тј. збир елемената текућег подниза је већи
// од траженог збира, прекидамо претрагу
if (s + 10e-5 < 0)
return 0;
// ако је збир преосталих елемената мањи од вредности која нам треба да бисмо добили
// тражени збир, прекидамо претрагу
if (zbirPreostalih + 10e-5 < s)
return 0;
// ако нисмо потрошили све елементе имамо две опције
// 1, да текући елемент укључимо у подниз, тиме и у рачунање збира
// 2, да текући елемент искључимо из подниза, тиме и из рачунања збира
// коначан број поднизова добијамо као збир ова два случаја
return broj_podnizova_datog_zbira(niz, s - niz[i], zbirPreostalih - niz[k], k + 1) // укључи
+ broj_podnizova_datog_zbira(niz, s, zbirPreostalih - niz[k], k + 1); // искључи
}
static int broj_podnizova_datog_zbira(double[] niz, double s)
{
// крећемо од празног подниза, па је збир преосталих једнак збиру
// елемената низа
double zbirPreostalih = 0;
for (int i = 0; i < niz.Length; i++)
zbirPreostalih += niz[i];
// рекурзивно одређујемо тражени број поднизова
return broj_podnizova_datog_zbira(niz, s, zbirPreostalih, 0);
}Још једно могуће одсецање се може извршити када се установи да је најмањи од преосталих бројева у низу већи oд циљног збира. Ако је тај циљни збир позитиван, тада није могуће достићи га (јер празан подниз има збир нула, а било који непразан подниз има збир већи или једнак од тог минималног елемента). Минимални елемент преосталог дела низа је једноставно одредити ако се низ сортира (што можемо урадити пре почетка претраге).
static int broj_podnizova_datog_zbira(double[] niz, double s, double zbirPreostalih, int k)
{
// ако је преостали збир једнак 0, тада смо нашли подниз
if (Math.Abs(s) < 10e-5)
return 1;
// ако смо потрошили све елементе низа, онда подниз не постоји
if (k == niz.Length)
return 0;
// ако је збир преосталих елемената мањи од вредности која нам треба да бисмо добили
// тражени збир, прекидамо претрагу
if (zbirPreostalih + 10e-5 < s)
return 0;
// ако је текући елемент низа већи од циљног збира, прекидамо претрагу
if (niz[k] > s + 10e-5)
return 0;
// ако нисмо потрошили све елементе имамо две опције
// 1, да текући елемент укључимо у подниз, тиме и у рачунање збира
// 2, да текући елемент искључимо из подниза, тиме и из рачунања збира
// коначан број поднизова добијамо као збир ова два случаја
return broj_podnizova_datog_zbira(niz, s - niz[i], zbirPreostalih - niz[k], k + 1) // укључи
+ broj_podnizova_datog_zbira(niz, s, zbirPreostalih - niz[k], k + 1); // искључи
}
static int broj_podnizova_datog_zbira(double[] niz, double s)
{
// крећемо од празног подниза, па је збир преосталих једнак збиру
// елемената низа
double zbirPreostalih = 0;
for (int i = 0; i < niz.Length; i++)
zbirPreostalih += niz[i];
// сортирамо полазни низ
Array.Sort(niz);
// рекурзивно одређујемо тражени број поднизова
return broj_podnizova_datog_zbira(niz, s, zbirPreostalih, 0);
}Дато је тегова, за сваки тег позната је његова маса. Датим теговима треба измерити масу тако да се укупна маса изабраних тегова најмање разликује од . Написати програм којим се одређује минимална разлика при таквом мерењу.
Улаз: Прва линија стандардног улаза садржи природан број (). Следећих линија садрже реалне бројеве, сваки у посебној линији, који представљају масе датих тегова. Последња линија стандардног улаза садржи реалан број који представља масу коју меримо.
Излаз: На стандардном излазу приказати у једној линији минималну разлику добијену при мерењу, разлику приказати на две децимале.
Решење грубом силом подразумева да се испитају сви могући подскупови датог скупа тегова. Генерисање свих подскупова смо већ разматрали. На пример, набрајање можемо остварити помоћу функције која проналази лексикографски следећи подскуп. За сваки генерисани подскуп израчунавамо масу тегова, рачунамо одступање од жељене масе и ако је оно мање од тренутно најмањег одступања, ажурирамо минимум. Најмање одступање је могуће иницијализовати на жељену масу, јер масу увек можемо добити помоћу празног скупа тегова. Рецимо да бисмо заједно са подскупом могли одржавати и масу предмета у подскупу и приликом проналажења наредног подскупа ажурирати ту масу, чиме би се програм мало убрзао.
static bool sledeca_varijacija(bool[] indikatori)
{
// одређујемо преломну тачку, тј. први индекс са десне стране
// такав да елемент можемо увећати истовремено бришући вредности
// преко којих пређемо
int i = 0;
for (i = indikator.Length - 1; i >= 0 && indikatori[i]; i--)
indikatori = false;
// ако такав елемент не постоји, не постоји ни следећа варијација
if (i < 0)
return false;
// увећавамо елемент на индексу i
indikatori[i] = true;
return true;
}
static double merenje_sa_n_tegova(double[] tegovi, double s)
{
// помоћни низ којим представљамо варијацију
bool[] varijacija = new bool[tegovi.Length];
// иницијализујемо минималну разлику
double minRazlika = s;
// у петљи
do {
// рачунамо текућу масу подскупа тегова уз помоћ
// текуће варијације
double tekuciZbir = 0;
for (int i = 0; i < varijacija.Length; i++)
{
if (indikatori[i])
tekuciZbir += tegovi[i];
}
// одређујемо текућу разлику и ажурирамо минималну разлику
double razilka = Math.Abs(tekuciZbir - s);
if (razlika < minRazlika)
minRazlika = razlika;
// све док постоји следећа варијација, тј. подскуп
} while (sledeca_varijacija(indikatora))
// враћамо минималну разлику
return minRazlika;
}Приметимо да у овом решењу, уместо да експлицитно правимо подскупове, генеришемо варијације индикатора чиме су подскупови једнозначно одређени. Генерисање следећег подскупа се своди на генерисање следеће варијације.
Рекурзивну функцију која генерише све подскупове можемо модификовати тако да враћа вредност најмањег одступања од циљне тежине. Подсетимо се, функција прима текући подскуп елемената низа са позиција из интервала и на све начине га проширује елементима низа из интервала . Када је , генерисан је подскуп целог низа, израчунава се његово одступање и враћа се резултат (то је једино, па уједно и најмање одступање). У супротном се разматрају две могућности: елемент на позицији се или додаје у подскуп или се из подскупа изоставља. Вршимо два рекурзивна позива и мање од њихова два одступања нам даје тражено минимално одступање (то је најмање одступање за све подскупове који садрже елементе са позиција који су тренутно одабрани). Централни позив се врши за (у почетку ништа није одабрано и сви елементи тегови нам на располагању). Приметимо да заправо није неопходно да знамо који су тачно тегови тренутно одабрани, већ само њихову укупну масу.
static double merenje_sa_n_tegova(double[] tegovi, double ciljnaMasa, int i, double tekucaMasa)
{
// ако смо потрошили све тегове
if (i == tegovi.Length)
{
// тада је резултат разлика две измерене масе
return Math.Abs(ciljnaMasa - tekucaMasa);
}
// ако нисмо потрошили све тегове
else
{
// прво разматрамо минималну разлику коју можемо да добијемо без текућег тега (искључи)
double razlikaBez = merenje_sa_n_tegova(tegovi, ciljnaMasa, i + 1, tekucaMasa);
// затим разматрамо минималну разлику коју можемо да добијемо користећи текући тег (укључи)
double razlikaSa = merenje_sa_n_tegova(tegovi, ciljnaMasa, i + 1, tekucaMasa + tegovi[i]);
// резултат је мањи од та два броја
return Math.Min(razlikaBez, razlikaSa);
}
}
static double merenje_sa_n_tegova(double[] tegovi, double s)
{
// рекурзивно одређујемо минималну разлику
return merenje_sa_n_tegova(tegovi, s, 0, 0);
}Ефикасније решење можемо добити ако током исцрпне претраге применимо одсецање. На пример, након што одредимо најмању разлику r без укључивања текућег тега и ако додавање текућег тега даје масу која је већа од циљане и чија је разлика од циљане већа од r, тада додавањем текућег тега није могуће добити мању разлику (јер ће додавање наредних тегова моћи само да повећа масу).
static double merenje_sa_n_tegova(double[] tegovi, double ciljnaMasa, int i, double tekucaMasa)
{
// ако смо потрошили све тегове
if (i == tegovi.Length)
{
// тада је резултат разлика две измерене масе
return Math.Abs(ciljnaMasa - tekucaMasa);
}
// ако нисмо потрошили све тегове
else
{
// прво разматрамо минималну разлику коју можемо да добијемо без текућег тега (искључи)
double minRazlika = merenje_sa_n_tegova(tegovi, ciljnaMasa, i + 1, tekucaMasa);
// ако нас текући тег приближава циљној маси, само онда га користимо
if (tekucaMasa + tegovi[i] < ciljnaMasa + minRazlika) {
// (укључи)
double razlikaSa = merenje_sa_n_tegova(tegovi, ciljnaMasa, i + 1, tekucaMasa + tegovi[i]);
// ажурирамо резултат, ако треба
minRazlika = Math.Min(minRazlika, razlikaSa);
}
// резултат је мањи од та два броја
return minRazlika;
}
}
static double merenje_sa_n_tegova(double[] tegovi, double s)
{
// рекурзивно одређујемо минималну разлику
return merenje_sa_n_tegova(tegovi, s, 0, 0);
}Дато је врста тегова, за сваки тег позната је његова маса (реалан број) и колико тегова те врсте имамо на располагању (природан број). Датим теговима треба измерити масу са тачношћу од децимале. Написати програм којим се проверава да ли је то могуће.
Улаз: Прва линија стандардног улаза садржи природан број (). Свака од следећих линија садржи реалан и природан број одвојени једним бланко карактером, који редом представљају масу тега и број тегова те масе које имамо на располагању. Последња линија стандардног улаза садржи реалан број који представља масу коју меримо.
Излаз: На стандардном излазу приказати поруку da ако је тражено мерење могуће извршити, а иначе приказати поруку ne.
Решење грубом силом подразумева да се испитају све могућности и да се утврди да ли је нека од њих задо- вољавајућа. Свака могућност у овом случају је нека варијација са понављањем, при чему је ограничење на свакој позицији у варијацији другачије (на свакој позицији тј. од сваке врсте тегова можемо узети највише онолико тегова колико постоји тегова те врсте). Генерисање свих варијација са понављањем смо већ разматрали. Крећемо од варијације у којој није узет ни један тег, у сваком кораку за текућу варијацију рачунамо измерену масу и проверавамо да ли је она једнака траженој (до на задату прецизност ). Ако јесте, тражено мерење постоји, па петљу можемо прекинути, а ако није, прелазимо на наредну варијацију, све док таква постоји. Приликом генерисања наредне варијације крећемо се од краја (последње врсте тегова) и тражимо врсту тегова која није достигла максимум, тј. где је број узетих тегова у варијацији мањи од броја расположивих тегова те врсте. Ако таква врста тегова не постоји, нема ни следеће варијације, а у супротном узимамо још један тег те врсте и уклањамо све тегове наредних врста.
static bool sledeca_varijacija_sa_ponavljanjem(int[] brojUzetihTegova, int[] brojTegova)
{
// тражимо преломну тачку
int i = brojTegova.Length - 1;
while (i >= 0 && brojUzetihTegova[i] == brojTegova[i])
{
brojUzetihTegova[i] = 0;
i--;
}
// ако преломна тачка не постоји, нема ни следеће варијације
if (i < 0)
return false;
// иначе увећавамо први елемент који се може увећати
brojUzetihTegova[i]++;
return true;
}
static bool merenje_sa_n_tegova(double[] maseTegova, int[] brojTegova, double s)
{
// креирамо помоћни низ у којем чувамо варијацију
int n = maseTegova.Length;
int[] brojUzetihTegova = new int[n];
// индикатор да ли смо измерили тражену масу
bool izmereno = false;
// у петљи
do {
// рачунамо укупну масу текуће варијације тегова
double tekucaMasa = 0;
for (int i = 0; i < n; i++)
tekucaMasa += brojUzetihTegova[i] * maseTegova[i];
// проверавамо да ли је довољно близу циљној маси и ажурирамо индикатор
// ако треба
if (Math.Abs(tekucaMasa - s) < 10e-2)
izmereno = true;
// све док постоји следећа варијација или не измеримо циљну масу
} while(sledece_sledeca_varijacija_sa_ponavljanjem(brojUzetihTegova, brojTegova) && !izmereno);
// враћамо резултат мерења
return izmereno;
}Све варијације можемо генерисати и рекурзивном функцијом и тада током генерисања можемо извршити и одсецање којим проверу чинимо ефикаснијом. Дефинишемо функцију која на основу одабраних тегова свих врста из интервала покушава да изврши мерење додајући тегове чије су врсте из интервала , при чему се након додавања тегова врсте циљна маса смањује. Ако је при уласку у рекурзију циљна маса једнака нули (до на допуштену прецизност), значи да је почетна маса успешно измерена помоћу тегова чије су врсте из интервала и функција може да констатује да је мерење могуће. У супротном, ако је не постоје тегови који би се додали и мерење није могуће. Такође, ако је циљна маса негативна (и мања од допуштене толеранције) мерење није могуће (јер се додавањем тегова циљна маса не може повећати). У супротном разматрамо разне могућности за додавање тегова врсте . У петљи проверавамо број тих тегова од па све до укупног броја тих тегова. Ако током петље установимо да се додавањем тих тегова превазишла циљна маса (укључујући и допуштену толеранцију) петљу можемо прекинути. У сваком кораку петље вршимо рекурзивни позив и ако било који од њих врати вредност true констатујемо да је пронађено успешно мерење. Ако се петља изврши и сви рекурзивни позиви врате false, тада мерење није могуће.
static bool merenje_sa_n_tegova(double[] maseTegova, double[] brojTegova, double s, int i)
{
// ако је измерена маса довољно близу, онда је мерење завршено
if (Math.Abs(s) < 10e-2)
return true;
// ако смо потрошили све тегове, онда не можемо да измеримо масу
if (i == maseTegova.Length)
return false;
// ако је текућа маса изабраних тегова већа од циљне масе, онда не можемо да
// извршимо мерење
if (s < 0)
return false;
// иначе, на тас додајемо један по један тег све док не исцрпимо све тегове врсте i
// бројимо од 0, што значи да у том случају искључујемо тег из мерења
for (int k = 0; k < brojTegova[i]; k++)
{
// ако је изабрана количина тегова већа од циљне масе, мерење не можемо да извршимо
if (k*maseTegova[i] > s + 10e-2)
break;
// ако је мерење успешно, прекидамо претрагу
if (merenje_sa_n_tegova(maseTegova, broj_belih_oblasti, s - k*maseTegova[i], i+1))
return true;
}
// ако пробамо све тегове и не нађемо решење, мерење није могуће
return false;
}
static bool merenje_sa_n_tegova(double[] maseTegova, double[] brojTegova, double s)
{
return merenje_sa_n_tegova(maseTegova, brojTegova, s, 0);
}Дата је матрица попуњена вредностима и ( означава проходно поље а препреку). Написати програм којим се одређује број корака на најдужем проходном путу од дате позиције до дате позиције . Под једним кораком подразумева се прелазак са поља на једно од суседна поља. Са сваког поља дозвољено је прећи на суседна поља (горе, доле, лево и десно) ако су проходна. Сва поља на путу морају бити различита (на једно поље можемо стати највише једанпут). На стартном ни на циљном пољу се не налази препрека.
Улаз: Прва линија стандардног улаза садржи димензије матрице и (), два природна броја одвојена једним размаком. Затим се на стандардном улазу налазе елементи матрице (у линија по бројева одвојених са по једним размаком). У последњој линији стандардног улаза налазе се природна броја , , , (, ).
Излаз: На стандардном излазу приказати природан број који представља број корака на најдужем проходном путу од стартне позиције до циљне позиције . Ако проходан пут не постоји приказати .
Задатак решавамо исцрпном рекурзивном претрагом. Рекурзивна функција прима матрицу која садржи позиције препрека, њену димензију, помоћну матрицу у којој се памти да ли је неко поље већ посећено (јер пут не сме два пута да посети једно те исто поље) и координате текућег и циљног поља. Ако је текуће поље једнако циљном, најдужи пут има дужину нула (не смемо да кренемо неким дужим путем, јер бисмо се тада вратили на исто поље, што је забрањено). У супротном обележавамо да је текуће поље посећено, анализирамо њему четири суседна поља и ако су доступна (нису раније посећена и на њима није препрека) рекурзивно проналазимо дужину најдужег пута до циља. Дужина најдужег пута из текућег поља је онда за један већа од највеће дужине пута из неког од та четири суседна поља (разматрају се само они путеви који успешно стижу до циља).
// дефинишемо листу суседа (4-повезаност)
static int[,] susedi = new int[4,2] {
{-1,0}, {0,1}, {1,0}, {0,-1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static int najduzi_put(int[,] mat, int i, int j, int mc, int nc, bool[,] poseceni)
{
// ако смо стигли до циља, дужина пута је 0
if (i == mc && j == nc)
return 0;
// обележавамо текуће поље као посећено
poseceni[i,j] = true;
// на почетку, претпостављамо да не постоји пут из текућег поља
int maks = - 1;
// разматрамо све суседе
for (int k = 0; k < susedi.GeLength(0); k++)
{
// реконструишемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако је сусед у матрици, ако је слободно поље и ако није посећен
if (u_matrici[ii,jj] && mat[ii,jj] == 0 && !poseceni[ii,jj])
{
// одређујемо дужину најдужег пута из суседа
int put = najduzi_put(mat, ii, jj, mc, nc, poseceni);
// ако такав пут постоји, по потреби ажурирамо максималну дужину
if (put >= 0)
maks = Math.Max(maks, put + 1);
}
}
// након што анализирамо све путеве из текућег поља,
// обележавамо га као слободног да би могло да се искористи у неком
// другом путу
poseceni[i,j] = false;
// враћамо дужину најдужег пута
return maks;
}
static int najduzi_put(int[,] mat, int ms, int ns, int mc, int nc)
{
// одређујемо димензију матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој ћемо памтити посећена поља
bool[] poseceni = new bool[m,n];
// рекурзивно одређујемо најдужи пут
return najduzi_put(int[,] mat, ms, ns, mc, nc, poseceni);
}Дат је скуп од предмета, за сваки предмет позната је његова вредност (реалан број). Предмете треба да поделе два брата тако да се укупнa вредност предмета које појединачно браћа добијају минимално разликују. При подели предмета сваки брат добија целе предмете и сваки предмет после поделе припада неком брату. Написати програм којим се одређује минимална разлика вредности коју браћа добијају при братској подели.
Улаз: Прва линија стандардног улаза садржи природан број (). Следећих линија садрже реалне бројеве, сваки у посебној линији, који представљају вредности предмета.
Излаз: На стандардном излазу приказати у једној линији минималну разлику вредности добијену при брат- ској подели, разлику приказати на две децимале.
Задатак се грубом силом решава тако што се наброје сви подскупови скупа од n елемената. Предмети који припадају подскупу се тумаче као предмети првог брата, док се предмети који не припадају том подскупу тумаче као предмети другог брата. Набрајање свих подскупова могуће је вршити тако што се за дати подскуп пронађе наредни подскуп у лексикографском редоследу. Подскупове можемо да кодирамо варијацијама скупа . Мана овог решења је то што се за сваки подскуп изнова рачунају збирови предмета једног и другог брата.
static bool sledeca_varijacija(bool[] skup)
{
// тражимо преломну тачку, тј. први елемент са десна
// који се може поставити на true
int i = skup.Length - 1;
while (i >= 0 && skup[i] == true)
{
skup[i] = false;
i--;
}
// ако преломна тачка не постоји, генерисали смо све подскупове
if (i < 0)
return false;
// постављамо елемент на true
skup[i] = true;
return true;
}
// помоћни метод одређује разлику вредности елемената након поделе
static double razlika(double[] predmeti, bool[] skup)
{
// на почетку су вредности елемената у оба скупа 0
double prvi = 0, drugi = 0;
// пролазимо кроз варијацију и рачунамо вредности подскупова
for (int i = 0; i < skup.Length; i++)
{
if (skup[i])
prvi += predmeti[i];
else
drugi += predmeti[i];
}
// враћамо разлику вредности
return Math.Abs(prvi - drugi);
}
static double podela(double[] predmeti)
{
// подскупове кодирамо варијацијама
bool[] varijacija = new bool[predmeti.Length];
// иницијализујемо минимум
double minRazlika = double.MaxValue;
// у петљи
do
{
// одређујемо разлику вредности у скуповима након текуће поделе
double r = razlika(predmeti, varijacija);
// по потреби ажурирамо минималну разлику
if (r < minRazlika)
minRazlika = r;
// све док постоји наредна варијација
} while (sledeca_varijacija(varijacija));
// враћамо тражени резултат
return minRazlika;
}Испитивање свих могућности можемо реализовати и рекурзивном исцрпном претрагом. За сваки предмет испитујемо могућност да припадне једном и да припадне другом брату. Рекурзивна функција прима низ од предмета које је преостало да распореди, збир вредности већ распоређених предмета који су припали једном и збир вредности већ распоређених предмета који су припали другом брату. Излаз из рекурзије је случај када нема више предмета које треба распоредити и у том случају знамо разлику вредности предмета које су браћа добила. У супротном први (или последњи) предмет из низа додајемо првом брату и рекурзивно делимо преостале предмете, затим исти предмет додајемо другом брату и рекурзивно делимо преостале предмете и као резултат враћамо мању од разлика које су постигнуте на ова два начина.
static double podela(double[] predmeti, double zbirPrvog, double zbirDrugog, int k)
{
// ако смо распоредили све предмете
if (k == predmeti.Length)
{
// враћамо резултат поделе
return Math.Abs(zbirPrvog - zbirDrugog);
}
// ако нисмо потрошили све предмете
else
{
// текући предмет прво додељујемо првом скупу и рекурзивно одређујемо
// најмању разлику са таквом поделом
double r1 = podela(predmeti, zbirPrvog + predmeti[i], zbirDrugog, k + 1);
// текући предмет затим додељујемо другом скупу и рекурзивно одређујемо
// најмању разлику са таквом поделом
double r2 = podela(predmeti, zbirPRvog, zbirDrugog + predmeti[i], k + 1);
// резултат је мања од те две разлике
return Math.Min(r1, r2);
}
}
static double podela(double[] predmeti)
{
// крећемо од празних подскупова и рекурзивно одређујемо минималну разлику
return podela(predmeti, 0, 0, 0);
}Могуће је извршити и одређена одсецања у исцрпној претрази. Наиме, ако знамо збир преосталих предмета које треба распоредити и ако утврдимо да би доделом свих тих предмета брату који је тренутно добио мање тај брат и даље имао мању вредност, онда је јасно да се разлика минимизује баш на тај начин. На пример, ако је први брат добио , други , и треба распоредити још предмете од , и , јасно је да све њих треба дати другом брату и да се тиме добија разлика од . Овим се избегава анализа могућности (да се неки од тих предмета додели првом брату). Дакле, пожељно је да прво поделимо велике предмете, а онда да ове мање предмете делимо овако групно. Стога низ вредности на почетку сортирамо тако да се у старту врши подела предмета са већом вредношћу.
Још једна оптимизација је да се разлика не мења ако браћа размене све предмете које имају. Да би се ова симетрија разбила (и избегла анализа суштински идентичних подела), у старту ћемо одабрати да се први предмет додели првом брату.
static double podela(double[] predmeti, double ukupno, double zbirPrvog, double zbirDrugog, int k)
{
// ако смо распоредили све предмете
if (k == predmeti.Length)
{
// враћамо резултат поделе
return Math.Abs(zbirPrvog - zbirDrugog);
}
// ако нисмо потрошили све предмете
else
{
// ако је разлика у корист другог скупа превелика, све додајемо првом скупу
if (zbirPrvog + ukupno <= zbirDrugog)
return zbirDrugog - (zbirPrvog + ukupno);
// ако је разлика у корист првог скупа превелика, све додајемо другом скупу
if (zbirDrugog + ukupno <= zbirPrvog)
return zbirPrvog - (zbirDrugog + ukupno);
// текући предмет прво додељујемо првом скупу и рекурзивно одређујемо
// најмању разлику са таквом поделом
double r1 = podela(predmeti, ukupno - predmeti[k], zbirPrvog + predmeti[i], zbirDrugog, k + 1);
// текући предмет затим додељујемо другом скупу и рекурзивно одређујемо
// најмању разлику са таквом поделом
double r2 = podela(predmeti, ukupno - predmeti[k], zbirPRvog, zbirDrugog + predmeti[i], k + 1);
// резултат је мања од те две разлике
return Math.Min(r1, r2);
}
}
static double podela(double[] predmeti)
{
// сортирамо предмете опадајуће по вредности
Array.Sort(predmeti, (x,y) => y.CompareTo(x));
// рачунамо укупну вредност свих предмета
double ukupno = 0;
for (int i = 0; i < predmeti.Length; i++);
// крећемо од празних подскупова и рекурзивно одређујемо минималну разлику
return podela(predmeti, ukupno - predmeti[0], predmeti[0], 0, 1);
}Низ је карактеристичан по томе што преставља пермутацију бројева од до и збир било која два суседна елемента је квадрат неког природног броја. Напиши програм који за дато одређује лексикографски најмању пермутацију бројева од до у којој је збир било која два суседна елемента квадрат неког природног броја.
Улаз: Са стандардног улаза се учитава број ().
Излаз: На стандардни излаз исписати тражену пермутацију (сви бројеви у истом реду праћени са по једним размаком) или текст nema ако тражена пермутација не постоји.
Задатак решавамо исцрпном бектрекинг претрагом. Тражени низ градимо елемент по елемент. На прво место уписујемо редом један по један елемент од до , а затим позивамо рекурзивну функцију да попуни остатак низа. Та функција на текуће место у низу покушава да постави све оне елементе који са претходним елементом низа дају потпун квадрат (низ свих пуних квадрата можемо израчунати унапред), а који се не јављају у до тада попуњеном делу низа (посебно ћемо одржавати скуп свих до тада попуњених елемената у облику низа логичких вредности таквог да је на месту вредност тачно ако и само ако се елемент јавља у попуњеном делу низа). Успешан излаз из рекурзије је када је цео низ попуњен (када текућа позиција која се попуњава постане једнака дужини низа).
static bool pun_kvadrat(int[] niz, int k, bool[] iskorisceni, Lista<int> kvadrati)
{
// ако смо попунили цео низ
if (k == niz.Length)
{
// генерисали смо тражену пермутацију
for (int i = 0; i < niz.Length; i++)
Console.Write("{0} ", niz[i]);
Console.WriteLine();
// враћамо сигнал да треба да прекинемо рекурзију
return true;
}
else
{
// пролазимо кроз све могуће квадрате
for (int i = 0; i < kvadrati.Count; i++)
{
// рачунамо кандидате за наредни елемент
int dopuna = kvadrati[i] - niz[k-1];
// ако кандидат постоји и није искоришћен
if (1 <= dopuna && dopuna <= niz.Length && !iskorisceni[dopuna])
{
// проширујемо пермутацију тим кандидатом
niz[k] = dopuna;
// обележавамо га као искоришћеног
iskorisceni[dopuna] = true;
// рекурзивно генеришемо тражену пермутацију ако постоји
// и прекидамо претрагу ако нађемо пермутацију
if (pun_kvadrat(niz, k + 1, iskorisceni, kvadrati))
return true;
// текући елемент обележавамо као слободан и прелазимо на
// наредну итерацију
iskorisceni[dopuna] = false;
}
}
// ако нисмо нашли пермутацију, настављамо претрагу
return false;
}
}
static bool pun_kvadrat(int n)
{
// низ индикатора који нам говоре да ли је број већ искоришћен
bool iskoriseni = new bool[n];
// низ квадрата који нам говоре шта треба да буду збирови суседних
List<int> kvadrati = new List<int>();
// попуњавамо могуће збирове
for (int i = 1; i*i <= n+(n-1); i++)
kvadrati.Add(i*i);
// низ у којем ћемо чувати тражену пермутацију
int[] niz = new int[n];
// пролазимо кроз све могуће бројеве
for (int i = 1; i <= n; i++)
{
// постављамо их на прво место у низу
niz[0] = i;
// обележавамо их као искоришћене
iskoriseni[i] = true;
// рекурзивно генеришемо тражену пермутацију ако постоји
if (pun_kvadrat(niz, 1, iskorisceni, kvadrati))
return true;
// текући елемент обележавамо као слободан и прелазимо на
// наредну итерацију
iskoriseni[i] = false;
}
// нисмо нашли пермутацију
return false;
}