Perrinkimas ir grįžimo metodas

Modern computers are so fast that brute force can be an effective and
honourable way to solve problems.
Šiuolaikiniai kompiuteriai yra tokie spartūs, kad perrinkimas gali būti
efektyvus ir garbingas būdas uždaviniams spręsti.
Steven S. Skienna, Miguel A. Revilla, „Programming Challenges“

1852 metais matematikas F. Gatris (Francis Guthrie) paskelbė hipotezę, teigiančią, jog kiekvienam žemėlapiui nuspalvinti taip, kad jokios dvi gretimos valstybės nebūtų nuspalvintos ta pačia spalva, pakanka keturių spalvų. Daugelis matematikų siūlė šios hipotezės įrodymus, tačiau vis išaiškėdavo, kad jie neteisingi [1]. Hipotezė pagaliau tapo teorema (buvo įrodyta) 1976 metais, o dalis įrodymo rėmėsi kompiuteriu išnagrinėtomis 1476 situacijomis. Kompiuterio programa veikė šimtus valandų, o žmonėms nepakako ir šimto metų. Taigi nors perrinkimo metodai dažnai būna neefektyvūs, spartėjant kompiuteriams šis sprendimo būdas (visų galimų sprendinių išbandymas) tam tikrais atvejais gali būti priimtinas, ypač jei perrinkimą pavyksta optimizuoti.

Formaliai perrinkimą galima apibrėžti kaip uždavinių sprendimo metodą, kai išbandomi visi galimi sprendiniai.

Šiame skyrelyje susipažinsime su patogiu metodu perrinkimui realizuoti – grįžimo metodu. Grįžimo metodas (angl. Backtracking) – tai sistemingas būdas spręsti uždaviniams, kurių sprendinys yra kintamųjų p_1, p_2, \dots, p_n reikšmių rinkinys, tenkinantis kokius nors reikalavimus. Prisiminkime, pavyzdžiui, Keliaujančio pirklio uždavinį [2]: šiuo atveju kintamųjų p_1, p_2, \dots, p_n reikšmėms reikia priskirti skirtingus miestų numerius taip, kad ši miestų aplankymo tvarka ir būtų pageidaujamas maršrutas.

Pagrindinė grįžimo metodo idėja tokia: paeiliui renkamos visų galimų kintamųjų reikšmės ir tikrinama, ar tenkinami reikalavimai, o radus sprendinį arba situaciją, kai reikalavimai netenkinami, grįžtama per vieną žingsnį atgal ir parenkama nauja atitinkamo kintamojo reikšmė.

Programuojant grįžimo metodą dažnai naudojama rekursija. Panagrinėsime abstrakčių kombinatorinių uždavinių sprendimų schemas bei porą konkrečių uždavinių.

Kėlinių generavimas

Visi galimi trijų prekių išdėstymo lentynoje būdai

Fig. 11 Visi galimi trijų prekių išdėstymo lentynoje būdai

Sakykime, parduotuvės lentynoje vienoje eilėje reikia išdėlioti n skirtingų prekių. Raskime visus skirtingus būdus, kaip tai padaryti. Uždavinys yra ekvivalentus visų n ilgio kėlinių be pasikartojimų generavimo uždaviniui.

Kas gi tas kėlinys be pasikartojimų? Tarkime, turime aibę iš n elementų. Kiekviena visų (skirtingų) n elementų seka vadinama kėliniu be pasikartojimų. Taigi kėliniai vienas nuo kito skiriasi tik elementų išsidėstymu vienas kito atžvilgiu.

Parašykime algoritmą, kuris išspausdintų visus prekių išdėstymo būdus. Prekes laikysime sunumeruotomis nuo 1 iki n.

Atkreipkite dėmesį – šis uždavinys priskiriamas įžangoje minėtai uždavinių klasei: m-ojoje vietoje padėtą prekę (prekės numerį) pažymėjus p_m, reikia rasti kintamųjų p_1, \dots, p_n reikšmių (kintančių nuo 1 iki n) rinkinius, tenkinančius vieną reikalavimą – visos reikšmės turi būti skirtingos; tuos rinkinius atspausdinti.

Uždavinį galima išreikšti rekursyviai, t. y. suskaidyti į tokius pat, tik mažesnius, uždavinius. Tegu procedūra generuok(m, n) priskirs reikšmes kintamiesiems nuo p_m-ojo iki p_n-ojo. Tuomet jos veikimas galėtų būti toks:

  • Jei m \leq n, imti po vieną visas dar lentynoje nepadėtas prekes ir su kiekviena atlikti tokius veiksmus:
    • Prekę padėti į m-ąją poziciją lentynoje (pm := prekės numeris).
    • Sudėti į lentyną likusias prekes (priskirti reikšmes kintamiesiems nuo p_m+1 iki p_n) – toks pat uždavinys, taigi iškviesti generuok(m + 1).
    • Prekę, esančią m-ojoje pozicijoje, paimti nuo lentynos.
  • Jei m > n, tai ši procedūra iškviesta jau išdėliojus visas prekes lentynoje, todėl atspausdiname kintamųjų p_1, p_2, \dots, p_n reikšmes.

Norint patikrinti, kurios prekės jau sudėtos į lentyną, galima peržiūrėti jau priskirtas reikšmes. Tačiau paprasčiau ir efektyviau paskirti globalų loginį masyvą panaudotas, ir, padėjus į lentyną prekę su numeriu i, pažymėti, jog šis numeris jau panaudotas (panaudotas[i] := true), o paėmus prekę nuo lentynos – atstatyti buvusią reikšmę (panaudotas[i] := false).

const MAXN = 20;        { didžiausia n reikšmė }
var p : array [1..MAXN] of integer;
    panaudotas : array [1..MAXN] of boolean;
procedure spausdink(m: integer);
var i : integer;
begin
    for i := 1 to m do
        write(p[i], ' ');
    writeln;
end;
procedure generuok(m, { parenkamas elementas m-ajai pozicijai }
                   n : integer);
var i : integer;
begin
    { jei m > n, tai ši procedūra iškviesta jau sugeneravus visą kėlinį }
    if m > n then
       spausdink(n)
    else
        for i := 1 to n do
            if not panaudotas[i] then begin
                panaudotas[i] := true;
                p[m] := i;
                generuok(m + 1, n);
                panaudotas[i] := false;
            end;
end;

Kad galėtume išspausdinti visas trijų prekių išdėliojimo lentynoje tvarkas, įvykdome:

n := 3;
for i := 1 to n do
    panaudotas[i] := false;
generuok(1, n);
Procedūros generuok vykdymą vaizduojantis medis  (n = 3)

Fig. 12 Procedūros generuok vykdymą vaizduojantis medis  (n = 3)

Parašytą procedūrą nesunku pritaikyti kitiems uždaviniams – vietoj spausdinimo galima atlikti kokius nors kitus veiksmus. Spausdinimą iškėlėme į atskirą procedūrą norėdami paryškinti sprendimo struktūrą.

Koks gi parašytos programos sudėtingumas, t. y. kaip atliekamų veiksmų skaičius priklauso nuo n? Algoritmas generuoja visus įmanomus skaičių nuo 1 iki n išdėstymo į eilę būdus. Kiek jų yra? Pirmąjį skaičių galima parinkti n būdų, antrąjį skaičių – (n - 1) būdu (kadangi vienas skaičius jau pasirinktas), trečiąjį skaičių – (n - 2) būdais (du skaičiai jau parinkti) ir t. t. Gauname, kad yra n(n – 1)(n – 2)\cdot \dots \cdot 2 \cdot 1 = n! skirtingų būdų išdėstyti n skaičių į eilę. Taigi procedūros generuok sudėtingumas yra O(n!). Pavyzdžiui, kai n = 13, tai vieną atspausdintą eilutę sudaro apie 30 simbolių, o eilučių yra 13! = 6227020800 ir programa spausdintų daugiau nei 150 gigabaitų teksto… (jei, žinoma, sulauktume veikimo pabaigos).

Aštuonių valdovių uždavinys

Išspręsime klasikinį aštuonių valdovių uždavinį.

Užduotis. 8 \times 8 dydžio šachmatų lentoje reikia išdėlioti 8 valdoves taip, kad jokiu būdu neatsidurtų dvi vienoje eilutėje, stulpelyje arba įstrižainėje (t. y. nė viena negalėtų nukirsti kitos tolesniu ėjimu). Uždavinio formuluotę išplėsime ir ieškosime, kaip n valdovių surikiuoti n \times n dydžio lentoje.
Aštuonių valdovių išdėstymo pavyzdys

Fig. 13 Aštuonių valdovių išdėstymo pavyzdys

Šį uždavinį taip pat spręsime grįžimo metodu. Pavyzdžiui, lentos langelius sunumeravę nuo 1 iki n^2, kiekvienai valdovei galime skirti po vieną langelį (numerį) taip, kad būtų tenkinama uždavinio sąlyga. Tačiau spręsdami uždavinį šiuo būdu, turėtume išnagrinėti labai didelį variantų skaičių. Variantų skaičius, kuriuo aštuonioms valdovėms galima paskirstyti langelių numerius nuo 1 iki 64 yra 64 \cdot 63 \cdot 62 \cdot 61 \cdot 60 \cdot 59 \cdot 58 \cdot 57 = 178\ 462\ 987\ 637\ 760 būdų.

Be abejo, didžioji dalis šių variantų visiškai neįdomūs, nes labai tikėtina, kad kurios nors dvi valdovės atsidurs toje pačioje eilutėje, stulpelyje arba įstrižainėje. Atkreipkime dėmesį – kiekviename stulpelyje turės atsidurti lygiai viena valdovė; stulpelių yra tiek, kiek ir valdovių, o viename stulpelyje dvi valdovės stovėti negali.

Taigi galima šiek tiek kitaip vykdyti perrinkimą. Tegu p_k yra valdovės, stovinčios k-ajame stulpelyje, eilutės numeris. Kintamiesiems p_1, p_2, \dots, p_n reikia priskirti reikšmes nuo 1 iki n taip, kad jokios dvi valdovės neatsidurtų vienoje eilutėje arba įstrižainėje.

Šitaip atliekant perrinkimą, net nepaisant įstrižainių apribojimo, nagrinėjamų variantų bus tik n!. Palyginkite – aštuonių valdovių atveju teks išnagrinėti 8! = 40\ 320 variantų vietoj 178\ 462\ 987\ 637\ 760.

Perrenkant valdovių rikiavimo būdus, visai nesudėtinga sekti, kuriose eilutėse valdovės jau pastatytos – tam galima skirti loginį masyvą.

Tačiau kaip elgtis su įstrižainėmis? Patikrinti, ar dvi valdovės nestovi vienoje įstrižainėje, galima sustačius visas valdoves. Tačiau išsisuksime paprasčiau (ir efektyviau) pastebėję, kad įstrižaines taip pat nesunku sunumeruoti: vienoje įstrižainėje esančių langelių eilutės ir stulpelio numerių suma arba skirtumas yra pastovus.

Taigi žinodami langelio koordinates (stulpelio ir eilutės numerius), galime pasakyti, kuriai įstrižainei priklauso šis langelis. Įstrižainėms skiriame du loginius masyvus su indeksais atitinkamai [2..2n] ir [-n + 1..n - 1], kuriuose žymėsime, ar įstrižainės jau užimtos.

Table 1 Kairėje pavaizduotos įstrižainės numeruojamos eilutės ir stulpelio numerių suma, dešinėje – skirtumu
  1 2 3 4 5       1 2 3 4 5
1 2 3 4 5 6     1 0 -1 -2 -3 -4
2 3 4 5 6 7     2 1 0 -1 -2 -3
3 4 5 6 7 8     3 2 1 0 -1 -2
4 5 6 7 8 9     4 3 2 1 0 -1
5 6 7 8 9 10     5 4 3 2 1 0

Parašysime procedūrą statyk(k, n), perrenkančią sprendinius grįžimo metodu, kuri visais įmanomais būdais sudėlios lentoje valdoves nuo k-osios iki n-osios. k-oji valdovė bus statoma k-ajame stulpelyje. Taigi procedūra turi bandyti pastatyti k-ąją valdovę nepažeisdama apribojimų, o pastačius – pažymėti užimtas eilutę ir įstrižaines, ir iškviesti statyk(k + 1, n).

Jei iškvietus procedūrą parametro k reikšmė viršija n (k > n), tai reiškia, kad ši procedūra buvo iškviesta sudėliojus visas n valdovių, taigi radus sprendinį. Viena vertus, sudėliojus visas n valdovių, procedūros statyk būtų galima nebekviesti, tačiau dėl šio papildomo iškvietimo programa tampa paprastesnė ir aiškesnė. Tai dažnai naudojama rekursyviose procedūrose.

Procedūroje skaičiuosime, kiek yra sprendinių, t. y. būdų išdėlioti valdoves lentoje. Tačiau nesunku modifikuoti procedūrą taip, kad ši rastus sprendinius išspausdintų – tuomet dar reikėtų saugoti, kur lentoje statomos valdovės.

const MAXN = 12;
var eilutė : array [1..MAXN] of boolean;
    įstr1 : array [2..2 * MAXN] of boolean;
    įstr2 : array [-MAXN + 1..MAXN - 1] of boolean;
    sprendinių_sk : longint;

procedure statyk(k, { valdovė statoma k-ajame stulpelyje }
                 n : integer { reikia pastatyti n valdovių });
var i : integer;
begin
    if k > n then { rastas sprendinys }
        sprendinių_sk := sprendinių_sk + 1
    else
        for i := 1 to n do
            if not (eilutė[i] or
                    įstr1[i + k] or
                    įstr2[i - k])
            then begin
                eilutė[i] := true;
                įstr1[i + k] := true;
                įstr2[i  k] := true;
                { bandoma pastatyti likusias valdoves }
                statyk(k + 1, n);
                eilutė[i] := false;
                įstr1[i + k] := false;
                įstr2[i - k] := false;
            end;
end;
Valdovių uždavinio rekursijos medis, kai n=4

Fig. 14 Valdovių uždavinio rekursijos medis, kai n=4

Gretiniai, deriniai ir poaibiai

Azartiniai žaidimai buvo dingstis atsirasti kombinatorikai

Fig. 15 Azartiniai žaidimai buvo dingstis atsirasti kombinatorikai

Ankstesniame skyrelyje (Kėlinių generavimas) nagrinėjome, kiek ir kokių kombinacijų galima sudaryti iš įvairių objektų, kad būtų tenkinamos vienokios ar kitokios sąlygos. Šitai nagrinėja matematikos šaka, vadinama kombinatorika, kuri atsirado XVI amžiuje išpopuliarėjus azartiniams žaidimams. Pirmieji kombinatorikos uždaviniai ir buvo susiję su šiais žaidimais, pavyzdžiui, buvo tiriama, keliais būdais galima išmesti kokį nors taškų skaičių, žaidžiant dviem arba trimis kauliukais.

Kombinatorikos žinių prireikia sprendžiant įvairius olimpiadinius uždavinius. Šiame skyrelyje glaustai išdėstysime, kaip generuoti kitus junginius rekursiniais algoritmais [3].

Keletas gretinių iš penkių prekių po tris

Fig. 16 Keletas gretinių iš penkių prekių po tris

Gretiniai. Grįžkime prie pavyzdžio su parduotuve. Sakykime, turime n skirtingų prekių, kurias reikia išdėlioti lentynoje; deja, lentynoje telpa tik k prekių ir visų prekių iš karto parodyti pirkėjams nepavyks. Reikia rasti visus būdus, kuriais galima išdėlioti prekes lentynoje. Tuščių vietų likti lentynoje negali.

Kitaip sakant, reikia rasti visus gretinius be pasikartojimų iš n elementų po k. Uždavinys labai panašus į jau nagrinėtą kėlinių be pasikartojimų generavimo uždavinį, tiesiog iš n elementų renkame tik k (k \leq n).

const MAX = 20;        { didžiausia n ir k reikšmė }
var p : array [1..MAX] of integer;
    panaudotas : array [1..MAX] of boolean;

procedure generuok(m, { parenkamas elementas m-ajai pozicijai }
                   n, k : integer);
var i : integer;
begin
    { jei m > k,
      tai ši procedūra iškviesta jau sugeneravus visą gretinį }
    if m > k then
       spausdink(k) { procedūros spausdink tekstą rasite 5.1 skyrelyje }
    else
        for i := 1 to n do
            if not panaudotas[i] then begin
                panaudotas[i] := true;
                p[m] := i;
                generuok(m + 1, n, k);
                panaudotas[i] := false;
            end;
end;

Norėdami gauti visus gretinius iš 5 po 3, į procedūrą kreipiamės:

n := 5;
k := 3;
for i := 1 to n do
    panaudotas[i] := false;
generuok(1, n, k);

Suskaičiuosime, kiek gali būti skirtingų gretinių be pasikartojimų, tuo pačiu įvertinsime ir algoritmo sudėtingumą. Pirmąją prekę galime rinktis iš visų n prekių, antrąją prekę – iš (n – 1) prekės ir t. t. k-ąją prekę galime rinktis iš (n - k+1) prekių.

Gretinių be pasikartojimų iš n elementų po k skaičius žymimas A_n^k ir lygus

A_n^k = n (n – 1)(n – 2)....(n – k + 1).

Deriniai. Generuodami gretinius atsižvelgėme į prekių išdėstymą lentynose. Pamėginkime rasti visus būdus, kuriais galima išdėstyti n skirtingų prekių lentynoje, kurioje telpa tik k prekių (lentynoje neturi likti tuščių vietų) nekreipiant dėmesio į prekių išdėstymą, t. y. kai rūpi tik tai, kokios prekės yra lentynoje, tačiau nesvarbu, kokia tvarka jos ten išdėliotos. Kitaip sakant, reikia sugeneruoti visus derinius be pasikartojimųn elementų po k.

Derinius galima generuoti kaip gretinius, laikantis vienos papildomos taisyklės: prekės dėliojamos taip, kad jų numeriai sudarytų didėjančią seką, t. y. p_1 < p_2 < p_3 < \dots < p_k. Derinius generuojančiai rekursinei procedūrai prireiks vieno papildomo parametro, kuris rodytų, nuo kurio elemento galime rinkti tolesnius elementus.

Keletas derinių iš penkių prekių po tris

Fig. 17 Keletas derinių iš penkių prekių po tris (tvarka deriniuose nesvarbi)

const MAX = 20;        { didžiausia n ir k reikšmė }
var p : array [1..MAX] of integer;
    panaudotas : array [1..MAX] of boolean;
procedure generuok(nuo, { bus renkamasi tik iš elementų,
                         didesnių arba lygių „nuo“ }
                   m, { parenkamas elementas m-ajai pozicijai }
                   n, k: integer);
var i : integer;
begin
    { jei m > k, tai ši procedūra iškviesta jau sugeneravus visą derinį }
    if m > k then spausdink(k) { procedūros spausdink tekstą rasite 5.1 skyrelyje }
    else
        for i := nuo to n do
            if not panaudotas[i] then begin
                panaudotas[i] := true;
                p[m] := i;
                generuok(i + 1, m + 1, n, k);
                panaudotas[i] := false;
            end;
end;

Norėdami gauti visus skirtingus derinius iš 5 elementų po 3, į procedūrą kreipiamės:

n := 5;
k := 3;
for i := 1 to n do
    panaudotas[i] := false;
generuok(1, 1, n, k);

Beliko apskaičiuoti, kiek gali būti skirtingų derinių be pasikartojimų iš n po k. Šį skaičių pažymėkime C_n^k.

Sakykime, turime konkretų derinį. Jei paimtume visus jo perstatymus, gautume visus kėlinius be pasikartojimų iš tų k derinį sudarančių elementų. Tokių kėlinių gali būti k!

O jei kartu paimtume visus kiekvieno galimo derinio perstatymus, gautume visus gretinius be pasikartojimų iš n elementų po k. Žinome, kad jų gali būti A_n^k = n(n - 1)(n - 2)\dots(n - k + 1). Gauname:

k!C_n^k = A_n^k

arba:

C_n^k =
  \frac{A_n^k}{k!} =
  \frac{n(n-1)(n-2)\dots(n-k+1)}{k!} =
  \frac{n!}{k!(n-k)!}

Pavyzdžiui, jei turime 10 prekių, o lentynoje telpa 7 prekės, tai nepaisydami prekių išdėstymo tvarkos šias prekes galime išdėlioti lentynoje C_{10}^7 = \frac{10!}{7!(10-7)!} = \frac{8 \cdot 9 \cdot 10}{3 \cdot 2 \cdot 1} = 1080 būdų.

Poaibiai. Visus galimus n elementų aibės poaibius galime gauti generuodami iš eilės 0, 1, 2, \dots, n ilgio derinius be pasikartojimų. Galimas ir dar paprastesnis būdas: pakanka sugeneruoti visus įmanomus žodžius, kurių ilgis n iš abėcėlės \{true, false\}.

Abėcėlės {true, false} žodžių transformavimo į poaibius pavyzdys

Fig. 18 Abėcėlės {true, false} žodžių transformavimo į poaibius pavyzdys

const MAXN = 20;        { didžiausia n reikšmė }
var parinktas : array [1..MAXN] of boolean;

procedure spausdink (m: integer);
var i : integer;
begin
    write('{ ');
    for i := 1 to m do
        if parinktas[i] then
            write(i, ' ');
    writeln('}');
end;

procedure generuok(k, n : integer);
{ nagrinėjamas k-asis n elementų aibės narys }
var log : boolean;
begin
    { jei k > n, tai ši procedūra iškviesta jau sugeneravus visą poaibį }
    if k > n then
        spausdink (k)
    else
        for log := false to true do begin
            parinktas[k] := log;
            generuok(k + 1, n);
        end;
end;

Norėdami gauti visus poaibius iš 4 elementų, į procedūrą generuok kreipiamės:

n := 4;
generuok(1, n);

Suskaičiuosime, kiek skirtingų poaibių turės aibė iš n elementų, o tuo pačiu ir algoritmo sudėtingumą. Poaibių skaičius lygus visų įmanomų n ilgio žodžių iš abėcėlės \{true, false\} skaičiui. Kadangi kiekvieną tokio žodžio raidę galime parinkti dviem būdais (atitinkamas elementas arba įtraukiamas į poaibį, arba ne), tai tokių žodžių (ir galimų poaibių) skaičius lygus 2^n.

Uždavinys Pakyla [4]

Panagrinėsime vieną uždavinį, kurio sprendimui reikia taikyti kombinatorikos žinias ir perrinkti visus įmanomus variantus.

Tarp dviejų taškų A ir B norime pastatyti pakylą, kurios aukštis H metrų. Į pakylos viršų tiek iš taško A, tiek iš taško B turi vesti kylantys laiptai. Laiptų pakopos aukštis yra 1 metras. Nesunku apskaičiuoti, kad pakylą turi sudaryti (2H-1) pakopų – po (H – 1) iš kiekvienos pusės bei viršutinė. Pirmoji laiptų, kylančių iš taško A (taško B), pakopa turi prasidėti taške A (atitinkamai taške B).

Atstumas tarp taškų A ir B lygus P metrų. O kiekvienos pakopos plotis turi būti lygus sveikajam metrų skaičiui. Aukščiausioje dalyje esančios pakopos plotis turi būti lygus V metrų.

Užduotis. Reikia rasti visus galimus skirtingus būdus pakylai įrengti. Dvi pakylos laikomos skirtingomis, jei jų aukštis skiriasi bent vienoje pozicijoje tarp taškų A ir B.

Galioja ribojimai: pradiniai duomenys tokie, kad galimų variantų skaičius pakylai įrengti neviršija 20\ 000.

Pakylos pavyzdys.

Fig. 19 Pakylos pavyzdys. H=4; P=12; V=3; Ši pakyla apibūdinama seka: 0\ 2\ 3\ 4\ 7\ 8\ 10\ 12

Prieš sprendžiant uždavinį, svarbu tiksliai apibrėžti, ko iš tiesų ieškome. Kiekvieną galimą pakylą atitinka didėjanti skaičių nuo 0 iki P seka {S_i}, kurią sudaro lygiai 2H skaičių ir kuri tenkina papildomus ribojimus:

  • S_1 = 0;
  • S_{2H} = P;
  • S_{H+1} - S_H = V.

Kiekvienas šios sekos elementas rodo vietą (koordinatę x), kurioje keičiasi pakopos aukštis. Pavyzdžiui, paveiksle pavaizduotą pakylą atitinka skaičių seka < 0, 2, 3, 4, 7, 8, 10, 12 >.

Taigi pirmojo ir paskutinio nario reikšmės yra fiksuotos, o (H+1)-ojo nario reikšmė priklauso nuo H-ojo nario: S_{H+1} = S_H + V. Nesunku apriboti k-ojo nario reikšmę:

\begin{align*}
  S_{k-1} &<& S_k &\leq& P - (V - 1) - (2H - k), &
    \text{ jei }2 \leq k \leq H; \\
  S_{k-1} &<& S_k &\leq& P - (2H - k), &
    \text{ jei }H+2 \leq k \leq 2H - 1.
\end{align*}

Apatinis ribojimas išplaukia iš to, kad seka yra didėjanti, o viršutinis – kad nepritrūktų skaičių sekai užbaigti.

Gavome derinių generavimo uždavinį, tik tam tikrais ribojimais maksimalioms pozicijų reikšmėms.

Pasinaudosime jau žinomu derinių generavimo algoritmu, kurį pritaikysime šio uždavinio sprendimui. Beje, sutarsime, kad sprendinys egzistuoja.

const MAXH = 100; { maksimalus pakylos aukštis }
var s : array [1..2*MAXH] of integer;
    P, H, V : integer;

procedure generuok(k : integer);
{ generuoja sekos narį, kurio numeris k }
var i, max : integer;
begin
    if k = 2*H then
        { sugeneruoti visi nariai (paskutinis žinomas iš anksto) }
        spausdink(2*H) { Procedūra spausdink analogiška spausdinimo
                         procedūrai 5.1 skyrelyje. }
    else if k = H+1 then begin
        { (H+1)-osios pakopos viršūnės plotis fiksuotas }
        s[k] := s[k-1]+V;
        generuok(k+1);
    end
    else begin
        { nagrinėjamos visos galimos k-ojo nario reikšmės }
        if k <= H then
            max := P-(2*H-k)-(V-1)
        else
            max := P-(2*H-k);
        for i := s[k-1]+1 to max do begin
            s[k] := i;
            generuok(k+1);
        end;
    end;
end;

Į procedūrą generuok turi būti kreipiamasi tokiu būdu:

S[1] := 0;
S[2*H] := P;
generuok(2);

Perrinkimo optimizavimas

Panagrinėkime dar vieną pavyzdį. Sakykime, saugos kodą, kurį reikia surinkti įeinant į laiptinę, sudaro 3 skaitmenys. Norint jį atspėti, reikia išbandyti 10^3=1000 variantų. Jei vieną kodą galima surinkti ir pabandyti atidaryti duris per 3 sekundes, tai visus variantus pavyks išbandyti per 50 minučių. Tačiau jei saugos kodą sudarytų 4 skaitmenys, tai visiems 10^4=10\ 000 variantams išbandyti prireiktų daugiau nei 8 valandų. Matome, kad pradiniams duomenims (t. y. skaitmenų skaičiui) padidėjus 33%, galimų sprendinių skaičius padidėja 900%. Toks staigus sprendinių skaičiaus augimas vadinamas kombinatoriniu sprogimu.

Vienas didžiausių perrinkimo trūkumų yra tai, kad susiduriama su kombinatoriniu sprogimu. Generuojant kombinatorinius objektus kitaip ir negali būti: reikia rasti visus objektus, o jų yra daug, taigi ir algoritmų sudėtingumas turi būti didelis. Tačiau dažniau tenka ieškoti tam tikros kombinacijos, t. y. sprendinio, tenkinančio konkrečias sąlygas.

Todėl daugelyje tokių uždavinių stengiamasi optimizuoti paiešką. Vienas galimų optimizavimo būdų – paanalizuoti sprendinio struktūrą ir sumažinti galimų sprendinių paieškos erdvę. Taip darėme Aštuonių valdovių uždavinyje. Pradinė sprendinių erdvė buvo gana didelė: buvo sutarta, kad kiekviena valdovė gali stovėti bet kuriame lentos langelyje (po vieną valdovę langelyje), ir galimų variantų skaičius viršijo 4 \cdot 10^9. Tačiau jei perrenkant variantus, kiekviena valdovė statoma tik į tuščią eilutę – tai išnagrinėjamų variantų skaičius iš karto sumažėja iki 8! = 40\ 320.

Gali pavykti sumažinti ir skyrelio pradžioje pateikto uždavinio paieškos erdvę. Jei žinoma, kad visi skaičiai turi būti paspausti vienu metu, tai saugos kode nebus pasikartojančių skaitmenų. Be to, šitaip parenkant kodą nenustatoma skaitmenų tvarka, todėl galime dar sumažinti sprendinių erdvę: pakanka išbandyti visus derinius. Pavyzdžiui, bandant atspėti keturių skaitmenų saugos kodą, mus domina visi deriniai iš 10 po 4. Jų skaičius yra C_{10}^4 = 210 (palyginkite su 10\ 000).

Jei reikalingas tik vienas sprendinys, paiešką verta optimizuoti parenkant sprendinių nagrinėjimo tvarką taip, kad tikėtini sprendiniai būtų nagrinėjami pirmiausia, jei tik tai įmanoma padaryti.

Yra įvairiausių kitų metodų paieškai pagreitinti, dažnai priimtinų tik konkrečiam uždaviniui. Pavyzdžiui, ieškant geriausio ėjimo stalo žaidimuose, naudojama Minimax paieška su Alfa-Beta atkirtimu; šis metodas leidžia anksčiau atkirsti daug neperspektyvių paieškos medžio šakų.

[1]Keletas įrodymų buvo paneigta praėjus tik 11 metų po jų paskelbimo.
[2]Žr. skyrelį NP sudėtingumas.
[3]Yra efektyvesnių (nerekursinių) kombinatorinius objektus generuojančių algoritmų, tačiau rekursiniai algoritmai yra intuityvesni ir lengviau realizuojami.
[4]Šis uždavinys buvo pateiktas Lietuvos moksleivių informatikos olimpiadoje III etape 2004 metais.