headerphoto

Problem n-królowych i wielowatkowosc

Strategia zrównoleglania

Głównym kłopotem w rozwiązaniu problemu n-królowych jest złożoność struktury danych, z jaką musi się zmierzyć algorytm z powrotami. Drzewo przestrzeni stanów rozrasta się bardzo szybko, a równoczesne przetwarzanie wielu jego gałęzi (szczególnie przy dużych szachownicach) jest zadaniem niezmiernie czasochłonnym. Analizując tę sytuację dotarto do wniosku, że istnieje dosyć interesujący sposób rozłożenia pracy związanej z przetwarzaniem drzewa przestrzeni stanów. Pomysł polega na podzieleniu drzewa na niezależne obszary, których przetwarzaniem zajmowałaby się grupa wątków. Liczba obszarów jest równa liczbie kolumn w analizowanej szachownicy. Jeżeli obszarów jest więcej niż dostępnych wątków, wtedy jeden wątek przetwarza kolejno kilka obszarów. Dane przetwarzane w ramach każdego z nich są danymi prywatnymi, jedynie ilość rozwiązań odnotowywana jest w zmiennej współdzielonej przez wszystkie wątki. Poniższy rysunek przedstawia sposób, w jaki dokonano zrównoleglania procesu poszukiwania rozwiązań dla szachownicy 4x4 za pomocą 4 wątków.



Rys. 1. Podział drzewa przestrzeni stanów na wątki.

Zatem wszystkie możliwe kombinacje ustawień królowych rozpoczynające się od królowej w wierszu 1 i kolumnie 1, będą przeliczane przez wątek 1. Z kolei wszystkie rozwiązania wyznaczone przez wątek 2 będą tyczyły się kombinacji ustawień królowych, rozpoczynających się od królowej w wierszu 1 i kolumnie 2 (królowa zielona) itd. Na rys. 2 pokazano, jak może wyglądać przykładowe rozdzielenie pracy między dwoma pierwszymi wątkami w czasie przetwarzania szachownicy 4x4.



Rys. 2. Gałęzie drzewa przestrzeni stanów podzielone na wątki.