Kereső algoritmusok a diszkrét optimalizálás problémájához

•SzPE

•2008. tavasz

Kereső algoritmusok a diszkrét optimalizálás problémájához A. Grama, A. Gupta, G. Karypis és V. Kumar: „Introduction to Parallel Computing”, Addison Wesley, 2003. könyv anyaga alapján A kereső eljárások pontosabb tárgyalása Futó Iván (szerk.): Mesterséges Intelligencia, Aula, 1999. fejezetéből származnak

Vázlat

A diszkrét optimalizálási probléma Soros megoldás Párhuzamos megoldási lehetőségek és problémák

Kereső algoritmusok diszkrét optimalizáláshoz

•Kereső algoritmusok diszkrét optimalizáláshoz

2

•1

•SzPE

•2008. tavasz

Diszkrét optimalizálás

A diszkrét optimalizálási problémák komoly számítási igényűek. Jelentős elmélettel és gyakorlati fontossággal rendelkeznek (ütemezési feladatok, pályatervezés, digitális áramkörökhöz tesztpéldák generálása, logisztikai feladatok, stb.).

A kereső algoritmusok a feltételeknek megfelelő megoldások terét szisztematikusan vizsgálják.


3

Definíció

A diszkrét optimalizációs probléma (DOP) a következő módon fejezhető ki: (S, f).

S bizonyos feltételeknek eleget tévő megoldások véges, vagy megszámlálhatóan végtelen halmaza, f költségfüggvény S minden eleméhez valós R értéket rendel.

A DOP megoldása olyan xopt megoldás keresése, hogy f(xopt) ≤ f(x) minden x ∈ S esetén.

Gyakran NP-teljes probléma. Kereső algoritmusok diszkrét optimalizáláshoz


4

•2

•SzPE

•2008. tavasz

Diszkrét optimalizáció: példa

Egyértékű lineáris programozási feladat (0/1 integer-linearprogramming problem): adott A m×n mátrix, b m×1 vektor és c n×1 vektor.

A cél egy olyan n×1 vektor meghatározása, amelynek elemei csak 0 és 1 értékekből állhatnak, a vektor teljesíti a következő feltételt: és az f függvénynek minimuma kell legyen:

*: Duális megfogalmazás Kereső algoritmusok diszkrét optimalizáláshoz

5

DOP és a gráfkeresés

Az S lehetséges elemeinek száma nagyon nagy. A DOP gyakran úgy is megfogalmazható, hogy egy gráfban minimum költségű utat keressünk egy kezdőponttól egy vagy több lehetséges cél csomópontig. Az S minden x elemét tekinthetjük egy útnak a kezdőponttól valamely célig.

A gráf csomópontjai állapotok Az állapotok vagy végpontok, vagy nem végpontok Bizonyos állapotok lehetséges megoldáshoz tartoznak, mások nem Az élekhez költségek tartoznak, amelyek az egyik állapotból a másikba történő átmenet ráfordításai.

A gráfot állapottérnek Kereső nevezzük. algoritmusok diszkrét optimalizáláshoz


6

•3

•SzPE

•2008. tavasz

Állapottér gráf: példa

Egyértékű lineáris programozási feladat

Az állapotok az x vektor egyes koordinátáihoz rendelt értékek => fa


7

2 8 3 1 6 4 7 5

8-as kirakó

2 8 3 1 6 4 7 5

2 8 3 6 4 1 7 5

Egy kezdeti állapotból találjuk meg azt a legrövidebb lépéssorozatot, amely a célkonfigurációba vezet. Állapottér: gráf

8 3 2 6 4 1 7 5

8 3 2 6 4 1 7 5

2 3 1 8 4 7 6 5

2 8 3 1 4 7 6 5

2 8 3 6 4 1 7 5

2 3 6 8 4 1 7 5

2 8 3 1 6 4 7 5

2 8 3 1 4 7 6 5

2 8 3 6 4 1 7 5

2 8 3 6 7 4 1 5

8 3 2 1 4 7 6 5

2 8 3 7 1 4 6 5

2 3 1 8 4 7 6 5

2 3 1 8 4 7 6 5

2 8 1 4 3 7 6 5

2 8 3 1 4 5 7 6

8 3 2 1 4 7 6 5

2 8 3 7 1 4 6 5

1 2 3 8 4 7 6 5

2 3 4 1 8 7 6 5

2 8 1 4 3 7 6 5

2 8 3 1 4 5 7 6

8 3 2 1 4 7 6 5

8 1 3 2 4 7 6 5

8 1 3 2 4 7 6 5

8 1 3 2 4 7 6 5

1 3 8 2 4 7 6 5

2 8 3 1 6 7 5 4

2 8 3 1 4 7 6 5

8 1 3 7 2 4 6 5

1 2 3 8 4 7 6 5

2 8 3 1 4 5 7 6

1 2 3 7 8 4 6 5

2 8 3 1 5 7 4 6

8 1 3 2 6 4 7 5

célállapot

2 8 1 6 3 7 5 4

2 8 3 1 6 7 5 4

2 8 3 1 6 7 5 4

2 3 1 6 8 7 5 4

2 8 3 1 5 7 4 6

2 3 1 8 5 7 4 6

2 3 1 6 3 7 5 4

2 8 3 1 5 6 7 4

2 8 3 1 5 6 7 4

2 8 3 1 5 7 4 6

2 8 3 1 5 6 7 4

2 8 3 1 5 7 4 6

duplikált állapot

1 3 8 2 4 7 6 5

1 3 8 2 4 7 6 5

1 2 3 8 4 7 6 5



8

•4

•SzPE

•2008. tavasz

Kereső algoritmusok tere

A keresési tér gráf vagy fa? A gráf fává történő kiterítése gyakran nagyméretű feladathoz vezet. 1

2

4

5

3

1

2

4

3

6

5

7 8

6

7 9

8

7 9

8

9

(a)

1

1 2

3

2

5

6 7

8

3

4

4

9 10


4

5

6

5

7

7

7

6 7

8

9

8

9

8

9

8

9

10

10

10

10

10

10

10

10

9

(b)

Kereső stratégiák I.

Nem módosítható keresés

Nincs visszalépés. Pl. hegymászó algoritmus (gradiens keresés).

Visszalépéses keresés

Törli a zsákutcát. Ha körre futunk, akkor visszalépés. Mélységi korlátot használhatunk (heurisztika). Azonos szinten célszerű sorrendi heurisztikát használni. Kis memória igényű. Nem garantálja az optimális megoldást (csak növekvő mélységi korláttal és iterálva).



10

•5

•SzPE

•2008. tavasz

Négy-királynő probléma

Visszalépéses keresés + azonos sorban haladva, mindig balról jobbra helyezzük el a királynőket.


11

Kereső stratégiák II. Nem informált gráfkeresés

Nem informált gráfkeresések – a gráf kiértékelő függvényben (f(n) = g(n) + h(n)) beépülő heurisztikát nem használunk. Csúcsok NYÍLT és ZÁRT listája. Mélységi keresés

Egységnyi élköltséget tekintünk. f(n):= -g(n) minden n NYÍLT csúcsra. Mélységi korlát használható, iterációs változatban is. Fa állapottérnél előnyös.

Szélességi keresés

Egységnyi élköltséget tekintünk. f(n):= g(n) minden n NYÍLT csúcsra. Kereső algoritmusok diszkrét optimalizáláshoz


12

•6

•SzPE

•2008. tavasz

Iteratív mélységi keresés

Gyakran a megoldás a gyökérhez közeli, de másik ágon van.

Az egyszerű mélységi keresés nagy részt dolgozna fel mielőtt erre az ágra jut.

Iteratív módon növeljük a mélységi határt, ameddig keresünk.

Ha nem találunk megoldást, akkor a határt növeljük és ismételjük a folyamatot. Kereső algoritmusok diszkrét optimalizáláshoz

13

Mélységi keresés: tárolási követelmény és adatstruktúra

A mélységi keresés minden lépésénél a még ki nem próbált alternatívákat el kell tárolni.

Ha m egy állapot tárolásához szükséges adatterület, és d a maximális mélység, akkor a mélységi kereséshez szükséges teljes tér O(md) nagyságrendű.

Ha a keresendő állapottér fa, akkor a mélységi keresést veremmel hatékonyan lehet reprezentálni.

A verem memória szükséglete egyenesen arányos a fa mélységével. Kereső algoritmusok diszkrét optimalizáláshoz


14

•7

•SzPE

•2008. tavasz

Mélységi keresés: tárolási követelmény és adatstruktúra

(a) Mélységi keresés fa esetén; pontozottan jelennek meg a már felkeresett csúcsok; (b) A verem a még ki nem próbált alternatívákat tárolja csak; (c) a verem a ki nem próbált alternatívákat és szüleiket Kereső algoritmusok diszkrét (szürkített) tárolja. optimalizáláshoz

15

Mélységi keresés korláttal: példa 1. 2 8 3 1 6 4 7 5

Korlát: 5

2. 2 8 3 1 6 4 7 5

3. 2 8 3 6 4 1 7 5

4.

5. 8 3 2 6 4 1 7 5

9.

6. 7. 8 6 3 8 3 2 6 4 2 4 1 7 5 1 7 5

10.

2 3 6 8 4 1 7 5

2 3 6 8 4 1 7 5


8 3 2 6 4 1 7 5

11. 2 3 6 8 4 1 7 5

20. 2 8 3 1 4 7 6 5

21.

8. 2 8 3 6 4 1 7 5

8 3 2 1 4 7 6 5

25. 2 8 3 7 1 4 6 5

8 3 2 1 4 7 6 5

26. 2 8 3 7 1 4 6 5

13. 2 8 3 6 4 1 7 5

16. 2 8 3 6 7 4 1 5

22.

14.

17. 18. 2 8 3 2 8 3 6 7 4 6 7 4 1 5 1 5

23. 8 3 2 1 4 7 6 5

15. 2 8 3 2 8 6 4 3 6 4 5 1 7 5 1 7

24. 8 1 3 2 4 7 6 5


27. 28. 2 8 3 2 8 3 7 4 7 1 4 6 1 5 6 5

19. 2 8 3 1 4 7 6 5

2 8 3 1 6 4 7 5

29. 2 3 1 8 4 7 6 5

2 8 3 1 4 7 6 5

30.

2 3 1 8 4 7 6 5

2 3 1 8 4 7 6 5

31. 1 2 3 8 4 7 6 5

32. 1 2 3 8 4 7 6 5

1 2 3 7 8 4 6 5

16

•8

•SzPE

•2008. tavasz

Szélességi keresés: példa 2. 2 8 3 1 6 4 7 5

5.

2 8 3 6 4 1 7 5

10.

11. 2 8 3 6 4 1 7 5

8 3 2 6 4 1 7 5

20. 8 3 2 6 4 1 7 5

35. 8 3 2 6 4 1 7 5

6.

21. 22. 2 3 6 8 4 1 7 5

38. 37. 36. 2 3 2 3 8 6 3 2 4 6 8 4 6 8 4 1 7 5 1 7 5 1 7 5

23. 2 8 3 6 4 1 7 5

2 8 3 1 4 7 6 5

2 8 3 1 6 4 7 5

3.

2 8 3 1 4 7 6 5

7.

2 3 1 8 4 7 6 5

13. 2 8 3 7 1 4 6 5

14.

8 3 2 1 4 7 6 5

25. 8 3 2 1 4 7 6 5

26. 2 8 3 7 1 4 6 5

27. 28. 2 3 4 1 2 3 1 8 8 4 7 6 5 7 6 5

12.

24. 2 8 3 6 7 4 1 5

1.

2 3 1 8 4 7 6 5

4.

8.

9.

2 8 3 1 4 7 6 5

15. 16. 2 8 2 3 1 4 3 1 8 4 7 6 5 7 6 5

17. 2 8 3 1 4 5 7 6

2 8 3 1 6 4 7 5

2 8 3 1 6 7 5 4

18. 2 8 3 1 6 7 5 4

29. 30. 31. 32. 3 2 8 2 8 3 2 8 3 2 1 6 1 6 8 1 4 3 1 4 5 6 7 5 4 7 5 4 7 6 5 7

19. 2 8 1 6 3 7 5 4

33. 2 8 3 1 5 6 7 4

34. 2 3 1 6 3 7 5 4

39. 40. 41. 43. 47. 42. 44. 45. 46. 2 8 3 2 8 3 2 8 3 8 3 2 8 1 2 3 2 8 3 2 8 3 8 1 3 1 4 8 4 2 1 4 algoritmusok 6 4 3 6 4 5 6 7 4 6 7 Kereső 2 4 4 7 4 7diszkrét 1 5 7 6 5 7 6 5 1 7 5 1 7 7 6 5 6 1 5 6 5 1 5

optimalizáláshoz

17

Heurisztikus gráfkereső stratégiák

Az f(x) kiértékelő függvénybe valamilyen heurisztikát építünk be (f(x) = g(x) + h(x)). Gyakran például becsülhető a cél elérésének költsége az aktuális csúcsból. A becslést heurisztikus becslésnek nevezik. Ha a becslés garantáltan alábecsül, akkor megengedő heurisztikáról beszélünk. Elképzelés: ha heurisztikát használunk, akkor a „rossz”, vagy „nem sokat ígérő” utakra nem költünk.



18

•9

•SzPE

•2008. tavasz

Diszkrét optimizálás példához heurisztika

A 8-as kirakóhoz (megengedő) heurisztika W(n) (n NYÍLT), ahol W a rossz helyek száma

A 8-as kirakóhoz megengedő heurisztika A rács minden pontja a koordinátáival azonosítható. Az (i, j) és a (k, l) pozíciók távolsága: |i - k| + |j - l|. Ez a Manhattan távolság. A kezdeti és cél pozíciók közötti Manhattan távolságok összege (P-vel fogjuk jelölni) megengedő heurisztika. Kereső algoritmusok diszkrét optimalizáláshoz

19

Kereső stratégiák III. Heurisztikus gráfkereső stratégiák

Előretekintő keresés

f(n) = h(n) minden n NYÍLT csúcsra.

A*

Kiértékelő fgv. f(n) = g(n) + h(n) minden n NYÍLT csúcsra, ahol h(n) megengedő heurisztika. Garantálja az optimális megoldást. Nagy a memória igény.

Mind fák, mind gráfok estében hatékony.

Meglátogatott csúcsokkal (állapotokkal) arányos.



20

•10

•SzPE

•2008. tavasz

Előretekintő keresés f = W

1. 2 8 3 4 1 6 4 7 5

2. 2 8 3 3 1 4 7 6 5

2 8 3 5 1 6 4 7 5

W hibásak száma, hátralévő mozgások alsó becslését adja.

3. 2 8 3 3 1 4 7 6 5

4.

8 3 2 1 4 7 6 5

3

5. 8 3 2 1 4 7 6 5

3

2 3 3 1 8 4 7 6 5

2 8 3 4 1 4 7 6 5

2 8 3 4 7 1 4 6 5

6. 8 1 3 2 4 7 6 5

8 3 4 2 1 4 7 6 5

2 8 3 5 1 6 4 7 5

3

7. 8 1 3 3 8 1 3 4 8 1 3 4 2 4 2 4 2 6 4 7 6 5 7 5 7 6 5

8.

1 3 8 2 4 7 6 5

2

9. 1 3 8 2 4 7 6 5

1

8 1 3 7 2 4 6 5

2 10. 1 2 3 1 3 Kereső algoritmusok 8 2 4 diszkrét 8 4 7 6 5 7 6 5 optimalizáláshoz

4

0

21

A* példa P heurisztikával 2 8 3 1 6 4 7 5

5

2 8 3 1 4 7 6 5

3

4.

1. 2 8 3 1 6 4 7 5

4

2. 2 8 3 1 4 7 6 5

3

3. 2 3 1 8 4 7 6 5

3

2 2 3

2 3 1 8 4 7 6 5

0

4

4

1

1 2 3 8 4 6 5

8 4 7 Kereső algoritmusok 7 6diszkrét 5 optimalizáláshoz


2 8 3 1 4 7 6 5

5

1 8 4 7 6 5

5. 1 2 3 8 4 7 6 5

6. 1 2 3

2 8 3 1 6 4 7 5

2

22

•11

•SzPE

•2008. tavasz

Párhuzamos diszkrét optimalizáció: motiváció

DOP általában NP-teljes problémák. Segít-e a párhuzamosítás? Sok problémánál az átlagos eset polinomiális idejű. Sokszor viszonylag kis állapotterünk van, de valós idejű megoldásra van szükségünk. Többletráfordítás

A soros és párhuzamos keresés közötti munkamennyiség gyakran különböző. Ha W a soros munka és WP a párhuzamos, a többletráfordítás s = WP/W. A sebességnövekedés határa p×(W/WP). Kereső algoritmusok diszkrét optimalizáláshoz

23

Párhuzamos mélységi keresés

A keresési teret miként osszuk fel processzorok között? A különböző ágakat lehet párhuzamosan keresni. De az ágak nagyon eltérő méretűek lehetnek. Nehéz becsülni az ágak méretét a gyökerükből. Dinamikus terhelés kiegyenlítés szükséges. A

B C

D

E

F

A statikus dekompozíció strukturálatlan fakeresést és nem kiegyensúlyozott terheléshez vezet. Kereső algoritmusok diszkrét optimalizáláshoz


24

•12

•SzPE

•2008. tavasz

Párhuzamos mélységi keresés: dinamikus terhelés kiegyenlítés

Amikor egy processzor befejezi munkáját, akkor egy másiktól kér.

Osztott memóriás modellnél ez lockolással és a munka szétvágásával történik (lásd később).

Ha valamely processzor megoldáshoz és, akkor a többi terminál.

Az eddig fel nem dolgozott részeket saját veremben tárolhatja minden processzor.

Kezdetben az egész teret egy processzorhoz rendeljük. Kereső algoritmusok diszkrét optimalizáláshoz

25

Párhuzamos mélységi keresés: dinamikus terhelés kiegyensúlyozás



26

•13

•SzPE

•2008. tavasz

Párhuzamos mélységi keresés: munkafelosztás

Mélységi keresés: a két részfa a verem reprezentációval. Kereső algoritmusok diszkrét optimalizáláshoz

27

Terhelés kiegyenlítés A munka kiosztásának sémája: Aszinkron (lokális) körbeforgó: minden processzor egy számlálót tart karban ((target +1) mod p ) és az igényét a felé közvetíti.

Globális körbeforgó: A rendszer tart karban egy számlálót és az igények körbeforgó módon kerülnek kezelésre.

Nagyszámú munkaigényt generál.

Legkevesebb munkaigényt generálja.

Véletlen ciklikus: Véletlenszerűen kerül kiválasztásra egy processzor.

Megfelelő kompromisszum.



28

•14

•SzPE

•2008. tavasz

Sebesség anomáliák párhuzamos keresésnél

A párhuzamos mélységi keresés kevesebb csomópontot jár be, mint a soros. Kereső algoritmusok diszkrét optimalizáláshoz

29

Sebesség anomáliák párhuzamos keresésnél

A párhuzamos mélységi keresés több csomópontot jár be, mint a soros. Kereső algoritmusok diszkrét optimalizáláshoz


30

•15

Kereső algoritmusok a diszkrét optimalizálás problémájához

Recommend Documents