4.3. Párhuzamos Szűrés

A párhuzamos szűrés olyan változata az előző példában is látott számítási modellnek, amely segítségével minden NP-beli probléma megoldására könnyen adhatunk hatékony és elegáns algoritmust. A fő különbség az eredeti és a párhuzamos szűrés között, hogy ebben a modellben egyszerre egymással párhuzamosan több lombikkal is végezhetünk műveleteket (ha elég nagy labor és elég laboráns áll rendelkezésre, akkor ez így is van).

Ez a szűrési modell is a „megjelöl és rombol" elven alapul, vagyis egy adott (multi)halmaz, lombik tartalmát, nem két részre bontjuk, amik felhasználhatóak lesznek a továbbiakban, hanem egyszerűen eltávolítjuk azokat az elemeket, amik nem kellenek a további számítás során.

A kiindulási halmaz el(ő)készítése után, a következő alapműveleteket végezhetjük:

A modell hatékonyságának, alkalmazhatóságának lényegét a következő példán mutatjuk be.

12. Példa. Adott az első n pozitív szám {1,2,...,n} halmaza. Állítsuk elő ezen számok összes permutációját.

A példa nehézsége a halmaz számosságában rejlik, ugyanis az n elemnek n! permutációja van, ami gyorsabban nő az n értékével, mint az n exponenciális függvénye. Tehát pusztán a megoldáshalmaz leírásához is rengeteg idő kell hagyományos eszközökkel.

A kiindulási halmaz jelen esetben a pozíciójeleket is tartalmazó gráf maximális útjainak kódját tartalmazza. Egy ilyen kódot a p0 i1 p1 i2 ... pn-1 in pn alakba írhatunk, ahol a pj elemek fixek, az ij-k pedig az {1,2,...,n} halmaz elemei (valójában a gráf megfelelő csúcsainak alsó indexei). Ennek megfelelően minden ilyen sztring, a pozíciójeleken kívül n számot tartalmaz, de lehetséges, hogy egyet többször is...

A feladat megoldása a következő algoritmussal történik:


   PÁRHUZAMOS SZŰRŐ MODELL ALGORITMUSA permutációk elkészítéséhez 
Input:  gráf maximális útjai, mint T multihalmaz 
1: for j = 1 to n -1 do 
2:    másol(T,{T1,T2,...,Tn})
3:    for each i∈{1,2,...n és k∈{j+1,...,n} in parallel do
4:       kidob(Ti,{i' pj ∣ 1≤ i'n, ii'} ∪ {ipk})
5:    end for 
6:    egyesít({T1,T2,...,Tn},T)
7: end for
8: az output halmaz T

Az algoritmus lényege a belső for ciklus, aminek törzsét párhuzamosan hajthatjuk végre. A ciklust az i ∈ ℕ minden 1 ≤ in értékére és a k ∈ ℕ minden j < kn értékére, vagyis olyan (i,k) párokra hajtjuk végre, amelyek esetén mindkét feltétel fennáll. A lényeg a 4. sorban zajlik: itt kidobjuk azokat az elemeket, amikben nem az i érték áll a pj előtt, vagyis a j-edik helyen, illetve kidobjuk azokat az elemeket, amikben az i valamely a j utáni pozícióban (is) megtalálható. Tehát a Ti-ben pontosan azok a sztringek maradnak meg, amikben a j. helyen az i szerepel, és sehol később. Mivel a külső ciklus az első pozíciótól indul (j=1), először azokat a sztrinegeket dobjuk ki, amikben az első helyen szereplő érték szerepel máshol is (a T1-ben pl. ha nem az 1 érték szerepel a j-edik, vagyis első helyen, illetve ha ez az érték szerepel máshol, a Ti-ben pedig ugyanezt a szűrést végezzük az i értékkel: kidobunk minden sztringet, amiben az j-edik, vagyis most az első helyen nem az i érték áll, illetve amiben az i érték valahol máshol előfordul). A 6. sorban egyesítjük a lombikok tartalmát, így a T-ben minden egyes {1,...,n}-beli értékre megvannak azok a sztringek, amik első pozíciójában az adott érték szerepel, és az sehol máshol nem szerepel a sztringben. A ciklus j-edik iterációja után az első előforduló j érték a megmaradt sztringekben bizonyosan nem fordul elő kétszer. A számítás végére ekkor pontosan azok a sztringek maradnak csak meg, amikben minden egyes érték pontosan egyszer szerepel, tehát egy permutációja az {1,2,...,n} halmaznak.

Az algoritmus 4. pontját, a következő alakokba is írhatjuk:


4     kidob(Ti,{1pj,...,(i-1)pj,(i+1)pj,...,npj,ipk}) 
4     kidob(Ti,{ipj,ipk})

Az eredeti alaknál a most leírt első alak kifejezőbbnek tűnhet, mivel a kiszűrendő részsztringek így felsorolva talán könnyebben olvashatók. A legutolsóként felírt alak a legtömörebb (a párhuzamos modell egyik bevezetője M. Amos használja így), de a fentiek értelmében így már érhető is: Azokat a sztringeket kell kiszűrnünk, ahol nem az i áll a pj helyjelölő előtt, illetve azokat amikben az i-t a pk jelölő követi.

Az ilyen modellben megoldott feladatokban általában ez az a művelet, ami lényegi részét jelenti a párhuzamosan is megvalósítható algoritmusnak.

(A minden út elején ott levő p0 valójában nem vesz részt a kódolásban, hiszen az n pozíciót a p1, ..., pn kódok jelzik. Ennek megfelelően igazából nincs is rá szükség. Akár a gráf kis módosításával fizikailag is megszabadulhatunk tőle. A továbbiakban az eredményt e nélkül a kódrész nélkül tekintjük.) Az előállított halmaz tehát a (módosított) gráf maximális útjai közül pont azok kódját tartalmazza, amelyekben nincs két különböző pozíció, j és j' (1 ≤ j, j'n), hogy az ottani értékek megegyeznek (ij = ij'). Ennek megfelelően ha csak a kódrészek értékeit tekintjük, akkor az előállított sztringek éppen az {1,2...,n} halmaz összes lehetséges permutációit kódolják.

Látható, hogy a párhuzamosítható rész az input méretével lineáris számú műveletet enged meg egyidejűleg elvégezni (vagyis ennyi az egyszerre párhuzamosan végzett műveletek száma).

A bemutatott példánkban létrehozott permutációkat kódoló sztringeket tartalmazó multihalmazt a -t kódoló kiindulási multihalmazból n-nel lineáris számú párhuzamos lépésben. (Attól függően hogy az algoritmus párhuzamosan végrehajtható utasításait konstans idővel, vagy a paramétereiknek megfelelő időben végrehajthatónak tekintjük szokás a gyenge és az erős modell megkülönböztetése. Az erős modellben a permutációk a n négyzetével arányos időben állíthatóak elő, ami jobban tükrözi a valóságot.) Ennek megfelelően, az így létrejött halmaz is könnyen előállítható és használható más feladatok megoldásához kiindulási multihalmazként.

19. Feladat. Futtassuk/szimuláljuk a permutációk előállítására szolgáló algoritmust n=3 esetén.

A párhuzamos szűrés algoritmusával sok NP-teljes probléma, többek közt, a részgráf-izomorfia, illetve a maximális klikk megtalálása is hatékonyan elvégezhető.