Γραφος & Αλγόριθμοι

Υποθέστε ότι σας δίνεται ένα γράφημα G το οποίο έχει τη μορφή ενός πλέγματος n × n. Ένα γράφημα πλέγματος είναι ένα γράφημα του οποίου το σύνολο των κόμβων είναι το σύνολο όλων των διατεταγμένων ζευγών των φυσικών αριθμών (i, j), όπου 1 ≤ i ≤ n και  1 ≤ j ≤ n. Οι κόμβοι (i, j) και (k, l) συνδέονται μεταξύ τους αν και μόνο αν |i - k| + |j - l| = 1. Αυτό σημαίνει ότι ο κάθε κόμβος συνδέεται με τους 4 γειτονικούς του κόμβους (πάνω-κάτω και δεξιά-αριστερά) όπως φαίνεται και στο παρακάτω σχήμα, πλην αυτών των κόμβων που είναι στο σύνορο.

Κάθε κόμβος v χαρακτηρίζεται από μία ετικέτα με ένα πραγματικό αριθμό x_v. Υποθέτουμε ότι όλες οι ετικέτες είναι ανά δύο διαφορετικές μεταξύ τους. Ορίζουμε ως καθολικό ελάχιστο κόμβο, τον κόμβο με τη μικρότερη ετικέτα από όλους τους κόμβους στο G. Στο παραπάνω σχήμα ο κόμβος αυτός είναι ο (3,2) μιας και έχει την ελάχιστη ετικέτα (2). Ένας κόμβος v θα ονομάζεται τοπικό ελάχιστο όταν όλοι οι γείτονές του έχουν τιμή μεγαλύτερη από αυτόν. Στο παραπάνω σχήμα εκτός του (3,2), τοπικά ελάχιστα είναι και οι κόμβοι (2,3) και (4,1).

Στα ερωτήματα που ακολουθούν, όταν ζητείται η πολυπλοκότητα ενός αλγόριθμου αυτή θα μετριέται με βάση το πλήθος των κόμβων που προσπελαύνονται. Για παράδειγμα, αν προσπελαστούν συνολικά x κόμβοι τότε η πολυπλοκότητα θα είναι O(x) ανεξαρτήτως αν χρειάστηκαν πολλές επιπλέον πράξεις ώστε να κάνουμε υπολογισμό – π.χ. x² πολλαπλασιασμοί. Σας ζητούνται τα εξής:

A) Να αποδείξετε ότι κάθε πλέγμα G έχει τουλάχιστον ένα τοπικό ελάχιστο.

Β) Δώστε έναν επαναληπτικό αλγόριθμο που κάνει Ω(nlogn) προσπελάσεις σε κόμβους για την εύρεση κάποιου τοπικού ελαχίστου. Αποδείξτε την πολυπλοκότητα του αλγόριθμού σας.

Γ) Έστω ότι με B αναπαριστούμε το σύνορο του πλέγματος G, δηλαδή τις στήλες 1 και nκαθώς και τις γραμμές 1 και n. Για παράδειγμα, στο παραπάνω σχήμα το Βπεριέχει όλους τους κόμβους πλην των (2,2), (3,2), (2,3) και (3,3). Θα λέμε ότι το πλέγμα G έχει την ιδιότητα λ αν περιέχει έναν κόμβο v Ï Bπου να είναι γειτονικός κάποιου κόμβου στο Bκαι να ισχύει ότι x_v < x_b για κάθε b Î B. Αυτό σημαίνει ότι το καθολικό ελάχιστο δεν βρίσκεται στο σύνορο B. Άρα, υπάρχει τουλάχιστον ένα τοπικό ελάχιστο που δεν ανήκει στο B. Αυτό το ελάχιστο το ονομάζουμε εσωτερικό τοπικό ελάχιστο. Το παραπάνω πλέγμα έχει αυτή την ιδιότητα αφού οι κόμβοι (2,3) και (3,2) έχουν μικρότερη ετικέτα από όλους τους κόμβους του Β. Με δεδομένο ότι έχετε έναν αλγόριθμο πολυπλοκότητας O(n) (θα σας ζητηθεί να τον σχεδιάσετε στο υποερώτημα (Δ)) για την εύρεση κάποιου τοπικού ελαχίστου σε ένα πλέγμα G με την ιδιότητα λ, δώστε έναν αλγόριθμο πολυπλοκότητας O(n) που να υπολογίζει ένα τοπικό ελάχιστο σε ένα πλέγμα G που ενδεχομένως δεν έχει την ιδιότητα λ.

Δ) Δώστε έναν αλγόριθμο διαίρει-και-βασίλευε πολυπλοκότητας Ο(n) που να βρίσκει ένα (όχι όλα) εσωτερικό τοπικό ελάχιστο σε ένα πλέγμα G με την ιδιότητα λ. Αποδείξτε την πολυπλοκότητα του αλγόριθμου. Προσέξτε ότι αφού το πλέγμα G έχει n² κόμβους για να πετύχουμε O(n) πολυπλοκότητα θα πρέπει να μην ελέγχουμε όλους τους κόμβους.

Υπόδειξη: διαιρέστε το πλέγμα με βάση τη μεσαία γραμμή και τη μεσαία στήλη σε τέσσερα υποπλέγματα. Έπειτα αναζητήστε το ελάχιστο μεταξύ των κόμβων στη μεσαία γραμμή και μεσαία στήλη, του συνόρου του G και όλων των γειτονικών τους κόμβων και με βάση το αποτέλεσμα που θα πάρετε συνεχίστε αναδρομικά στο κατάλληλο υποπλέγμα ή τερματίστε επιστρέφοντας το αποτέλεσμα.
-----

Ο ΘΑ αποδείξουμε ότι κάθε πλέγμα G έχει  ένα τοπικό ελάχιστο.

Το πλέγμα είναι n_xn με κάθε κόμβο  (I,j)να συνδέεται με τον επόμενο κόμβο (k,l)  μόνο όταν ικανοποιείται  η συνθήκη |i - k| + |j - l| = 1 . Επομένως ο μέγιστος αριθμός γειτόνων  που  έχει ένας κόμβος είναι 4 ,όπως σε κάθε πλέγμα n_xn. Θα πρέπει να ελέγξουμε  τις ετικέτες τον 4 γειτόνων .Γνωρίζουμε ότι οι ετικέτες ανα δυο είναι διαφορετικές δηλαδή εάν ο κόμβος μας κ1 συνδέετε με τους κόμβους κ2,κ3,κ4 και κ5 τότε οι ετικέτες που είναι σε κάθε κόμβο θα είναι διαφορετικές ανα δυο .Επομένως η ετικέτα του κόμβου κ1  θα είναι διαφορετική με την ετικέτα του κ2, και την ετικέτα του κ4 και του κ5. Έστω η ετικέτα κ1 του κόμβου είναι η ε1 και ε2,ε3,ε4,ε5 οι ετικέτες που έχουν οι κομβόι κ2,κ3,κ4,κ5 αντίστοιχα.  Τότε ο κ1 όπως αναφέραμε συνδέεται με τους κ2,κ3,κ4,κ5 και οι ετικέτα ε1#ε2 αλλά   ε1#ε3 , ε1#ε4 και ε1#ε5 , διότι ανα δυο είναι διαφορετικές. Δηλαδή θα υπάρχει μια ετικέτα που θα είναι μικρότερη από Όλες.

Δηλαδή θα Μπορούσαμε  με βήματα να διαπιστώσουμε ποιος γείτονας από τα κ2,κ3,κ3,κ4και κ5 έχει την μικρότερη ετικέτα .

Συγκρίνοντας την ε1 με την ε2  όποια από τις 2 είναι μικρότερη την συγκρίνουμε με τις υπόλοιπες 4 οπού μια από αυτές θα είναι και η μικρότερη και ο κόμβος με την μικρότερη ετικέτα θα είναι ο τοπικος ελάχιστος. 

<Β.>

 Ο Θα προσπαθήσουμε να δώσουμε ένα αλγόριθμο που χρειάζεται  Ω(nlogn) προσπελάσεις δηλαδή η χειρότερη περίπτωση θα έχει κόστος  nlogn. Πριν το σχεδιασμό να θυμηθούμε ότι χρειαζόμαστε Ω(nlogn) συγκρίσεις στην χειρότερη περίπτωση για  να ταξινομήσουμε αριθμούς , ένας  τέτοιος αλγόριθμος είναι και η Mergesort που χρησιμοποιεί την τεχνική divide and conquer

Tο Γράφημα G είναι πλέγμα  nxn , δηλαδή θα μπορούσαμε να δούμε το πλέγμα ως ένα πίνακα n_xn . Συνολικά το πλήθος όλων τον κόμβων είναι nxn το ιδιο και οι ετικέτες που έχει κάθε κόμβος. Κάθε κόμβος συνορεύει με διπλανο κόμβο όπως ορίζει η συνάρτηση σύνδεσης και επειδή το γράφημα είναι πλέγμα κάθε κόμβος θα έχει από 3 ως 4 γείτονες ( 3 ή 4 γείτονες). Επομένως θα μπορούσαμε να ελενξουμε την ετικέτα κάθε κόμβου  και να την συγκρίνουμε με τους γείτονες τους, η διαδικασία θα επαναλαμβάνεται για όλους τους κόμβους. Είδαμε ότι ο συνολικός αριθμός των κόμβων είναι nXn οπού σε κάθε κόμβο για να διαπιστώσουμε  το τοπικό ελάχιστο θα χρειαστεί να ελέγξουμε όλες τις ετικέτες από του γειτονικούς κόμβους . Επομένως σε κάθε κόμβο  που θα ελέγξουμε  για τοπικό ελάχιστο  οι περισσότερες πράξεις που μπορούν να γίνουν είναι 4 συγκρίσεις και 4 καταχωρήσεις , το κόστος των παραπάνω πράξεων είναι 8Θ(1) δηλαδή Θ(1).Δηλαδή το κόστος για κάθε κόμβου θα είναι Θ(1) , επομένως το κόστος για nXn κόμβους θα είναι  Θ(1) * n*n δηλαδή είναι Θ(n*n)=Θ(n²).

Παρακάτω θα δούμε αναλυτικά τον παραπάνω τόπο σκέψης.

Τον ψευδοκωδικα στην φυσική γλώσσα.

1.    Επέλεξε κόμβο προς έλεγχο

2.    Αποθήκευσε την ετικέτα του ως ελάχιστο

3.    Σύγκρινε το ελάχιστο με το γείτονα.

4.    Εάν το ελάχιστο είναι μεγαλύτερο από την ετικέτα του γείτονα τότε αποθήκευσε την ετικέτα ως τοπικό ελάχιστο  και τον κόμβο_γειτονα  ως τοπικό ελάχιστο κόμβο .

5.    Επανάλαβε το βήμα 4 για ολους τους γείτονες  του κόμβου.

6.    Επανέλαβε το  βήμα 1 ως 5 για όλους τους κόμβους.

Παρακάτω η πιο αυστηρός ψευδοκωδικας  .

Η procedure δεχτέ το γράφημα G μεγέθους nxm οπού m=n.

Procedure LocalMinimum (n,m)

Min←0;i←0; j←0  -- αρχικοποίηση

While (i<=n) do

While (j<=m) do

  Min←Flag [i,j]--διάβασε την ετικέτα του κόμβου και αποθήκευσε την στην μεταβλητή min

Check neighbor of [i , j]--ελέγχουμε τους γείτονες   του κόμβο i,j

If (neighbor Flag<min) then  -- έλεγχος εάν η ετικέτα  του γείτονα είναι μικρότερη   

         Min← neighbor Flag-- Αποθήκευσε την μικρότερη στην μεταβλητη min.

  j←j+1 

               

End While

       Return [i,j], Flag

       i←i+1

        End While

Παραπάνω είδαμε τον ψευδοκώδικα πιο αυστηρά προγραμματιστικά. Στο θαλασσή πλαίσιο είναι οι εντολές που θα εκτελεστούν nxm φορές, (n=m) . Όπως είδαμε και παραπάνω αυτές οι εντολές έχουν πολυπλοκότητά Θ(1). Δηλαδή συνολικά η πολυπλοκότητα  θα είναι Θ(1) * n*n= (Θ(n²).

Γενικά ισχύει Θ(n)= O(n) ÇΩ(n)

Παραπάνω βλέπουμε τις γραφικές παρατάσεις των συναρτήσεων.

Δηλαδή θέλουμε η  συνάρτηση μας να έχει Ω(nlogn) κόστος δηλαδή  ο νέος αλγόριθμος που υπολογίσαμε Α(n) πρέπει να είναι Α(n)≥nlogn που ισχύει διότι Α(n)=Θ(n²) και

Θ(n²) ≥ nlogn που ισχύει (για n>1).