Αναγωγή

[Mathletic]

Γειά σας!!

Κοιτάζω την εξής λυμένη άσκηση:
Μια εταιρεία με φορτηγά έχει δύο ίδια φορτηγά. Ο χώρος αποσκευών είναι ένα ορθογώνιο παραλληλεπίπεδο με εμβαδόν και ύψος . Τα πακέτα που η επιχείρησή έχει να προσφέρει είναι επίσης ορθογώνια παραλληλεπίπεδα.
Τα πακέτα πρέπει να κατανεμηθούν στα δύο φορτηγά.
Το πρόβλημα ορίζεται ως εξής:
- Έχουμε πακέτα με μέγεθος .
- Το ερώτημα είναι αν οι συσκευασίες χωράνε στα δύο φορτηγά.
Δείξτε ότι το πρόβλημα είναι NP-complete.

Για να το δείξουμε, ανάγουμε το πρόβλημα partition στο παραπάνω ως εξής:
Έστω η είσοδος για το PARTITION. Έστω . Κατασκευάζουμε για κάθε αριθμό ένα πακέτο μεγέθους για το παραπάνω πρόβλημα. Τότε για ένα σύνολο έχουμε ότι

Οπότε, υπάρχει η κατανομή των σε δύο ίδια σύνολα αν και μόνο αν τα πακέτα ταιριάζει στα δύο φορτηγά.


Δεν έχω καταλάβει στην αναγωγή το μέρος που κατασκευάζουμε για κάθε αριθμό ένα πακέτο μεγέθους . Γιατί θεωρούμε αυτό το μέγεθος;

[taratoris]

Αρχικά φαίνεται οτι ίσως υπάρχει πρόβλημα με την εκφώνηση. Εννοείς οτι θέλουμε να δούμε αν μπορούμε να κατανείμουμε τα πακέτα στα δύο φορτηγά έτσι ώστε το άθροισμα του μήκους των πακέτων στο πρώτο φορτηγό να είναι ίσο με το αθροισμα του μήκους των πακέτων στο δεύτερο. Διαφορετικά δεν μπορείς να κάνεις αναγωγή απο PARTITION.

Σχετικά με την ερώτησή σου, το πλάτος και το ύψος (5 και 3) που διάλεξαν δεν έχει κάποια σημασία. Μπορείς να υποθέσεις οτι στην αναγωγή σου οτι τα δύο φορτηγά έχουν αρκετά μεγάλο πλάτος και ύψος και μόνο το μήκος είναι πρόβλημα.

[Mathletic]

Σχετικά με την ερώτησή σου, το πλάτος και το ύψος (5 και 3) που διάλεξαν δεν έχει κάποια σημασία. Μπορείς να υποθέσεις οτι στην αναγωγή σου οτι τα δύο φορτηγά έχουν αρκετά μεγάλο πλάτος και ύψος και μόνο το μήκος είναι πρόβλημα.

Γιατί μπορούμε να υποθέσουμε ότι τα δύο φορτηγά έχουν αρκετά μεγάλο πλάτος και ύψος και μόνο το μήκος είναι πρόβλημα? Μπορείτε να μου το εξηγήσετε?

[taratoris]

Ο λόγος είναι οτι θέλεις να αποδείξεις οτι αν μπορείς να λύσεις το αρχικό πρόβλημα (με τα φορτηγά) σε πολυωνυμικό χρόνο τότε μπορείς να λύσεις το PARTITION σε πολυωνυμικό χρόνο. Ίσως να μην ήμουν ξεκάθαρος αλλά αυτό που εννοώ είναι οτι το πλάτος και το ύψος δεν έχουν σημασία στο αρχικό πρόβλημα. Πχ αν είχαμε ορίσει το πρόβλημα με τα φορτηγά να έχουν διαστάσεις τότε θα δημιουργούσαμε στην αναγωγή κουτιά που το καθένα θα ειχε πλάτος και ύψος και των οποίων το άθροισμα των μηκών θα ήταν . (Ουσιαστικά τα μεγέθη (2,5,3) δεν έχουν κάποιο ιδιαίτερο νόημα.) Ο λόγος που διαλέγει στην λύση το κάθε πακέτο να έχει πλάτος 5 και ύψος 3 είναι επειδή τότε το κάθε κουτί χωράει ακριβώς στο πλάτος και το ύψος μέσα σε κάθε φορτηγό και άρα δεν μπορεί να υπάρχει κάποιο άλλο κουτί απο επάνω του ή δίπλα του. Άρα το μόνο πρόβλημα είναι αν τα κουτιά μπορούν να χωριστούν έτσι ώστε να χωρούν μέσα στα φορτηγά κατά μήκος. Αλλά εφόσον το άθροισμα των μηκών των κουτιών είναι 4 και το κάθε φορτηγό έχει μήκος 2, αυτό μπορεί να συμβεί αν και μόνο αν τα κουτιά χωριστουν σε δύο ομάδες έτσι ώστε το άθροισμα των μηκών σε κάθε ομάδα να είναι 2.

Edit: Το πρώτο μου σχόλιο ήταν λάθος. Δεν υπάρχει κανένα πρόβλημα με την εκφώνηση του προβλήματος.

[Mathletic]

Ο λόγος είναι οτι θέλεις να αποδείξεις οτι αν μπορείς να λύσεις το αρχικό πρόβλημα (με τα φορτηγά) σε πολυωνυμικό χρόνο τότε μπορείς να λύσεις το PARTITION σε πολυωνυμικό χρόνο. Ίσως να μην ήμουν ξεκάθαρος αλλά αυτό που εννοώ είναι οτι το πλάτος και το ύψος δεν έχουν σημασία στο αρχικό πρόβλημα. Πχ αν είχαμε ορίσει το πρόβλημα με τα φορτηγά να έχουν διαστάσεις τότε θα δημιουργούσαμε στην αναγωγή κουτιά που το καθένα θα ειχε πλάτος και ύψος και των οποίων το άθροισμα των μηκών θα ήταν . (Ουσιαστικά τα μεγέθη (2,5,3) δεν έχουν κάποιο ιδιαίτερο νόημα.) Ο λόγος που διαλέγει στην λύση το κάθε πακέτο να έχει πλάτος 5 και ύψος 3 είναι επειδή τότε το κάθε κουτί χωράει ακριβώς στο πλάτος και το ύψος μέσα σε κάθε φορτηγό και άρα δεν μπορεί να υπάρχει κάποιο άλλο κουτί απο επάνω του ή δίπλα του. Άρα το μόνο πρόβλημα είναι αν τα κουτιά μπορούν να χωριστούν έτσι ώστε να χωρούν μέσα στα φορτηγά κατά μήκος. Αλλά εφόσον το άθροισμα των μηκών των κουτιών είναι 4 και το κάθε φορτηγό έχει μήκος 2, αυτό μπορεί να συμβεί αν και μόνο αν τα κουτιά χωριστουν σε δύο ομάδες έτσι ώστε το άθροισμα των μηκών σε κάθε ομάδα να είναι 2.

Θα μπορούσαμε να θεωρήσουμε ότι το κάθε πακέτο έχει μήκος 2 και ύψος 3 και το πρόβλημα να είναι αν τα κουτιά μπορούν να χωριστούν έτσι ώστε να χωρούν μέσα στα φορτηγά κατά πλάτος? Ή υπάρχει συγκεκριμένος λόγος που θεωρούμε ότι το κάθε πακέτο έχει πλάτος 5 και ύψος 3?

[taratoris]

Ναι μπορείς να κάνεις και αυτό. Αλλά τότε πρέπει το άθροισμα του πλάτους όλων των πακέτων να είναι 2*5=10.

[Mathletic]

Το κατάλαβα!! Ευχαριστώ πολύ!!