Page 1 of 1

Αλγόριθμοι

Posted: Sat Oct 22, 2005 1:40 pm
by rapadder
Σχετικά με την πρώτη σειρά ασκήσεων, στις αναδρομικές σχέσεις (άσκηση 2), εκτός από το υποερώτημα (α) και (γ), έχει λύσει κανείς τα (β) και (δ);

Posted: Sat Oct 22, 2005 2:09 pm
by mikem4600
Ναι, εφαρμόζοντας απλώς τη μέθοδο της αντικατάστασης.

Posted: Sat Oct 22, 2005 9:42 pm
by rapadder
Ευχαριστώ :-) .

Posted: Wed Jan 04, 2006 5:16 pm
by rapadder
Έχω μια μικρή παρατήρηση να κάνω. Στο CLRS στη σελίδα 1007, στο σχήμα 34.15 δείχνει ότι εάν ο αρχικός γράφος G = (V, E) έχει κλίκα (clique) που αποτελείται από τους κόμβους {u, v, x, y} τότε το ανάστροφο γράφημα έχει Vertex Cover που αποτελείται από τους κόμβους (που περισσεύουν) {z, w}. Επίσης οι κόμβοι {u, v, x, y } συνιστούν ένα Independent Set (IS). Αποδεικνύεται και το αντίστροφο.
Παρατηρώ ότι ο γράφος G έχει Vertex Cover που αποτελείται από τους κόμβους {y, x}. Ρίχνοντας όμως μια ματιά στο ανάστροφο γράφημα, βλέπω ότι δεν υπάρχει κλίκα (clique) που να αποτελείται από τους κόμβους {u, v, z, w}, αφού αυτοί οι τέσσερις κόμβοι δεν σχηματίζουν πλήρες υπογράφημα. Δεν θα έπρεπε να ισχύει κάτι τέτοιο;

Posted: Wed Jan 04, 2006 11:04 pm
by nap
rapadder wrote:Έχω μια μικρή παρατήρηση να κάνω. Στο CLRS στη σελίδα 1007, στο σχήμα 34.15 δείχνει ότι εάν ο αρχικός γράφος G = (V, E) έχει κλίκα (clique) που αποτελείται από τους κόμβους {u, v, x, y} τότε το ανάστροφο γράφημα έχει Vertex Cover που αποτελείται από τους κόμβους (που περισσεύουν) {z, w}. Επίσης οι κόμβοι {u, v, x, y } συνιστούν ένα Independent Set (IS). Αποδεικνύεται και το αντίστροφο.

Σωστό.

rapadder wrote:Παρατηρώ ότι ο γράφος G έχει Vertex Cover που αποτελείται από τους κόμβους {y, x}.

Είσαι σίγουρος; Το {y, x} στο γράφημα G (34.15 a) δεν είναι VC (αφού υπάρχουν ακμές που δεν "καλύπτονται" από τους κόμβους x και y, όπως οι (z,w), (u,v) κ.ά.).

Posted: Thu Jan 05, 2006 12:50 am
by rapadder
Έχεις δίκιο nap. Στραβομάρα εντελώς... Ευχαριστώ πολύ για την απάντηση. Ελπίζω να ρωτήσουν και άλλοι τίποτα για να κινηθεί το thread. (Θέλω να πιστεύω ότι δεν είμαι ο μόνος που δεν τα ξέρει όλα :-) ).

Posted: Thu Jan 05, 2006 9:55 pm
by mikem4600
Να σου πω την αλήθεια, εγώ δεν έχω κοιτάξει (ακόμα) την τελευταία σειρά ασκήσεων...

Posted: Fri Jan 13, 2006 2:26 pm
by rapadder
Σχετικά με το πρόβλημα Bin Packing, έχω την εξής απορία. Το Bin Packing είναι Strongly NP-Complete. Όταν ζητείται η αναγωγή από ένα άλλο πρόβλημα (που γνωρίζουμε ότι είναι NP-Complete), πρέπει να δείξουμε κατ'αρχάς ότι υπάρχει ένας πολυωνυμικός αλγόριθμος που να μπορεί να απαντήσει ΝΑΙ σε ένα στιγμιότυπο του προβλήματος (αν αυτό είναι φυσικά αληθές). Για παράδειγμα, στον κύκλο Hamilton που επίσης είναι πρόβλημα Strongly NP-Complete, αρκεί να δούμε ότι ο προς έλεγχο κύκλος (το στιγμιότυπο του προβλήματος) καλύπτει κάθε κόμβο του γραφήματος, που γίνεται εύκολα σε πολυωνυμικό χρόνο. Το θέμα είναι ότι δεν μπορώ να σκεφτώ έναν προφανή πολυωνυμικό αλγόριθμο (για το Bin Packing), συγκεκριμένα την decision version του, που να τσεκάρει δηλαδή ότι ένας δοσμένος αριθμός Χ από κάδους (bins) χωρητικότητας Μ είναι ο ελάχιστος (για να τοποθετηθούν n αντικείμενα με διαφορετικό βάρος το κάθε ένα, ώστε το βάρος των αντικειμένων να μην ξεπερνάει την χωρητικότητα Μ του κάθε σακιδίου). Έχει βρει κανένας κανένα πολυωνυμικό αλγόριθμο για αυτόν τον έλεγχο;
Θα μπορούσα να παρέθετα απ' ευθείας την αναγωγή (απ' τό NP πλήρες πρόβλημα) αλλά πιστεύω ότι κάτι θα έλειπε για αν είμαι 100% σωστός...

Posted: Fri Jan 13, 2006 3:19 pm
by rapadder
Μια προφανής απαίτηση είναι ότι το άθροισμα των περισσευούμενων χώρων σε κάθε κάδο (κάθε κάδος ή θα είναι τελείως γεμάτος ή θα περισσεύει κάποιος χώρος) θα πρέπει να είναι μικρότερο από την χωρητικότητα Μ του κάθε κάδου. Αφού μας ενδιαφέρει η ελαχιστοποίηση του αριθμού των κάδων, στην περίπτωση αυτή η λύση μπορεί να θεωρηθεί βέλτιστη (καθώς αν τα αντικείμενα έχουν συνολικό βάρος k*W+z, k ανήκει στο {0,1,2,…} και z < W τότε σαφώς απαιτούνται τουλάχιστον k+1 κάδοι. Το θέμα είναι εάν για κάθε σύνολο αντικειμένων (με βάρη μικρότερα από M το καθένα για να χωράνε στους κάδους), η βέλτιστη λύση έχει ακριβώς k+1 κάδους.

Posted: Fri Jan 13, 2006 3:50 pm
by rapadder
Το όριο αυτό είναι υπερβολικά αυστηρό. Π.χ. για χωρητικότητα κάδου Μ = 10 μονάδες και αντικείμενα βάρους {9, 8, 7, 6}, το παραπάνω κάτω όριο είναι 3 κάδοι (9+8+7+6 = 30), ενώ απαιτούνται 4. Στη χειρότερη περίπτωση θα αντιστοιχεί ένας κάδος σε κάθε αντικείμενο. Οπότε ισχύει ότι ο ελάχιστος αριθμός κάδων θα είναι >= k+1 (δες παραπάνω post) και <= n (πλήθους αντικειμένων). Δεν νομίζω ότι στη γενική περίπτωση μπορούμε να βρούμε κάποιο συγκεκριμένο όριο ώστε κάθε βέλτιστη λύση να πρέπει να ισούται με αυτό.
Το θέμα παραμένει. Αφού το πρόβλημα είναι (strongly) NP – Complete, θα πρέπει να μπορώ να απαντήσω σε πολυωνυμικό χρόνο για ένα στιγμιότυπο του προβλήματος (αν αυτό ικανοποιείται).

Posted: Sat Jan 14, 2006 10:14 am
by Erevodifwntas
Το decision πρόβλημα δεν έχει σχέση με το ελάχιστο