Φίλοι του αλλοδαπού

Ο σχεδιασμός μέθοδος αλγόριθμος Branch και δεσμεύονται (ονομάζεται επίσης υποκαταστημάτων και Διαστασιολόγηση) είναι μια παραλλαγή του Backtracking βελτιωθεί σημαντικά και εφαρμόζεται κυρίως για την επίλυση ζητημάτων ή προβλήματα βελτιστοποίησης.

Η τεχνική του Κλάδου και δεσμεύεται ερμηνεύεται συνήθως ως ένα δέντρο λύση, όπου κάθε υποκατάστημα οδηγεί σε μια πιθανή λύση για την τρέχουσα θέση. Το χαρακτηριστικό αυτής της τεχνικής σε προηγούμενα προγράμματα (και το οποίο οφείλει το όνομά του) είναι ότι ο αλγόριθμος είναι υπεύθυνη για τον εντοπισμό τον κλάδο των λύσεων που δεν είναι πλέον είναι η καλύτερη επιλογή για «κλάδεμα» του υποκαταστήματος δέντρο και να μη συνεχιστεί η σπατάλη πόρων και διαδικασιών

Παρουσιάζοντας Πρόβλημα

Από το ακόλουθο αλγόριθμο για την επίλυση των Mochila 0 / 1 μέσω υποκαταστημάτων και κλάδεμα, έχω εφαρμόσει ένα πρόγραμμα σε C # που επιλύει αυτό το πρόβλημα με τις ακόλουθες στρατηγικές:

• FIFO - (First In First Out) First In - First Out
• LIFO - (Last In First Out) τελευταία στην πρώτη έξω. (PILA)
• LC - LIFO - τελευταία σε Array First Out. (Συστοιχία ΜΠΑΤΑΡΙΕΣ)
• LC - FIFO - Array First In First Out. (Σειρά ΚΟΛΛΑ)

Ο κατάλογος των ζωντανών κόμβων (LNV), θα πρέπει να αποτελείται από αντικείμενα της κλάσης κόμβου, η οποία ορίζεται ως εξής:

Ψήφισμα Process

1. Διανύσματα κατατάσσονται ανάλογα με το βάρος πλεονέκτημα και ο δείκτης Β / σ.
2. Μόλις αυτό κόμβο δημιουργείται και προστίθεται στη λίστα των κόμβων ζωντανός.
3. Στο σημείο αυτό εισέρχεται σε ένα βρόχο που επαναλαμβάνεται έως ότου το LNV αδειάσει τα ακόλουθα:
4. Αν ο κόμβος που εξάγονται υπόσχεται ότι το καλύτερο συμφέρον που μελετήσαμε μέχρι τώρα (πρώτη κλαδέματα) είδος παιδιά τους στον κόμβο y.
5. Για κάθε παιδί, αν το βάρος που περιέχει είναι> από ό, τι δεν είναι το μέγιστο επιτρεπόμενο βάρος προσπαθήσω (δεν κάνω τίποτε) ότι για τον κατασκευαστή κατηγορίας Ι ξεκινά κόμβους και ύψη τις αξίες πολύ μικρούς αριθμούς.
6. Διαφορετικά θεραπεία και ο κόμβος των φύλων εκτιμήσεις αναλόγως.
7. Κατόπιν ελέγχει αν η σημερινή κατάσταση είναι μια λύση και αν ναι ενημερώνει τον κόμβο λύση.
8. Αν καμιά λύση δεν δούμε αν το άνω όριο του κόμβου που έχουμε να κάνουμε με είναι μεγαλύτερο ή ίσο προς C ότι εμείς (κλάδεμα 2), προστίθεται LNV αν δεν είναι.

Στόχος:

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

Προτεινόμενης λύσης

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