10.5 Πρόβλημα των Ν-Βασιλισσών

Επόμενο:10.6 Περίληψη Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: 10.4 Εξάλειψη της Συμφόρησης

10.5 Πρόβλημα των Ν-Βασιλισσών

Για δείξουμε με πόση ευκολία η υλοποίηση της Δεξαμενής Εργασίας που δίνεται στο κεφάλαιο αυτό μπορεί να εφαρμοστεί σε ένα νέο πρόγραμμα Αντιγράφων Εργαζομένων θεωρούμε ένα ακόμη παράδειγμα: το πρόβλημα των Ν Βασιλισσών. Το πρόβλημα αυτό εξαιτίας της απλότητάς του και της εντελώς συνδυαστικής του φύσης είναι ιδιαίτερα δημοφιλές ως παράδειγμα της επιστήμης των υπολογιστών στον παράλληλο προγραμματισμό. Το πρόβλημα αναφέρεται στην εύρεση μιας θέσης για n βασίλισσες πάνω σε μια σκακιέρα nxn, έτσι ώστε καμία από τις βασίλισσες να μην επιτίθεται σε καμία άλλη. Ο καλύτερος τρόπος για να λύσουμε ένα τέτοιου είδους πρόβλημα είναι απλά να κάνουμε μια συνδυαστική αναζήτηση των πιθανών θέσεων των βασιλισσών και να απορρίψουμε αυτές στις οποίες οι βασίλισσες επιτίθενται η μια στην άλλη. Εξαιτίας του μεγάλου αριθμού των συνδυασμών ακόμα και για μια μικρή τιμή του n το πρόβλημα μπορεί να διατηρήσει έναν μεγάλο αριθμό επεξεργαστών απασχολημένο και να έχουμε ως αποτέλεσμα μια καλή επιτάχυνση.

Δύο βασίλισσες πάνω σε μια σκακιέρα επιτίθενται η μία στην άλλη αν βρίσκονται στην ίδια γραμμή, στήλη ή στην ίδια διαγώνιο. Το σχήμα 10.10 δείχνει μια βασίλισσα σε μια σκακιέρα 8x8. Το “Q” δηλώνει τη θέση της βασίλισσας και το “x” δείχνει όλα τα τετράγωνα στα οποία επιτίθεται η βασίλισσα. Σημειώστε ότι αυτό περιλαμβάνει όλα τα τετράγωνα στην ίδια γραμμή και όλα τα τετράγωνα στην ίδια στήλη. Περιλαμβάνει επίσης όλα τα διαγώνια τετράγωνα, τα τετράγωνα δηλαδή εκείνα που βρίσκονται και στις τέσσερις διαγώνιους. Το σχήμα 10.11 δείχνει μια λύση του προβλήματος για n=7.

Για να λύσει κάποιος αυτό το πρόβλημα με το χέρι μπορεί να πάρει μια σκακιέρα nxn και ένα σύνολο n βασιλισσών και να αρχίσει να τοποθετεί τις βασίλισσες μια κάθε φορά πάνω στη σκακιέρα. Κάποιος θα μπορούσε επίσης να προσθέτει μια νέα βασίλισσα στη σκακιέρα με τέτοιο τρόπο ώστε να μην επιτίθεται σε αυτές που ήδη υπάρχουν εκεί. Αν φτάσουμε σε μια κατάσταση στην οποία μπορούμε πλέον να τοποθετήσουμε μια βασίλισσα πάνω στην σκακιέρα που να μην επιτίθεται στις άλλες τότε μπορούμε να συνεχίσουμε οπισθοχωρώντας και αφαιρώντας μια ή περισσότερες βασίλισσες. Μπορούμε κατόπιν συνεχίζοντας από εκείνο το σημείο να επιχειρήσουμε εναλλακτικές θέσεις που δεν είχαμε επισκεφτεί. Αυτό το είδος της συνδυαστικής αναζήτησης υπολογίζεται εύκολα με τέτοιο τρόπο ώστε όλες οι εναλλακτικές λύσεις διερευνώνται κατά έναν συστηματικό τρόπο. Σε έναν παράλληλο υπολογιστή ο χώρος αναζήτησης μπορεί να μοιραστεί στους διαθέσιμους υπολογιστές.

ΣΧΗΜΑ 10.10 Περιοχή επίθεσης της βασίλισσας

ΣΧΗΜΑ 10.11 Λύση για 7 βασίλισσες

Εφόσον μια βασίλισσα πάντα επιτίθεται σε όλα τα τετράγωνα που βρίσκονται στη ίδια γραμμή, είναι εμφανές ότι δεν μπορούν να υπάρξουν δυο βασίλισσες στην ίδια γραμμή. Επίσης εφόσον ο αριθμός των βασιλισσών είναι n και ο αριθμός των γραμμών της σκακιέρας είναι πάλι n, κάθε λύση πρέπει να έχει ακριβώς μια βασίλισσα σε κάθε γραμμή της σκακιέρας. Συνεπώς, μια συστηματική διαδικασία λύσης θα άρχιζε με την τοποθέτηση της πρώτης βασίλισσας στην πρώτη γραμμή, λαμβάνοντας έτσι υπόψη όλες τις n πιθανότητες. Για κάθε μια από αυτές τις τοποθετήσεις της πρώτης βασίλισσας τοποθετούμε την δεύτερη βασίλισσα στην δεύτερη σειρά, λαμβάνοντας υπόψη όλες τις θέσεις στις οποίες δεν δέχεται επίθεση από την βασίλισσα 1. Το αποτέλεσμα θα είναι ένα σύνολο δυάδων (Q₁,Q₂) όπου το Q₁ δίνει τον αριθμό στήλης της βασίλισσας στη γραμμή 1 και το Q₂ δίνει τον αριθμό στήλης της βασίλισσας που βρίσκεται στην γραμμή 2. Στην συνέχεια κάθε μια από αυτές τις δυάδες μπορεί να επεκταθεί αν θεωρήσουμε κάθε έγκυρη θέση της τρίτης βασίλισσας στην τρίτη γραμμή. Το αποτέλεσμα θα είναι ένα σύνολο της μορφής (Q₁, Q₂, Q₃). Αυτή η διαδικασία αναζήτησης μπορεί να συνεχίσει μέχρι το n, καταλήγοντας σε ένα σύνολο νιάδων της μορφής (Q₁, Q₂, …, Q_n). Καθένα από αυτά τα σύνολα νιάδων είναι μια λύση στο πρόβλημα των Ν Βασιλισσών.

Σε ένα πρόγραμμα της Multi-Pascal για το πρόβλημα των Ν Βασιλισσών κάθε μια από τις νιάδες μπορεί να αναπαρασταθεί με την ακόλουθη δομή δεδομένων:

TYPE worktype=RECORD

            len: INTEGER; (*Ο τρέχων αριθμός των βασιλισσών*)

            queens: ARRAY [1..n] OF INTEGER; (*Θέσεις πάνω στην σκακιέρα*)

END;

Σε ένα πρόγραμμα Αντιγράφων Εργαζομένων η Δεξαμενή Εργασίας μπορεί να περιέχει όλες τις νιάδες που έχουν δημιουργηθεί μέχρι εκείνη τη στιγμή. Όταν ένας εργαζόμενος αφαιρέσει ένα αντικείμενο από τη Δεξαμενή Εργασίας, προσθέτει μια επιπλέον βασίλισσα στη νιάδα στην επόμενη κενή γραμμή. Λαμβάνουμε υπόψη κάθε πιθανή θέση στη γραμμή κοιτώντας όμως για αυτές που δεν δέχονται επίθεση από τις βασίλισσες που ήδη βρίσκονται πάνω στην σκακιέρα. Για κάθε μία τέτοια έγκυρη θέση η νέα βασίλισσα τοποθετείται στην σκακιέρα και το αντίστοιχο αντικείμενο εργασίας γράφεται στην Δεξαμενή Εργασίας. Καθώς προχωράει ο χρόνος οι νιάδες στην Δεξαμενή Εργασίας σταδιακά αυξάνονται σε μήκος μέχρι να φτάσουν το μήκος n. Όλες οι νιάδες που έχουν μείνει αποτελούν την λύση στο αρχικό πρόβλημα των Ν Βασιλισσών.

Παρακάτω δίνουμε μια περιγραφή υψηλού επιπέδου του Εργαζόμενου:

Worker process;

 

    Getwork(myboard); (*Παίρνω μια νιάδα από την Δεξαμενή Εργασίας*)

    While myboard < > Doneflag Do

    Begin

        If myboard.len= n then “A Solution is Found”

        Else Begin

        newrow:= len+1;

        For col:= 1 to n Do 

        Begin

            Is position (newrow,col) attacked by any of the previous Queens on “myboard”? 

            If answer is “no” then 

            Begin

                create “newboard” by adding Queen in position (newrow,col);

            End;

        End;

        Getwork(myboard);

End;

Το πλήρες πρόγραμμα της Multi-Pascal παρουσιάζεται στο σχήμα 10.12. Ο κώδικας της διαδικασίας Worker ακολουθεί στενά την παραπάνω υψηλού επιπέδου περιγραφή. Το σήμα τερματισμού για τους Εργαζόμενους είναι το “-1” στο myboard.len και έτσι κάθε εργαζόμενος συνεχίζει το βρόχο μέχρι να ανιχνεύσει αυτό το σήμα. Όλες οι λύσεις του προβλήματος των Ν Βασιλισσών συλλέγονται στο διαμοιραζόμενο κανάλι solutions. Το μόνο δύσκολο σημείο του κώδικα είναι η μέθοδος που χρησιμοποιείται για να ελέγξουμε αν οι θέσεις μιας νέας βασίλισσας δέχονται επίθεση από κάποια από τις ήδη υπάρχουσες. Αυτό γίνεται για κάθε μια από τις υπάρχουσες βασίλισσες υπολογίζοντας την απόστασή της σε γραμμές (rowdist) και στήλες (coldist) από την θέση ελέγχου.

Η υλοποίηση της Δεξαμενής Εργασίας που αναπτύχθηκε στην παράγραφο του Συντομότερου Μονοπατιού μπορεί να εφαρμοστεί και εδώ. Οι διαδικασίες Getwork και Putwork που χρησιμοποιήσαμε στο πρόβλημα των Ν Βασιλισσών είναι ακριβώς ίδιες με αυτές του σχήματος 10.7. Θυμηθείτε ότι σε αυτή την υλοποίηση η Δεξαμενή Εργασίας περιέχει έναν μικρό αριθμό ξεχωριστών καναλιών, με ένα σύνολο εργαζομένων να έχει ανατεθεί σε κάθε κανάλι. Η υλοποίηση αυτή αποφεύγει την συμφόρηση καναλιών στη Δεξαμενή Εργασίας. Η εξισορρόπηση του φορτίου επιτυγχάνεται έχοντας κατανείμει εκ περιτροπής τα Putwork αντικείμενα εργασίας στα κανάλια. Όλες αυτές οι εσωτερικές λεπτομέρειες υλοποίησης καθώς επίσης και η ανίχνευση τερματισμού είναι εντελώς κρυμμένες στις διαδικασίες Putwork και Getwork του σχήματος 10.7. Αυτό το νέο πρόγραμμα των Ν Βασιλισσών γράφτηκε θεωρώντας την Δεξαμενή Εργασίας ως μια αφηρημένη δομή δεδομένων, όπως παρουσιάζεται στο σχήμα 10.1. Φυσικά οι εργαζόμενοι πρέπει να είναι σχεδιασμένοι με έναν ειδικό τρόπο για να επιλύσουν το πρόβλημα των Ν Βασιλισσών, αλλά δεν χρειάζονται αλλαγές στην υλοποίηση της Δεξαμενής Εργασίας.

PROGRAM Nqueens;

CONST n= 8; (*Αριθμός των Βασιλισσών*)

    num_worker_groups= 5;

    worker_group_size= 6;

    numworkers= num_worker_groups*worker_group_size;

TYPE board= ARRAY [1..n] OF INTEGER;

    worktype= RECORD

            len: INTEGER; (*Αριθμός των τρεχουσών βασιλισσών*)

            queens: board; (*θέσεις των βασιλισσών*)

            END;

VAR workpool: ARRAY [1..num_worker_groups] OF CHANNEL OF worktype;

    i: INTEGER; startitem: worktype;

    solutions: CHANNEL OF board; (*Συλλέγει τις τελικές λύσεις*)

    … (*Δηλώσεις αθροιστών της Δεξαμενής Εργασίας όπως και στο σχήμα 10.7*)

 

PROCEDURE Getwork(me: INTEGER; VAR item: worktype);

 

… (*Ίδια όπως και στο σχήμα 10.7*)

 

 

PROCEDURE Putwork(me: INTEGER; item: worktype);

 

… (*Ίδια όπως και στο σχήμα 10.7*)

 

 

PROCEDURE Worker(me: INTEGER);

VAR myboard: worktype; row,col,coldist,rowdist: INTEGER;

    samecol,samediag,ok: BOOLEAN;

BEGIN

    Getwork(me,myboard);

    WHILE myboard.len < > -1 DO

    BEGIN

        WITH myboard DO

            IF len= n THEN solutions:= myboard.queens

            ELSE BEGIN (*Πρόσθεση νέας βασίλισσας στην σκακιέρα*)

         len:= len + 1;

         FOR col:= 1 TO n DO 

            BEGIN (*Έλεγχος αν μπορούμε να τοποθετήσουμε την βασίλισσα σε αυτή την στήλη*)

                ok:= true;

                FOR row:= 1 TO len-1 DO

                BEGIN

                    rowdist:= Abs(len-row);

                    coldist:= Abs(col-queens[row]);

                    samecol:= coldist= 0;

                    samediag:= coldist= rowdist;        

                    IF samecol OR samediag THEN ok:= false;

                END;

                IF ok THEN

                BEGIN

                    queens[len]:= col;

                    Putwork(me, myboard); (*Πρόσθεση νέου αντικειμένου στην Δεξαμενή Εργασίας*)

                END;

            END;

        END;

    END;

    Getwork(me, myboard); (*Νέο αντικείμενο για εξέταση*)

END;

END; (*Worker*)

 

BEGIN (*Κυρίως πρόγραμμα*)

    startitem.len:= 0;

    workpool[1]:= statritem; (*Αρχικοποίηση της Δεξαμενής Εργασίας με την άδεια σκακιέρα*)

 

    … (*Αρχικοποίηση των αθροιστών της Δεξαμενής Εργασίας όπως και στο σχήμα 10.7*)

 

    FORALL i:= 1 TO numworkers DO (*Δημιουργία των εργαζομένων*)

        Worker(i);

 

    … (*Όλες οι απαντήσεις βρίσκονται στο κανάλι “solutions”*)

 

END.

ΣΧΗΜΑ 10.12 Το πρόγραμμα των Ν Βασιλισσών για σύστημα διαμοιραζόμενης μνήμης

Επόμενο:10.6 Περίληψη Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: 10.4 Εξάλειψη της Συμφόρησης