Επίλυση του προβλήματος του πλανόδιου πωλητή. Κατάλογος χρησιμοποιημένης βιβλιογραφίας. Γενικό σχέδιο για την επίλυση του προβλήματος του ταξιδιώτη πωλητή
X 0 = (1,2); (2,3); (3,4); (4,5); (5,1)
Τότε F(X 0) = 90 + 40 + 60 + 50 + 20 = 260
Για να προσδιορίσουμε το κάτω όριο του συνόλου, χρησιμοποιούμε λειτουργία μείωσηςή μείωση της γραμμής του πίνακα κατά σειρά, για την οποία είναι απαραίτητο να βρεθεί το ελάχιστο στοιχείο σε κάθε σειρά του πίνακα D.
d i = min(j) d ij
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | Μ | 90 | 80 | 40 | 100 | 40 |
| 2 | 60 | Μ | 40 | 50 | 70 | 40 |
| 3 | 50 | 30 | Μ | 60 | 20 | 20 |
| 4 | 10 | 70 | 20 | Μ | 50 | 10 |
| 5 | 20 | 40 | 50 | 20 | Μ | 20 |
Στη συνέχεια αφαιρούμε το d i από τα στοιχεία της εν λόγω σειράς. Από αυτή την άποψη, στον νέο πίνακα που λήφθηκε θα υπάρχει τουλάχιστον ένα μηδέν σε κάθε σειρά.
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | Μ | 50 | 40 | 0 | 60 |
| 2 | 20 | Μ | 0 | 10 | 30 |
| 3 | 30 | 10 | Μ | 40 | 0 |
| 4 | 0 | 60 | 10 | Μ | 40 |
| 5 | 0 | 20 | 30 | 0 | Μ |
Εκτελούμε την ίδια λειτουργία μείωσης κατά μήκος των στηλών, για τις οποίες βρίσκουμε το ελάχιστο στοιχείο σε κάθε στήλη:
d j = min(i) d ij
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | Μ | 50 | 40 | 0 | 60 |
| 2 | 20 | Μ | 0 | 10 | 30 |
| 3 | 30 | 10 | Μ | 40 | 0 |
| 4 | 0 | 60 | 10 | Μ | 40 |
| 5 | 0 | 20 | 30 | 0 | Μ |
| DJ | 0 | 10 | 0 | 0 | 0 |
Αφού αφαιρέσουμε τα ελάχιστα στοιχεία, λαμβάνουμε έναν εντελώς μειωμένο πίνακα, όπου ονομάζονται οι τιμές d i και d j σταθερές χύτευσης.
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | Μ | 40 | 40 | 0 | 60 |
| 2 | 20 | Μ | 0 | 10 | 30 |
| 3 | 30 | 0 | Μ | 40 | 0 |
| 4 | 0 | 50 | 10 | Μ | 40 |
| 5 | 0 | 10 | 30 | 0 | Μ |
Το άθροισμα των σταθερών αναγωγής καθορίζει το κάτω όριο του H:
H = ∑d i + ∑d j
H = 40+40+20+10+20+0+10+0+0+0 = 140
Τα στοιχεία του πίνακα d ij αντιστοιχούν στην απόσταση από το σημείο i στο σημείο j.
Εφόσον υπάρχουν n πόλεις στον πίνακα, τότε το D είναι ένας πίνακας nxn με μη αρνητικά στοιχεία d ij >=0
Κάθε έγκυρη διαδρομή αντιπροσωπεύει έναν κύκλο κατά τον οποίο ο περιοδεύων πωλητής επισκέπτεται την πόλη μόνο μία φορά και επιστρέφει στην αρχική πόλη.
Το μήκος της διαδρομής καθορίζεται από την έκφραση:
F(M k) = ∑d ij
Επιπλέον, κάθε γραμμή και στήλη περιλαμβάνεται στη διαδρομή μόνο μία φορά με το στοιχείο d ij .
Βήμα 1.
Προσδιορισμός της ακμής διακλάδωσης
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | Μ | 40 | 40 | 0(40) | 60 | 40 |
| 2 | 20 | Μ | 0(20) | 10 | 30 | 10 |
| 3 | 30 | 0(10) | Μ | 40 | 0(30) | 0 |
| 4 | 0(10) | 50 | 10 | Μ | 40 | 10 |
| 5 | 0(0) | 10 | 30 | 0(0) | Μ | 0 |
| DJ | 0 | 10 | 10 | 0 | 30 | 0 |
d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Το μεγαλύτερο άθροισμα σταθερών αναγωγής είναι (40 + 0) = 40 για την ακμή (1,4), επομένως, το σύνολο χωρίζεται σε δύο υποσύνολα (1,4) και (1*,4*).
H(1*,4*) = 140 + 40 = 180
Εξαλείφουμε το άκρο (1,4) αντικαθιστώντας το στοιχείο d 14 = 0 με M, μετά από το οποίο πραγματοποιούμε την επόμενη μείωση του πίνακα απόστασης για το προκύπτον υποσύνολο (1*,4*), ως αποτέλεσμα λαμβάνουμε ένα μειωμένη μήτρα.
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | Μ | 40 | 40 | Μ | 60 | 40 |
| 2 | 20 | Μ | 0 | 10 | 30 | 0 |
| 3 | 30 | 0 | Μ | 40 | 0 | 0 |
| 4 | 0 | 50 | 10 | Μ | 40 | 0 |
| 5 | 0 | 10 | 30 | 0 | Μ | 0 |
| DJ | 0 | 0 | 0 | 0 | 0 | 40 |
Η συμπερίληψη της ακμής (1,4) πραγματοποιείται εξαιρώντας όλα τα στοιχεία της 1ης σειράς και της 4ης στήλης, στην οποία το στοιχείο d 41 αντικαθίσταται από το M για να εξαλειφθεί ο σχηματισμός ενός μη Χαμιλτονιανού κύκλου.
Το αποτέλεσμα είναι ένας άλλος μειωμένος πίνακας (4 x 4), ο οποίος υπόκειται στη λειτουργία αναγωγής.
∑d i + ∑d j = 10
| i j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | Μ | 0 | 30 | 0 |
| 3 | 30 | 0 | Μ | 0 | 0 |
| 4 | Μ | 50 | 10 | 40 | 10 |
| 5 | 0 | 10 | 30 | Μ | 0 |
| DJ | 0 | 0 | 0 | 0 | 10 |
Το κάτω όριο του υποσυνόλου (1,4) ισούται με:
H(1,4) = 140 + 10 = 150 ≤ 180
Δεδομένου ότι το κάτω όριο αυτού του υποσυνόλου (1,4) είναι μικρότερο από το υποσύνολο (1*,4*), συμπεριλαμβάνουμε την άκρη (1,4) στη διαδρομή με νέα σύνορα H=150
Βήμα 2.
Προσδιορισμός της ακμής διακλάδωσηςκαι διαιρέστε ολόκληρο το σύνολο των διαδρομών σε σχέση με αυτό το άκρο σε δύο υποσύνολα (i,j) και (i*,j*).
Για το σκοπό αυτό, για όλα τα κελιά του πίνακα με μηδενικά στοιχεία, αντικαθιστούμε τα μηδενικά ένα προς ένα με Μ (άπειρο) και προσδιορίζουμε για αυτά το άθροισμα των σταθερών αναγωγής που προκύπτουν, δίνονται σε παρένθεση.
| i j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | Μ | 0(20) | 30 | 20 |
| 3 | 30 | 0(10) | Μ | 0(30) | 0 |
| 4 | Μ | 40 | 0(30) | 30 | 30 |
| 5 | 0(30) | 10 | 30 | Μ | 10 |
| DJ | 20 | 10 | 0 | 30 | 0 |
d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
Το μεγαλύτερο άθροισμα σταθερών αναγωγής είναι (0 + 30) = 30 για την ακμή (3,5), επομένως, το σύνολο χωρίζεται σε δύο υποσύνολα (3,5) και (3*,5*).
Το κάτω όριο για τους κύκλους Χαμιλτονίου αυτού του υποσυνόλου είναι:
H(3*,5*) = 150 + 30 = 180
Εξαλείφουμε το άκρο (3.5) αντικαθιστώντας το στοιχείο d 35 = 0 με M, μετά από το οποίο πραγματοποιούμε την επόμενη μείωση του πίνακα απόστασης για το προκύπτον υποσύνολο (3*,5*), με αποτέλεσμα να έχουμε μειωμένο πίνακα .
| i j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | Μ | 0 | 30 | 0 |
| 3 | 30 | 0 | Μ | Μ | 0 |
| 4 | Μ | 40 | 0 | 30 | 0 |
| 5 | 0 | 10 | 30 | Μ | 0 |
| DJ | 0 | 0 | 0 | 30 | 30 |
Η συμπερίληψη της ακμής (3.5) πραγματοποιείται με την εξαίρεση όλων των στοιχείων της 3ης σειράς και της 5ης στήλης, στην οποία το στοιχείο d 53 αντικαθίσταται από το M για να εξαλειφθεί ο σχηματισμός ενός μη Χαμιλτονιανού κύκλου.
Ως αποτέλεσμα, λαμβάνουμε έναν άλλο μειωμένο πίνακα (3 x 3), ο οποίος υπόκειται στη λειτουργία αναγωγής.
Το άθροισμα των σταθερών αναγωγής του ανηγμένου πίνακα:
∑d i + ∑d j = 10
Μετά τη λειτουργία μείωσης, ο μειωμένος πίνακας θα μοιάζει με:
| i j | 1 | 2 | 3 | d i |
| 2 | 20 | Μ | 0 | 0 |
| 4 | Μ | 40 | 0 | 0 |
| 5 | 0 | 10 | Μ | 0 |
| DJ | 0 | 10 | 0 | 10 |
Το κάτω όριο του υποσυνόλου (3.5) ισούται με:
H(3,5) = 150 + 10 = 160 ≤ 180
Δεδομένου ότι το κάτω όριο αυτού του υποσυνόλου (3,5) είναι μικρότερο από το υποσύνολο (3*,5*), συμπεριλαμβάνουμε την άκρη (3,5) στη διαδρομή με νέο όριο H = 160
Βήμα #3.
Προσδιορισμός της ακμής διακλάδωσηςκαι διαιρέστε ολόκληρο το σύνολο των διαδρομών σε σχέση με αυτό το άκρο σε δύο υποσύνολα (i,j) και (i*,j*).
Για το σκοπό αυτό, για όλα τα κελιά του πίνακα με μηδενικά στοιχεία, αντικαθιστούμε τα μηδενικά ένα προς ένα με Μ (άπειρο) και προσδιορίζουμε για αυτά το άθροισμα των σταθερών αναγωγής που προκύπτουν, δίνονται σε παρένθεση.
| i j | 1 | 2 | 3 | d i |
| 2 | 20 | Μ | 0(20) | 20 |
| 4 | Μ | 30 | 0(30) | 30 |
| 5 | 0(20) | 0(30) | Μ | 0 |
| DJ | 20 | 30 | 0 | 0 |
d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
Το μεγαλύτερο άθροισμα σταθερών αναγωγής είναι (0 + 30) = 30 για την ακμή (5,2), επομένως, το σύνολο χωρίζεται σε δύο υποσύνολα (5,2) και (5*,2*).
Το κάτω όριο για τους κύκλους Χαμιλτονίου αυτού του υποσυνόλου είναι:
H(5*,2*) = 160 + 30 = 190
Εξαλείφουμε την ακμή (5,2) αντικαθιστώντας το στοιχείο d52 = 0 με M, μετά την οποία πραγματοποιούμε την επόμενη μείωση του πίνακα απόστασης για το προκύπτον υποσύνολο (5*,2*), με αποτέλεσμα να έχουμε μειωμένη μήτρα.
| i j | 1 | 2 | 3 | d i |
| 2 | 20 | Μ | 0 | 0 |
| 4 | Μ | 30 | 0 | 0 |
| 5 | 0 | Μ | Μ | 0 |
| DJ | 0 | 30 | 0 | 30 |
Η συμπερίληψη της ακμής (5.2) πραγματοποιείται με την εξαίρεση όλων των στοιχείων της 5ης σειράς και της 2ης στήλης, στην οποία το στοιχείο d 25 αντικαθίσταται από το M για να εξαλειφθεί ο σχηματισμός ενός μη Χαμιλτονιανού κύκλου.
Ως αποτέλεσμα, λαμβάνουμε έναν άλλο μειωμένο πίνακα (2 x 2), ο οποίος υπόκειται στη λειτουργία αναγωγής.
Το άθροισμα των σταθερών αναγωγής του ανηγμένου πίνακα:
∑d i + ∑d j = 20
Μετά τη λειτουργία μείωσης, ο μειωμένος πίνακας θα μοιάζει με:
| i j | 1 | 3 | d i |
| 2 | 20 | 0 | 0 |
| 4 | Μ | 0 | 0 |
| DJ | 20 | 0 | 20 |
Το κάτω όριο του υποσυνόλου (5,2) ισούται με:
H(5,2) = 160 + 20 = 180 ≤ 190
Δεδομένου ότι το κάτω όριο αυτού του υποσυνόλου (5,2) είναι μικρότερο από το υποσύνολο (5*,2*), συμπεριλαμβάνουμε την άκρη (5,2) στη διαδρομή με νέο όριο H = 180
Σύμφωνα με αυτόν τον πίνακα, συμπεριλαμβάνουμε τις ακμές (2,1) και (4,3) στη διαδρομή Hamiltonian.
Ως αποτέλεσμα, κατά μήκος του διακλαδούμενου δέντρου του κύκλου Hamiltonian, οι άκρες σχηματίζονται:
(1,4), (4,3), (3,5), (5,2), (2,1),
Το μήκος της διαδρομής είναι F(Mk) = 180
Επίλυση του προβλήματος του πλανόδιου πωλητή χρησιμοποιώντας τη μέθοδο διακλάδωσης και δέσμευσης
Ορισμοί
Ένα γράφημα είναι ένα μη κενό πεπερασμένο σύνολο που αποτελείται από δύο υποσύνολα και . Πρώτο υποσύνολο 
(κορυφές) αποτελείται από οποιοδήποτε σύνολο στοιχείων. Το δεύτερο υποσύνολο (τόξα) αποτελείται από διατεταγμένα ζεύγη στοιχείων του πρώτου υποσυνόλου 
. Αν οι κορυφές και 
έτσι ώστε , τότε αυτές είναι γειτονικές κορυφές.
Μια διαδρομή σε ένα γράφημα είναι μια ακολουθία κορυφών 
όχι απαραίτητα ανά ζεύγη διακριτή, όπου για κανένα 
πλησίον 
. Μια διαδρομή ονομάζεται αλυσίδα εάν όλες οι άκρες της είναι ξεχωριστές ανά ζεύγη. Αν τότε η διαδρομή ονομάζεται κλειστή. Ένα κλειστό κύκλωμα ονομάζεται κύκλος.
Διατύπωση του προβλήματος
Ο ταξιδιώτης πωλητής πρέπει να ταξιδέψει n πόλεις. Για να μειώσει το κόστος, θέλει να φτιάξει μια διαδρομή τέτοια που να κάνει ακριβώς μια φορά γύρω από όλες τις πόλεις και να επιστρέψει στην αρχική με ελάχιστο κόστος.
Όσον αφορά τη θεωρία γραφημάτων, το πρόβλημα μπορεί να διατυπωθεί ως εξής. Σειρά nκορυφές και μήτρα ( ντο ij), όπου ντο ij ≥0 – μήκος (ή τιμή) του τόξου ( Εγώ,
ι),
. Κάτω από διαδρομή ταξιδιού πωλητήzας καταλάβουμε τον κύκλο Εγώ 1 ,
Εγώ 2 ,…,
Εγώ n ,
Εγώ 1 βαθμοί 1,2,…, n. Ετσι, Διαδρομήείναι ένα σύνολο τόξων. Αν μεταξύ πόλεων ΕγώΚαι ιδεν υπάρχει μετάβαση, τότε το σύμβολο "άπειρο" τοποθετείται στη μήτρα. Πρέπει να τοποθετηθεί διαγώνια, πράγμα που σημαίνει ότι απαγορεύεται να επιστρέψετε σε σημείο από το οποίο έχετε ήδη περάσει διαδρομή ταξιδιού πωλητή, μήκος διαδρομής μεγάλο(z) ισούται με το άθροισμα των μηκών των τόξων που περιλαμβάνονται στη διαδρομή. Αφήνω Ζ– το σύνολο όλων των πιθανών διαδρομών. Αρχική κορυφή Εγώ 1 – σταθερό. Πρέπει να βρείτε μια διαδρομή z 0 Ζ, τέτοιο που μεγάλο(z 0)= ελάχ μεγάλο(z),
z
Ζ.
Η λύση του προβλήματος
Η κύρια ιδέα της μεθόδου διακλάδωσης και δέσμευσης είναι ότι πρώτα κατασκευάζεται ένα χαμηλότερο όριο φ στα μήκη του συνόλου των διαδρομών Z. Στη συνέχεια το σύνολο των διαδρομών χωρίζεται σε δύο υποσύνολα έτσι ώστε το πρώτο υποσύνολο 
αποτελούνταν από διαδρομές που περιείχαν κάποιο τόξο (i, j) και ένα άλλο υποσύνολο 
δεν περιείχε αυτό το τόξο. Για καθένα από τα υποσύνολα, τα κατώτερα όρια καθορίζονται σύμφωνα με τον ίδιο κανόνα όπως και για το αρχικό σύνολο διαδρομών. Τα κατώτερα όρια που προκύπτουν στα υποσύνολα 
και αποδεικνύεται ότι δεν είναι λιγότερο από το κάτω όριο του συνόλου όλων των διαδρομών, δηλ. φ(Z)≤ φ (), φ(Z) ≤ φ ().
Σύγκριση κάτω ορίων φ () Και φ (), μπορούμε να επιλέξουμε το υποσύνολο διαδρομών που είναι πιο πιθανό να περιέχει μια διαδρομή ελάχιστου μήκους.
Στη συνέχεια, ένα από τα υποσύνολα, ή σύμφωνα με έναν παρόμοιο κανόνα, χωρίζεται σε δύο νέα 
Και 
. Τα κατώτερα όρια βρίσκονται και πάλι για αυτούς φ
(), Και φ
() και τα λοιπά. Η διαδικασία διακλάδωσης συνεχίζεται μέχρι να βρεθεί μια ενιαία διαδρομή. Ονομάζεται πρώτος δίσκος. Μετά κοιτάζουν μέσα από τα σκισμένα κλαδιά. Εάν τα κάτω όριά τους είναι μεγαλύτερα από το μήκος της πρώτης εγγραφής, τότε το πρόβλημα λύνεται. Εάν υπάρχουν εκείνα για τα οποία τα κάτω όρια είναι μικρότερα από το μήκος της πρώτης εγγραφής, τότε το υποσύνολο με το μικρότερο κάτω όριο υποβάλλεται σε περαιτέρω διακλάδωση μέχρι να πειστεί ότι δεν περιέχει το καλύτερο Διαδρομή.
Αν βρεθεί, τότε η ανάλυση των σπασμένων διακλαδώσεων συνεχίζεται ως προς τη νέα τιμή του μήκους διαδρομής. Ονομάζεται δεύτερος δίσκος. Η διαδικασία λύσης τελειώνει όταν αναλυθούν όλα τα υποσύνολα.
Για την πρακτική εφαρμογή της μεθόδου διακλάδωσης και δέσμευσης σε σχέση με το πρόβλημα του περιοδεύοντος πωλητή, θα υποδείξουμε μια τεχνική για τον προσδιορισμό των κατώτερων ορίων των υποσυνόλων και τη διαίρεση του συνόλου των διαδρομών σε υποσύνολα (διακλάδωση).
Για να βρούμε το κάτω όριο, χρησιμοποιούμε την ακόλουθη θεώρηση: εάν προστεθεί ή αφαιρεθεί ένας συγκεκριμένος αριθμός από τα στοιχεία οποιασδήποτε γραμμής του πίνακα του προβλήματος του περιοδεύοντος πωλητή (γραμμή ή στήλη), τότε η βέλτιστη του σχεδίου δεν θα αλλαγή. Το μήκος οποιουδήποτε διαδρομή ταξιδιού πωλητήθα αλλάξει κατά αυτό το ποσό.
Αφαιρέστε από κάθε γραμμή έναν αριθμό ίσο με το ελάχιστο στοιχείο αυτής της γραμμής. Αφαιρέστε από κάθε στήλη έναν αριθμό ίσο με το ελάχιστο στοιχείο αυτής της στήλης. Ο προκύπτων πίνακας ονομάζεται μειωμένος κατά σειρές και στήλες. Το άθροισμα όλων των αριθμών που αφαιρούνται ονομάζεται σταθερά αναγωγής.
Μια σταθερά χύτευσης πρέπει να επιλέγεται ως κατώτερο όριο στο μήκος των διαδρομών.
Διαχωρισμός ενός συνόλου διαδρομών σε υποσύνολα
Για να εντοπίσουμε υποψηφίους για συμπερίληψη στο σύνολο τόξων κατά μήκος των οποίων πραγματοποιείται η διακλάδωση, θεωρούμε στον δεδομένο πίνακα όλα τα στοιχεία ίσο με μηδέν. Ας βρούμε τους βαθμούς Θ ij των μηδενικών στοιχείων αυτού του πίνακα. Ο βαθμός του μηδενικού στοιχείου Θ ij είναι ίσος με το άθροισμα του ελάχιστου στοιχείου της σειράς Εγώκαι το ελάχιστο στοιχείο στη στήλη ι(όταν επιλέγετε αυτά τα ελάχιστα ντο ij – δεν λαμβάνεται υπόψη). Με τη μεγαλύτερη πιθανότητα, η απαιτούμενη διαδρομή ανήκει σε τόξα με μέγιστο βαθμό μηδέν.
Για να λάβετε τον πίνακα πληρωμής των διαδρομών, συμπεριλαμβανομένου του τόξου ( Εγώ, ι) διαγράφουμε τη σειρά στη μήτρα Εγώκαι στήλη ι, και για να αποτρέψουμε το σχηματισμό κύκλου στη διαδρομή, αντικαθιστούμε το στοιχείο που κλείνει την τρέχουσα αλυσίδα στο άπειρο.
Πολλές διαδρομές που δεν περιλαμβάνουν τόξο ( Εγώ, ι) λαμβάνεται με την αντικατάσταση του στοιχείου ντο ij στο άπειρο.
Ένα παράδειγμα επίλυσης του προβλήματος του περιοδεύοντος πωλητή χρησιμοποιώντας τη μέθοδο διακλάδωσης και δέσμευσης
Ένας ταξιδιώτης πωλητής πρέπει να ταξιδέψει 6 πόλεις. Για να μειώσει το κόστος, θέλει να φτιάξει μια διαδρομή τέτοια που να κάνει ακριβώς μια φορά γύρω από όλες τις πόλεις και να επιστρέψει στην αρχική με ελάχιστο κόστος. Πόλη πηγής Α. Το κόστος μετακίνησης μεταξύ πόλεων δίνεται από τον ακόλουθο πίνακα:
Η λύση του προβλήματος
Για διευκόλυνση της παρουσίασης, παντού παρακάτω στον πίνακα πληρωμών θα αντικαταστήσουμε τα ονόματα των πόλεων (A, B, ..., F) με τους αριθμούς των αντίστοιχων γραμμών και στηλών (1, 2, ..., 6).
Ας βρούμε το κάτω όριο στα μήκη του συνόλου όλων των διαδρομών. Ας αφαιρέσουμε από κάθε σειρά έναν αριθμό ίσο με το ελάχιστο στοιχείο αυτής της σειράς, στη συνέχεια αφαιρούμε από κάθε στήλη έναν αριθμό ίσο με το ελάχιστο στοιχείο αυτής της στήλης και έτσι παρουσιάζουμε έναν πίνακα σε γραμμές και στήλες. Ελάχιστα σειρές: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.
Αφού τα αφαιρέσουμε γραμμή προς γραμμή, παίρνουμε:
Ελάχιστα στηλών: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6.
Αφού τα αφαιρέσουμε κατά στήλες, έχουμε τον ακόλουθο πίνακα:
Ας βρούμε το κάτω όριο φ (Ζ) = 15+1+0+16+5+5+5 = 47.
Για να αναγνωρίσουμε υποψηφίους για συμπερίληψη στο σύνολο τόξων κατά μήκος των οποίων πραγματοποιείται η διακλάδωση, βρίσκουμε τους βαθμούς Θ ij των μηδενικών στοιχείων αυτού του πίνακα (το άθροισμα των ελάχιστων στη γραμμή και στη στήλη). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. Ο υψηλότερος βαθμός είναι Θ 14 = 10. Πραγματοποιούμε διακλάδωση κατά μήκος του τόξου (1, 4).
Κάτω όριο για σετ 
παραμένει ίσο με 47. Για όλες τις διαδρομές του σετ
από την πόλη Α δεν μετακινούμαστε στην πόλη Δ. Στον πίνακα αυτό υποδεικνύεται τοποθετώντας το σύμβολο ∞ στο κελί (1, 4). Σε αυτήν την περίπτωση, η έξοδος από την πόλη Α προσθέτει στην εκτίμηση του κάτω ορίου από τουλάχιστοντο μικρότερο στοιχείο της πρώτης σειράς. φ
()
= 47 + 10.
Στη μήτρα που αντιστοιχεί βάζουμε ντο 14 = ∞.
Αφού εκτελέσουμε τη διαδικασία αναγωγής με r 1 = 10, λαμβάνουμε ένα νέο κάτω όριο 57 + 10 = 67.
Στον πίνακα που αντιστοιχεί στο , διαγράφουμε την πρώτη σειρά και την τέταρτη στήλη και βάζουμε ντο 41 = ∞ για να αποφευχθεί η εμφάνιση ενός κύκλου 1→ 4 → 1. Λαμβάνουμε έναν νέο πίνακα πληρωμών ( ντο 1 ij):
Για να μειώσετε, πρέπει να αφαιρέσετε το ελάχιστο στην πρώτη στήλη: h 1 =1. Σε αυτήν την περίπτωση, το κατώτερο όριο θα γίνει ίσο με 47 + 1 = 48. Συγκρίνοντας τα κατώτερα όρια
φ
() = 67 και φ
() = 48, το οποίο είναι πιο πιθανό να περιέχει μια διαδρομή ελάχιστου μήκους.
Ρύζι. 1 Διακλάδωση στο πρώτο βήμα
Στη συνέχεια συνεχίζουμε τη διαδικασία διακλάδωσης. Ας βρούμε τους βαθμούς Θ ij των μηδενικών στοιχείων αυτού του πίνακα Θ 21 =16, Θ 36 = 5, Θ 42 = 2, Θ 56 = 2, Θ 62 = 0, Θ 63 =9, Θ 65 = 2. ο μεγαλύτερος βαθμός είναι Θ 21. Στη συνέχεια, το σετ χωρίζεται κατά μήκος του τόξου (2, 1) σε δύο νέα 
Και 
.
Στον πίνακα για διαγράφουμε τη σειρά 2 και τη στήλη 1. τα τόξα (1, 4) και (2, 1) σχηματίζουν μια συνδεδεμένη διαδρομή (2, 1, 4), ας βάλουμε ντο 42 = ∞ για να αποτρέψετε την εμφάνιση του κύκλου 2→1→ 4 → 2.
Για να μειώσετε, πρέπει να αφαιρέσετε το ελάχιστο στη γραμμή 4: r 4 =2. Σε αυτή την περίπτωση, το κατώτερο όριο θα γίνει ίσο με 48+2 = 50.
Κατώτερο όριο για , που λήφθηκε όπως στο προηγούμενο βήμα διακλάδωσης, ισούται με 48 + 16 = 64. Συγκρίνοντας τα κάτω όρια φ () = 64 και φ () = 50 .
Ρύζι. 2 Διακλάδωση στο δεύτερο βήμα
Ο δεδομένος πίνακας πληρωμής για
Για να μειώσετε, πρέπει να αφαιρέσετε το ελάχιστο στη γραμμή 3: r 3 =5. Σε αυτήν την περίπτωση, το κατώτερο όριο θα γίνει ίσο με 50 + 5 = 55. Επιλέγουμε ένα υποσύνολο διαδρομών για περαιτέρω κατάτμηση.
Ρύζι. 3 Διακλάδωση στο τρίτο βήμα
Ο δεδομένος πίνακας πληρωμής για
|
0 Cheat sheet >> Λογιστική και έλεγχος Δραστηριότητες, επιρροή, συμμετοχή σε απόφαση καθήκοντα. ΣΕ διαφορετικές καταστάσειςζωή... Ιδιαίτερη καθήκονταειδικός μαθηματικός προγραμματισμός καθήκονταμαθηματικός προγραμματισμός. ΕργοΟ περιοδεύων πωλητής.Μέθοδος κλαδια δεντρουΚαι σύνορα. ΕργοΟ περιοδεύων πωλητήςΑς είναι... |
(5x5) (Μετράει για 4 προβλήματα υπό όρους) χρόνος για τη συμπλήρωση 2 ζευγαριών) (Παρουσίαση ΤΑΞΙΔΕΥΟΝΤΑΣ ΠΩΛΗΤΗΣ) Το πιο δύσκολο πρόβλημα στην επιχειρησιακή έρευνα
Χρησιμοποιώντας τη μέθοδο διακλάδωσης και δέσμευσης, πρέπει να βρείτε τη συντομότερη διαδρομή για να παρακάμψετε 5 πόλεις με επιστροφή στην αρχική, ΠΟΥ ΚΑΘΕ ΠΟΛΗ ΕΠΙΣΚΕΦΤΕΙΤΑΙ ΑΚΡΙΒΩΣ 1 φορά (ο πίνακας δείχνει τις τιμές για ταξίδια από την "αριστερή" πόλη προς την "ανώτερος").
Διακλάδωση και Δεσμευμένη Λύση
Η διαδικασία τελειώνει εν μέρει μετά την επιλογή k-2 άκρων, όπου k είναι ο συνολικός αριθμός κορυφών. Σε ένα πρόβλημα 2x2, η λύση είναι μοναδική, οδηγεί (συνήθως) σε διόρθωση του άνω ορίου. Εάν όλα τα (άλλα) κάτω όρια είναι χειρότερα, η απάντηση λαμβάνεται. Σε ένα παράδειγμα όπως αυτό που δίνεται σε αυτήν την εργασία, αυτή η κατάσταση εμφανίζεται συνήθως, αλλά σε ένα μεγαλύτερο και πιο σύνθετο γράφημα (κατά τη δημιουργία ενός καθολικού αλγόριθμου), είναι απαραίτητο να περιγραφούν περαιτέρω ενέργειες. Εάν δεν εξακολουθούν να είναι όλα τα κάτω όρια χειρότερα από το προσαρμοσμένο άνω όριο, τότε τα σωζόμενα μη τετριμμένα σύνολα θα πρέπει να διακλαδιστούν έως ότου εξαφανιστούν λόγω του υψηλού, δηλ. κακή χαμηλότερη εκτίμηση, ή (που είναι σπάνιο) πριν ληφθεί μια νέα ανώτερη εκτίμηση - νέα λύση, ανώτερη σε ποιότητα από την προηγούμενη. Η διαδικασία συνεχίζεται έως ότου η προκύπτουσα λύση παραμένει αδιαμφισβήτητη.
Βήμα Νο. 0 Υπολογίζουμε τον κύκλο 1-2-3-4-5-1 - αυτή είναι η πρώτη προσέγγιση της ανώτερης εκτίμησης. Επιπλέον, εάν σε οποιοδήποτε κλάδο του διακλαδούμενου δέντρου η χαμηλότερη εκτίμηση του υποσυνόλου των λύσεων αποδειχθεί υψηλότερη από την ανώτερη, αυτός ο κλάδος «σβήνει», επειδή όλες οι λύσεις της είναι χειρότερες από τις υπάρχουσες.
Βήμα Νο. 1α) Γράψτε τις σταθερές αναγωγής γραμμή προς γραμμή. Αυτοί είναι οι ελάχιστοι αριθμοί στις γραμμές. Πρέπει να αφαιρεθούν από τα στοιχεία των γραμμών τους (τουλάχιστον ένα μηδέν θα εμφανίζεται σε κάθε γραμμή).
Βήμα Νο. 1β) Στον πίνακα που μόλις λήφθηκε στο βήμα 1α) (με μηδενικά στις σειρές), εκτελέστε ακριβώς την ίδια λειτουργία κατά μήκος των στηλών - αναζητήστε στήλες όπου το ελάχιστο e είναι 0 και αφαιρέστε το. Στη μορφή αυτοδιαγνωστικού ελέγχου, βεβαιωθείτε ότι υπάρχει τώρα τουλάχιστον ένα μηδέν σε κάθε στήλη και κάθε γραμμή του πίνακα ναύλων.
Βήμα Νο. 1γ) Υπολογίζουμε το άθροισμα των σταθερών αναγωγής που λαμβάνονται στα βήματα α) και β). Προφανώς, καμία διαδρομή δεν μπορεί να κοστίσει λιγότερο - επομένως αυτή είναι μια χαμηλότερη εκτίμηση. Στη συνέχεια θα αυξήσουμε αυτήν την εκτίμηση κατά το ποσό 
Και 
(θα περιγράψουμε αυτές τις ποσότητες παρακάτω), όπου 
- ένα ζεύγος ευρετηρίων της ακμής κατά μήκος της οποίας επιλέγεται να διακλαδωθεί.
Ας περιγράψουμε πώς θα συμβεί η διακλάδωση: επιλέγουμε την άκρη i, j (ικανοποιώντας τις απαιτήσεις της επόμενης παραγράφου) το σύνολο των διαδρομών Hamiltonian μπορεί να θεωρηθεί ως ένα συνδυαστικά μεγάλο σύνολο μοναδικών «σφαιριδίων» που αποτελείται από συνδέσμους όπως το St. Πετρούπολη-Μόσχα, Μόσχα-Οδησσός, Οδησσό-Βελιγράδι κ.λπ. Ας υιοθετήσουμε μια μέθοδο για να χωρίσουμε ολόκληρο το σύνολο των κλειστών μονοπατιών σε εκείνα όπου υπάρχει δρόμος Οδησσού-Βελιγραδίου και σε εκείνα όπου δεν υπάρχει (το πρώτο σύνολο είναι μικρότερο από το δεύτερο).
Θεωρητικά, είναι δυνατή η διακλάδωση κατά μήκος οποιασδήποτε άκρης, αλλά το καθήκον μας είναι να διασφαλίσουμε ότι στο ένα σύνολο η χαμηλότερη εκτίμηση της τιμής της διαδρομής δεν αλλάζει και από την άλλη αυξάνεται όσο το δυνατόν περισσότερο - αυτό μπορεί να συμβάλει στην Το γεγονός ότι στις περισσότερες περιπτώσεις μια συνδυαστική αναζήτηση, μιλώντας γενικά, ενός εκθετικού αλγορίθμου για την επίλυση της NP ολοκληρωμένης εργασίας δεν θα είναι πολύ μεγάλη.
Για να το κάνετε αυτό: Βήμα Νο. 2. Υπολογίζουμε το κόστος διέλευσης για κάθε μηδενικό στοιχείο (αν μετατραπεί σε άπειρο ∞) 
- το ποσό κατά το οποίο αυξάνονται οι σταθερές αναγωγής της αντίστοιχης γραμμής και στήλης.
Χωρίζουμε το τρέχον σύνολο λύσεων σε δύο:
Εξετάστε τη μήτρα του κόστους ταξιδιού από την "αριστερή" πόλη στην "επάνω"
Η αρχική συνολική εκτίμηση Zupper=10+10+20+15+10 = 65 λαμβάνεται μέσω του κύκλου. (οι αντίστοιχες άκρες κυκλώνονται σε τετράγωνα στο σχήμα - ένα στην κάτω αριστερή γωνία, τα υπόλοιπα πάνω από τη διαγώνιο).
Ας αρχίσουμε να σχεδιάζουμε ένα δέντρο που διακλαδίζεται
Στον προκύπτοντα πίνακα
θα υπολογίσουμε το πρόσθετο κόστος μιας «παράκαμψης» για κάθε άτομο μηδέν (δηλαδή πόσο θα αυξηθεί το άθροισμα των σταθερών μείωσης αν πάψει να υπάρχει ο δρόμος (η τιμή του ναύλου θα αντικατασταθεί από το άπειρο)) και επιλέξτε εκείνο το «μηδέν» του οποίου το κόστος παράκαμψης είναι το μέγιστο.
(1,2)=0
(1,5)=1
(2,1)=0
(2,3)=5 (Ανώτατο όριο )
(3,1)=0
(3,4)=2
(4,2)=4
(5,2)=2
Άρα, το μέγιστο κόστος μιας παράκαμψης παρατηρείται όταν η άκρη είναι απενεργοποιημένη (2,3)=5.
Με τον αλγόριθμό μας, είναι φυσικό να χωρίζουμε όλους τους κύκλους παράκαμψης σε αυτούς που περιέχουν την άκρη (2,3) και σε αυτούς που δεν την περιέχουν. Η χαμηλότερη εκτίμηση του κόστους της πρώτης ομάδας κύκλων (θα το υπολογίσουμε αργότερα) πιθανότατα δεν θα αλλάξει, η χαμηλότερη εκτίμηση των κύκλων που δεν περιλαμβάνουν το (2,3) αυξάνεται κατά το ποσό (2,3)=5.
Επί ξεχωριστή σελίδαΑρχίζουμε να σχεδιάζουμε το δέντρο που διακλαδίζεται.
Επί αρχικό στάδιοπεριέχει το σύνολο όλων των κύκλων, το οποίο χωρίζεται σε ένα σύνολο που περιέχει (2,3) (είναι λιγότεροι από αυτούς) στα αριστερά και δεν περιέχει (2,3) στα δεξιά.
Το κάτω όριο του (μεγαλύτερου) δεξιού συνόλου προκύπτει από το άθροισμα του ορίου της προηγούμενης κορυφής Z ελάχ=58 και(2,3)=5:Z ελάχ =58+5=63.
Στο αριστερό σετ, η άκρη (2,3) (σχετικά μιλώντας, η διαδρομή Αγία Πετρούπολη - Μόσχα) είναι υποχρεωτική - συνεπώς, δεν έχουμε πλέον επιλογή για το πού θα πάμε από την πόλη 2 (διαγράφουμε τη γραμμή 2) και πώς για να φτάσουμε στην πόλη Νο 3 (διαγράφουμε τη στήλη).
Το τελικό δέντρο κλάδων:
Τελική μέθοδος.
Το αποτέλεσμα είναι ένας πίνακας 2x2.
Μικρό παράδειγμα.
Τέλος, ας δούμε έναν πίνακα 3x3.
Τότε το άνω όριο στα μήκη όλων των διαδρομών είναι Z max = 4+9+8 = 21
Έτσι, η χαμηλότερη εκτίμηση του Z είναι χαμηλότερη = 16 (6+3+4+3).
Υπολογίζουμε τις σταθερές παράκαμψης:
Ας συνδυάσουμε τις πόλεις 2 και 1 στον αριστερό κλάδο, στον δεξιό κλάδο η χαμηλότερη εκτίμηση κόστους θα αυξηθεί από 16 σε 5 σε 21.
παίρνουμε τη μήτρα
Ας απαγορεύσουμε βραχυκύκλωμα- να αποφύγω 
και μειώστε τη μήτρα
Στον αριστερό κλάδο ΔZ_=4, νέα εκτίμηση της αντικειμενικής συνάρτησης Z_=16+ ΔZ_=16+4=20.
Επιλέχθηκε η άκρη
Έφυγαν τα πλευρά 
.
Χρησιμοποιώντας την αρχή του ντόμινο, επαναφέρουμε τον ελάχιστο κύκλο ξεκινώντας από την άκρη ξεκινώντας από το 1, με αυτήν την άκρη 
, σαν να περπατά σαν «τρένο».
Αυτό είναι ένα συγκεκριμένο μονοπάτι μήκους 20 στο οποίο σημείο παίρνουμε ένα νέο άνω όριο, το οποίο είναι καλύτερο από το παλιό άνω όριο του 21.
Στο δέντρο διακλάδωσης των συνόλων απαρίθμησης, ο κλάδος με την υψηλότερη χαμηλότερη εκτίμηση 21 (δεξιός κλάδος) εξαφανίζεται.
Στην περίπτωσή μας, η επιλογή που προέκυψε αποδείχθηκε καλύτερη από όλες τις χαμηλότερες εκτιμήσεις για άλλους κλάδους.
Απάντηση: 
.
Εξέταση
Παρουσίαση ΤΑΞΙΔΕΥΟΝΤΑΣ ΠΩΛΗΤΗΣ.
Η εργασία ελέγχεται από τον δάσκαλο σχετικά με το σχέδιο του δέντρου που διακλαδίζεται. Για να παρουσιάσει τις πληρέστερες πληροφορίες που είναι απαραίτητες για επαλήθευση, εμφανίστε τις χαμηλότερες εκτιμήσεις στις κορυφές του δέντρου λειτουργίες στόχου, όλα τα θ (αύξηση του αθροίσματος των σταθερών μείωσης σε μια δεξιά στροφή), όλα τα ΔZ (αύξηση του αθροίσματος των σταθερών μείωσης σε μια αριστερή στροφή) πρέπει να εμφανίζονται στις άκρες του δέντρου. Κατά τη διάρκεια μιας αριστερής στροφής, επιλέγεται ένα υποχρεωτικό άκρο (σημειώνεται στο δέντρο κλαδιών) και προστίθεται ένα απαγορευμένο άκρο. Για να εξηγηθεί η επιλογή του, δίπλα στο δέντρο που διακλαδίζεται στο κατάλληλο επίπεδο, θα πρέπει να απεικονιστεί μια αλυσίδα στην οποία η απαγορευμένη άκρη, μαζί με τις προηγουμένως επιλεγμένες (συμπεριλαμβανομένης της τρέχουσας επιλεγμένης), δημιουργεί έναν κύκλο που δεν διέρχεται από όλα τα άκρες (το λεγόμενο «βραχυκύκλωμα» του κύκλου).
Η απάντηση δίνει μια αλυσίδα από άκρες της μορφής (1,k)(k,l)(l,m)..(r,1)(ανάλογα με το μέγεθος του προβλήματος), το κόστος της διαδρομής αποτελείται από αρχική χαμηλότερη εκτίμηση και οι προσαυξήσεις της ΔZ (αν υπήρχαν μόνο CROSSOUTS - αριστερές στροφές) και - κάτι που συμβαίνει πολύ σπάνια - ΔZ και θ, εάν, ΕΠΙΠΛΕΟΝ στις αριστερές στροφές, υπήρχαν μία ή περισσότερες δεξιές στροφές. Ελέγξτε το κόστος της ΛΗΨΗΜΕΝΗΣ λύσης χρησιμοποιώντας τον αρχικό πίνακα, εξηγήστε τους λόγους της απόκλισης - εάν υπάρχουν (δεν πρέπει να υπάρχουν αναντιστοιχίες).
Γεια σου, Χαμπρ! Κατά την εφαρμογή διαφόρων αλγορίθμων για την εύρεση του χαμηλού κόστους κύκλου Hamiltonian, συνάντησα μια δημοσίευση που προσφέρει τη δική μου έκδοση. Αφού το δοκίμασα, πήρα τη λάθος απάντηση:
Περαιτέρω αναζητήσεις στο Διαδίκτυο δεν έφεραν το αναμενόμενο αποτέλεσμα: είτε μια θεωρητική περιγραφή που ήταν δύσκολη για τους μη μαθηματικούς, είτε κατανοητή, αλλά με λάθη.
Κάτω από την περικοπή θα βρείτε έναν διορθωμένο αλγόριθμο και μια ηλεκτρονική αριθμομηχανή.
Η ίδια η μέθοδος, που δημοσιεύτηκε από τους Little, Murthy, Sweeney, Carell το 1963, είναι εφαρμόσιμη σε πολλά προβλήματα NP-πλήρης και είναι πολύ θεωρητικό υλικό που, χωρίς καλή γνώση Στα Αγγλικάκαι τα μαθηματικά δεν μπορούν να εφαρμοστούν αμέσως στο πρόβλημα του πλανόδιου πωλητή μας.
Εν συντομία για τη μέθοδο - αυτή είναι μια πλήρης αναζήτηση όλων πιθανές επιλογέςμε την εξάλειψη σαφώς μη βέλτιστων λύσεων.
Διορθωμένος αλγόριθμος για την εύρεση μιας πραγματικά ελάχιστης διαδρομής
Ο αλγόριθμος αποτελείται από δύο στάδια:
Πρώτο στάδιο
Μείωση του πίνακα κόστους και υπολογισμός της χαμηλότερης εκτίμησης του κόστους διαδρομής r.
1. Υπολογίστε το μικρότερο στοιχείο σε κάθε σειρά (σταθερά για τη σειρά)2. Προχωράμε σε έναν νέο πίνακα κόστους, αφαιρώντας τη σταθερά μείωσης του από κάθε σειρά
3. Υπολογίστε το μικρότερο στοιχείο σε κάθε στήλη (σταθερά εξαναγκασμού για τη στήλη)
4. Προχωράμε σε έναν νέο πίνακα κόστους, αφαιρώντας τη σταθερά αναγωγής του από κάθε στήλη.
Ως αποτέλεσμα, έχουμε έναν πίνακα κόστους στον οποίο κάθε γραμμή και κάθε στήλη έχει τουλάχιστον ένα μηδενικό στοιχείο.
5. Υπολογίστε το όριο στο σε αυτό το στάδιοως το άθροισμα των σταθερών χύτευσης για στήλες και σειρές ( αυτό το σύνοροθα είναι το κόστος κάτω από το οποίο είναι αδύνατο να κατασκευαστεί η επιθυμητή διαδρομή)
Δεύτερο (κύριο) στάδιο
1. Υπολογισμός της ποινής για μη χρήση για κάθε μηδενικό στοιχείο του δεδομένου πίνακα κόστους.Η ποινή για τη μη χρήση ενός στοιχείου με δείκτη (h,k) στον πίνακα σημαίνει ότι αυτή η άκρη δεν περιλαμβάνεται στη διαδρομή μας, πράγμα που σημαίνει ότι το ελάχιστο κόστος της «μη χρήσης» αυτής της ακμής είναι ίσο με το άθροισμα των ελάχιστων στοιχείων στο σειρά h και στήλη k.
Α) Αναζητούμε όλα τα μηδενικά στοιχεία στον δεδομένο πίνακα
β) Για καθένα από αυτά υπολογίζουμε την ποινή του για μη χρήση.
γ) Επιλέξτε το στοιχείο που αντιστοιχεί στη μέγιστη ποινή (οποιοδήποτε, εάν υπάρχουν πολλά από αυτά)
2. Τώρα χωρίζουμε το σετ μας S σε σετ - αυτά που περιέχουν την άκρη με τη μέγιστη ποινή (S w) και αυτά που δεν περιέχουν αυτήν την άκρη (S w/o).
3. Υπολογισμός εκτιμήσεων κόστους για διαδρομές που περιλαμβάνονται σε καθένα από αυτά τα σύνολα.
α) Για το σύνολο S w/o όλα είναι απλά: αφού δεν παίρνουμε την αντίστοιχη άκρη με τη μέγιστη ποινή (h,k), τότε η εκτίμηση κόστους για αυτό είναι ίση με την εκτίμηση κόστους του συνόλου S + η ποινή για μη χρήση της ακμής (h,k)
β) Κατά τον υπολογισμό του κόστους για το σύνολο S w, λαμβάνουμε υπόψη ότι εφόσον η άκρη (h,k) περιλαμβάνεται στη διαδρομή, σημαίνει ότι η άκρη (k,h) δεν μπορεί να συμπεριληφθεί στη διαδρομή, επομένως στην τον πίνακα κόστους γράφουμε c(k,h) = άπειρο, και αφού έχουμε «απομείνει ήδη» από το σημείο h, και έχουμε «ήδη φτάσει» από το σημείο k, τότε ούτε μία ακμή δεν φεύγει από την h ούτε μία ακμή δεν φτάνει στο k δεν μπορεί πλέον να χρησιμοποιηθεί, επομένως διαγράφουμε από τον πίνακα κόστους, τη γραμμή h και τη στήλη k. Μετά από αυτό, μειώνουμε τον πίνακα και, στη συνέχεια, η εκτίμηση κόστους για S w είναι ίση με το άθροισμα της εκτίμησης κόστους για S και r(h,k), όπου r(h,k) είναι το άθροισμα των σταθερών μείωσης για τον τροποποιημένο πίνακα κόστους.
4. Από Ολοιαπό μη κατανεμημένα σύνολα, επιλέγεται αυτό με τη χαμηλότερη βαθμολογία.
Συνεχίζουμε με αυτόν τον τρόπο έως ότου απομείνει μία μη διασταυρωμένη γραμμή και μία στήλη χωρίς διασταύρωση στον πίνακα κόστους.
Μικρή βελτιστοποίηση - προσθήκη ευρετικών
Ναι, αλήθεια, γιατί δεν εισάγουμε την ευρετική; Πράγματι, στον αλγόριθμο του κλαδιού και του δεσμού, στην πραγματικότητα χτίζουμε ένα δέντρο, στους κόμβους του οποίου αποφασίζουμε να πάρουμε την άκρη (h,k) ή όχι, και να κρεμάσουμε δύο παιδιά - Sw(h,k) και Sw/o( η, κ). Αλλά η καλύτερη επιλογήγια την επόμενη επανάληψη επιλέγουμε μόνο με εκτίμηση. Ας επιλέξουμε λοιπόν το καλύτερο όχι μόνο από άποψη βαθμολογίας, αλλά και από άποψη βάθους στο δέντρο, γιατί... Όσο πιο βαθύ είναι το επιλεγμένο στοιχείο, τόσο πιο κοντά βρίσκεται στο τέλος της μέτρησης. Έτσι μπορούμε επιτέλους να περιμένουμε μια απάντηση.
Τώρα, στην πραγματικότητα, για τα λάθη σε αυτή τη δημοσίευση
Υπήρχε μόνο ένα λάθος - θα πρέπει να επιλέξετε για την κατάτμηση του συνόλου με το ελάχιστο όριο όλων πιθανούς τρόπους, και όχι από τα δύο παιδιά που αποκτήθηκαν ως αποτέλεσμα του τελευταίου χωρισμού.Απόδειξη
Ας επιστρέψουμε στην εικόνα στην αρχή της ανάρτησης:
Και εδώ είναι η λύση με τον διορθωμένο αλγόριθμο:
Απάντηση: διαδρομή:3=>4=>2=>1=>5=>3 μήκος: 41
Όπως μπορείτε να δείτε, η συμπερίληψη του άκρου 5:2 στη λύση θα ήταν λάθος. Q.E.D
Γράφημα συγκρίνοντας τη μέθοδο διακλάδωσης και δέσμευσης και τον χρόνο που δαπανήθηκε για τυχαίος πίνακαςαπό 5x5 έως 10x10: 
Γράφημα του μέγιστου και του ελάχιστου χρόνου που δαπανάται για πίνακες από 5x5 έως 66x66. 
Δοκιμάστε με λεπτομερής λύσηΜπορώ
Γειά σου! Κατά την εφαρμογή διαφόρων αλγορίθμων για την εύρεση του χαμηλού κόστους κύκλου Hamiltonian, συνάντησα μια δημοσίευση που προσφέρει τη δική μου έκδοση. Αφού το δοκίμασα, πήρα τη λάθος απάντηση:
Περαιτέρω αναζητήσεις στο Διαδίκτυο δεν έφεραν το αναμενόμενο αποτέλεσμα: είτε μια θεωρητική περιγραφή που ήταν δύσκολη για τους μη μαθηματικούς, είτε κατανοητή, αλλά με λάθη.
Κάτω από την περικοπή θα βρείτε έναν διορθωμένο αλγόριθμο και μια ηλεκτρονική αριθμομηχανή.
Η ίδια η μέθοδος, που δημοσιεύτηκε από τους Little, Murthy, Sweeney, Carel το 1963, είναι εφαρμόσιμη σε πολλά προβλήματα NP-πλήρης και είναι ένα πολύ θεωρητικό υλικό που, χωρίς καλή γνώση αγγλικών και μαθηματικών, δεν μπορεί να εφαρμοστεί αμέσως στο πρόβλημα του ταξιδιώτη πωλητή. .
Εν συντομία για τη μέθοδο - είναι μια πλήρης αναζήτηση όλων των πιθανών επιλογών με την εξάλειψη σαφώς μη βέλτιστων λύσεων.
Διορθωμένος αλγόριθμος για την εύρεση μιας πραγματικά ελάχιστης διαδρομής
Ο αλγόριθμος αποτελείται από δύο στάδια:
Πρώτο στάδιο
Μείωση του πίνακα κόστους και υπολογισμός της χαμηλότερης εκτίμησης του κόστους διαδρομής r.
1. Υπολογίστε το μικρότερο στοιχείο σε κάθε σειρά (σταθερά για τη σειρά)
2. Προχωράμε σε έναν νέο πίνακα κόστους, αφαιρώντας τη σταθερά μείωσης του από κάθε σειρά
3. Υπολογίστε το μικρότερο στοιχείο σε κάθε στήλη (σταθερά εξαναγκασμού για τη στήλη)
4. Προχωράμε σε έναν νέο πίνακα κόστους, αφαιρώντας τη σταθερά αναγωγής του από κάθε στήλη.
Ως αποτέλεσμα, έχουμε έναν πίνακα κόστους στον οποίο κάθε γραμμή και κάθε στήλη έχει τουλάχιστον ένα μηδενικό στοιχείο.
5. Υπολογίζουμε το όριο σε αυτό το στάδιο ως το άθροισμα των σταθερών μείωσης για στήλες και σειρές (αυτό το όριο θα είναι το κόστος κάτω από το οποίο είναι αδύνατο να κατασκευαστεί η απαιτούμενη διαδρομή)
Δεύτερο (κύριο) στάδιο
1. Υπολογισμός της ποινής για μη χρήση για κάθε μηδενικό στοιχείο του δεδομένου πίνακα κόστους.
Η ποινή για τη μη χρήση ενός στοιχείου με δείκτη (h,k) στον πίνακα σημαίνει ότι αυτή η άκρη δεν περιλαμβάνεται στη διαδρομή μας, πράγμα που σημαίνει ότι το ελάχιστο κόστος της «μη χρήσης» αυτής της ακμής είναι ίσο με το άθροισμα των ελάχιστων στοιχείων στο σειρά h και στήλη k.
α) Αναζητούμε όλα τα μηδενικά στοιχεία στον δεδομένο πίνακα
β) Για καθένα από αυτά υπολογίζουμε την ποινή του για μη χρήση.
γ) Επιλέξτε στοιχεία που αντιστοιχούν στη μέγιστη ποινή
2. Τώρα χωρίζουμε το σύνολο μας S σε σύνολα - που περιέχουν την άκρη με τη μέγιστη ποινή (S w i) και δεν περιέχουν αυτές τις ακμές (S w i /o).
3. Υπολογισμός εκτιμήσεων κόστους για διαδρομές που περιλαμβάνονται σε καθένα από αυτά τα σύνολα.
α) Για σύνολα S w i /o όλα είναι απλά: αφού δεν παίρνουμε την αντίστοιχη ακμή με τη μέγιστη ποινή (hi ,k i), τότε για αυτό η εκτίμηση κόστους είναι ίση με την εκτίμηση κόστους του συνόλου S + ποινή για όχι χρησιμοποιώντας την άκρη (γεια, k i)
β) Κατά τον υπολογισμό του κόστους για το σύνολο S w i, λαμβάνουμε υπόψη ότι εφόσον η άκρη (hi i,k i) περιλαμβάνεται στη διαδρομή, σημαίνει ότι η άκρη (k i,hi) δεν μπορεί να συμπεριληφθεί στη διαδρομή, επομένως στον πίνακα κόστους γράφουμε c(k i,hi) = άπειρο, και αφού έχουμε «απομείνει ήδη» από το σημείο hi, και έχουμε «ήδη έφτασε» από το σημείο κι, τότε ούτε μία άκρη δεν αφήνει hi, ούτε μία Η άκρη που φτάνει στο ki, μπορεί ήδη να χρησιμοποιηθεί, επομένως διαγράφουμε από τον πίνακα κόστους, τη σειρά h i και τη στήλη k i. Μετά από αυτό, δίνουμε τον πίνακα και, στη συνέχεια, η εκτίμηση κόστους για S w είναι ίση με το άθροισμα της εκτίμησης κόστους για S και r(hi,k i), όπου r(hi,k i) είναι το άθροισμα των σταθερών μείωσης για τον τροποποιημένο πίνακα κόστους.
4. Από όλα τα μη κατανεμημένα σετ επιλέγεται αυτό με τη χαμηλότερη βαθμολογία.
Συνεχίζουμε με αυτόν τον τρόπο έως ότου απομείνει μία μη διασταυρωμένη γραμμή και μία στήλη χωρίς διασταύρωση στον πίνακα κόστους.
Μικρή βελτιστοποίηση - προσθήκη ευρετικών
Ναι, αλήθεια, γιατί δεν εισάγουμε την ευρετική; Πράγματι, στον αλγόριθμο του κλαδιού και του δεσμού, στην πραγματικότητα χτίζουμε ένα δέντρο, στους κόμβους του οποίου αποφασίζουμε να πάρουμε την άκρη (hi,k i) ή όχι και να κρεμάσουμε δύο ή περισσότερα παιδιά - Sw(hi,k i) και Sw/ o (γεια, κ i). Αλλά επιλέγουμε την καλύτερη επιλογή για την επόμενη επανάληψη μόνο βάσει αξιολόγησης. Ας επιλέξουμε λοιπόν το καλύτερο όχι μόνο από άποψη βαθμολογίας, αλλά και από άποψη βάθους στο δέντρο, γιατί... Όσο πιο βαθύ είναι το επιλεγμένο στοιχείο, τόσο πιο κοντά βρίσκεται στο τέλος της μέτρησης. Έτσι μπορούμε επιτέλους να περιμένουμε μια απάντηση.
Τώρα, στην πραγματικότητα, για τα λάθη σε αυτή τη δημοσίευση
Αυτά τα σφάλματα έχουν έναν λόγο - αγνοώντας την πιθανότητα εμφάνισης πολλών μηδενικών στοιχείων με μέγιστη ποινή. Σε αυτή την περίπτωση, είναι απαραίτητο να χωριστείτε όχι σε δύο υποσύνολα, αλλά σε μεγάλη ποσότητα(2n). Θα πρέπει επίσης να επιλέξετε για την κατάτμηση του συνόλου με το ελάχιστο όριο από όλες τις πιθανές διαδρομές και όχι από τα δύο παιδιά που προέκυψαν ως αποτέλεσμα της τελευταίας κατάτμησης.
Απόδειξη
Ας επιστρέψουμε στην εικόνα στην αρχή της ανάρτησης:
Και εδώ είναι η λύση με τον διορθωμένο αλγόριθμο.
