Αλγόριθμοι
- rapadder
- Gbyte level
- Posts: 1896
- Joined: Thu Jun 17, 2004 7:12 pm
- Academic status: Alumnus/a
- Gender: ♂
Αλγόριθμοι
Σχετικά με την πρώτη σειρά ασκήσεων, στις αναδρομικές σχέσεις (άσκηση 2), εκτός από το υποερώτημα (α) και (γ), έχει λύσει κανείς τα (β) και (δ);
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
- rapadder
- Gbyte level
- Posts: 1896
- Joined: Thu Jun 17, 2004 7:12 pm
- Academic status: Alumnus/a
- Gender: ♂
Έχω μια μικρή παρατήρηση να κάνω. Στο 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}, αφού αυτοί οι τέσσερις κόμβοι δεν σχηματίζουν πλήρες υπογράφημα. Δεν θα έπρεπε να ισχύει κάτι τέτοιο;
Παρατηρώ ότι ο γράφος 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). Αποδεικνύεται και το αντίστροφο.
Είσαι σίγουρος; Το {y, x} στο γράφημα G (34.15 a) δεν είναι VC (αφού υπάρχουν ακμές που δεν "καλύπτονται" από τους κόμβους x και y, όπως οι (z,w), (u,v) κ.ά.).rapadder wrote:Παρατηρώ ότι ο γράφος G έχει Vertex Cover που αποτελείται από τους κόμβους {y, x}.
It is by will alone I set my mind in motion...
- rapadder
- Gbyte level
- Posts: 1896
- Joined: Thu Jun 17, 2004 7:12 pm
- Academic status: Alumnus/a
- Gender: ♂
Σχετικά με το πρόβλημα Bin Packing, έχω την εξής απορία. Το Bin Packing είναι Strongly NP-Complete. Όταν ζητείται η αναγωγή από ένα άλλο πρόβλημα (που γνωρίζουμε ότι είναι NP-Complete), πρέπει να δείξουμε κατ'αρχάς ότι υπάρχει ένας πολυωνυμικός αλγόριθμος που να μπορεί να απαντήσει ΝΑΙ σε ένα στιγμιότυπο του προβλήματος (αν αυτό είναι φυσικά αληθές). Για παράδειγμα, στον κύκλο Hamilton που επίσης είναι πρόβλημα Strongly NP-Complete, αρκεί να δούμε ότι ο προς έλεγχο κύκλος (το στιγμιότυπο του προβλήματος) καλύπτει κάθε κόμβο του γραφήματος, που γίνεται εύκολα σε πολυωνυμικό χρόνο. Το θέμα είναι ότι δεν μπορώ να σκεφτώ έναν προφανή πολυωνυμικό αλγόριθμο (για το Bin Packing), συγκεκριμένα την decision version του, που να τσεκάρει δηλαδή ότι ένας δοσμένος αριθμός Χ από κάδους (bins) χωρητικότητας Μ είναι ο ελάχιστος (για να τοποθετηθούν n αντικείμενα με διαφορετικό βάρος το κάθε ένα, ώστε το βάρος των αντικειμένων να μην ξεπερνάει την χωρητικότητα Μ του κάθε σακιδίου). Έχει βρει κανένας κανένα πολυωνυμικό αλγόριθμο για αυτόν τον έλεγχο;
Θα μπορούσα να παρέθετα απ' ευθείας την αναγωγή (απ' τό NP πλήρες πρόβλημα) αλλά πιστεύω ότι κάτι θα έλειπε για αν είμαι 100% σωστός...
Θα μπορούσα να παρέθετα απ' ευθείας την αναγωγή (απ' τό NP πλήρες πρόβλημα) αλλά πιστεύω ότι κάτι θα έλειπε για αν είμαι 100% σωστός...
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
- rapadder
- Gbyte level
- Posts: 1896
- Joined: Thu Jun 17, 2004 7:12 pm
- Academic status: Alumnus/a
- Gender: ♂
Μια προφανής απαίτηση είναι ότι το άθροισμα των περισσευούμενων χώρων σε κάθε κάδο (κάθε κάδος ή θα είναι τελείως γεμάτος ή θα περισσεύει κάποιος χώρος) θα πρέπει να είναι μικρότερο από την χωρητικότητα Μ του κάθε κάδου. Αφού μας ενδιαφέρει η ελαχιστοποίηση του αριθμού των κάδων, στην περίπτωση αυτή η λύση μπορεί να θεωρηθεί βέλτιστη (καθώς αν τα αντικείμενα έχουν συνολικό βάρος k*W+z, k ανήκει στο {0,1,2,…} και z < W τότε σαφώς απαιτούνται τουλάχιστον k+1 κάδοι. Το θέμα είναι εάν για κάθε σύνολο αντικειμένων (με βάρη μικρότερα από M το καθένα για να χωράνε στους κάδους), η βέλτιστη λύση έχει ακριβώς k+1 κάδους.
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
- rapadder
- Gbyte level
- Posts: 1896
- Joined: Thu Jun 17, 2004 7:12 pm
- Academic status: Alumnus/a
- Gender: ♂
Το όριο αυτό είναι υπερβολικά αυστηρό. Π.χ. για χωρητικότητα κάδου Μ = 10 μονάδες και αντικείμενα βάρους {9, 8, 7, 6}, το παραπάνω κάτω όριο είναι 3 κάδοι (9+8+7+6 = 30), ενώ απαιτούνται 4. Στη χειρότερη περίπτωση θα αντιστοιχεί ένας κάδος σε κάθε αντικείμενο. Οπότε ισχύει ότι ο ελάχιστος αριθμός κάδων θα είναι >= k+1 (δες παραπάνω post) και <= n (πλήθους αντικειμένων). Δεν νομίζω ότι στη γενική περίπτωση μπορούμε να βρούμε κάποιο συγκεκριμένο όριο ώστε κάθε βέλτιστη λύση να πρέπει να ισούται με αυτό.
Το θέμα παραμένει. Αφού το πρόβλημα είναι (strongly) NP – Complete, θα πρέπει να μπορώ να απαντήσω σε πολυωνυμικό χρόνο για ένα στιγμιότυπο του προβλήματος (αν αυτό ικανοποιείται).
Το θέμα παραμένει. Αφού το πρόβλημα είναι (strongly) NP – Complete, θα πρέπει να μπορώ να απαντήσω σε πολυωνυμικό χρόνο για ένα στιγμιότυπο του προβλήματος (αν αυτό ικανοποιείται).
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
-
- Gbyte level
- Posts: 1098
- Joined: Thu Apr 22, 2004 2:18 pm
- Academic status: Alumnus/a
- Gender: ♂
- Location: In a Long Time Ago in A Galaxy far far away
- Contact: