Venus AUEB Forum

Σχετικά με την πρώτη σειρά ασκήσεων, στις αναδρομικές σχέσεις (άσκηση 2), εκτός από το υποερώτημα (α) και (γ), έχει λύσει κανείς τα (β) και (δ);

Ναι, εφαρμόζοντας απλώς τη μέθοδο της αντικατάστασης.

Ευχαριστώ .

Έχω μια μικρή παρατήρηση να κάνω. Στο 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}, αφού αυτοί οι τέσσερις κόμβοι δεν σχηματίζουν πλήρες υπογράφημα. Δεν θα έπρεπε να ισχύει κάτι τέτοιο;

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) κ.ά.).

Έχεις δίκιο nap. Στραβομάρα εντελώς... Ευχαριστώ πολύ για την απάντηση. Ελπίζω να ρωτήσουν και άλλοι τίποτα για να κινηθεί το thread. (Θέλω να πιστεύω ότι δεν είμαι ο μόνος που δεν τα ξέρει όλα ).

Να σου πω την αλήθεια, εγώ δεν έχω κοιτάξει (ακόμα) την τελευταία σειρά ασκήσεων...

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

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

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

Το decision πρόβλημα δεν έχει σχέση με το ελάχιστο