Backtracking - τί είναι και πως χρησιμοποιείται;

[nikolasmer]

Μπορεί κάποιος/α να μου εξηγήσει τι είναι αυτό το ρημάδι το backtracking με απλά λόγια; Πως γλιτώνω περιττούς υπολογισμούς με ένα παράδειγμα χωρίς απαραίτητα αναδρομικές συναρτήσεις και με χρήση αλγοριθμικών δομών του μάθήματος της Πληροφορικής;

[Foto]

Για τη κατανόηση του backtracking, το βασικό στοιχείο είναι η ουρά, Queue.
Ο πιο εύκολος τρόπος κατανόησης είναι να πάρεις ένα χαρτί και να σχεδιάσεις ένα λαβύρινθο. Κάθε φορά που θα πηγαίνεις σε ένα σημείο στο λαβύρινθο θα σημειώνεις ότι πέρασες από εκεί και θα ακολουθείς μια διαδρομή, ενώ αν υπάρχουν άλλες απο το ίδιο σημείο θα τις βαλεις σε μια ουρά. Η ουρά είναι πολύ απλή για να φτιαχτεί στο χαρτί, απλά προσθέτεις στο τέλος της το σημείο εισόδου στο λαβύρινθο. Όταν φτάνεις σε αδιέξοδο, παίρνεις το πρώτο στοιχείο, διεύθυνση, το διαγράφεις από την ουρά, και παίζει ο αλγόριθμος από εκεί.

Αν θες να το δυσκολέψεις το πράγμα θα έβαζες όλη τη διαδρομή για επιστροφή, με την έννοια ότι δίνουμε εντολές σε ένα ρομπότ να κινηθεί. Ενώ αυτό που περιέγραψα πριν κάνει την μετάθεση άμεση, γιατί στην ουσία παίζουμε τον ίδιο αλγόριθμο με άλλα σύνολα παραμέτρων, που έχουν προκύψει από προηγούμενη εκτέλεση του ίδιου αγοριθμου με διαφορετικό σύνολο παραμέτρων. Στην ουσία ο αλγόριθμος ή βρίσκει το τέλος και δηλώνει τερματισμό, πχ αδειάζει την ουρά, ή προσθέτει στην ουρά, για να τρέξει μια ή δυο φορές ακόμα (ακριβώς επειδή μια εκτέλεση του αλγόριθμου μπορεί να προκαλέσει πολλαπλές εκτελέσειςτου ίδιου δεν μπορούμε να γλιτώσουμε με ένα εξ αρχής προκαθορισμενο σύνολο βημάτων).
Δεν υπάρχουν μικρά προγράμματα σε ΓΛΩΣΣΑ για να το δείξω, επειδή πρέπει να έχουμε κανονίσει δομές για την αναπαράσταση του λαβύρινθου, της ουράς και να αρχικοποιήσουνε τον λαβύρινθο! Πολύ δουλειά....

[gpapargi]

Το πιο αρχέγονο backtracking που μπορώ να σκεφτώ είναι αυτό που έγινε στο λαβύρινθο του Μίνωα χρησιμοποιώντας το μίτο της Αριάδνης. Μπαίνεις στο λαβύρινθο κρατώντας το μίτο. Σε κάθε διασταύρωση διαλέγεις ένα δρόμο. Αν βρεθείς σε αδιέξοδο, ακολουθείς το μίτο και βαδίζεις πάνω στα ίδια σου τα βήματα ανάποδα. Αυτό είναι κυριολεκτικά το backtracking... ανάποδη ιχνηλάτιση. Μόλις φτάσεις στην προηγούμενη διασταύρωση ακολουθείς άλλη διαδρομή μαρκάροντας αυτό που σε έστειλε σε αδιέξοδο ώστε να μην την ξανακολουθήσεις. ΑΝ θέλεις να προσομοιώσεις ακριβώς τη διαδικασία, για κάθε κόμβο που πατάς, αποθηκεύεις τον προηγούμενο ώστε να μπορείς να γυρίσεις πίσω (αυτή είναι η προγραμματιστικη εκδοχή του μίτου).
Αν θέλεις μόνο την τελική διαδρομή μπορείς να μην πας ένα ένα τα βήματα ανάποδα, αλλά να "τηλεμεταφερθείς" στην προηγούμενη διασταύρωση και να συνεχίσεις από εκεί. ΑΥτό υλοποιείται με στοίβα (αφού θέλεις να πας στην αμέσως προηγούμενη διασταύρωση και όχι στην αρχική). Δηλαδή σε κάθε διασταύρωση παίρνεις μια διαδρομή και βάζεις τις άλλες σε στοίβα.
Η αναδρομή χρησιμοποιεί στοίβα.

[Foto]

Η αναδρομη μπορεί να φαντάζει στο μυαλό σαν LIFO, στοίβα, αλλά αυτό έχει να κάνει μόνο όταν υπάρχει μια και μόνο κλήση μιας διαδικασίας.
Στο backtracking η κλήση της βασικής διαδικασίας μπορεί να παράγει περισσότερες μελλοντικές κλήσεις. Δηλαδή η αναδρομική διαδικασία μπορεί να ξεχειλωνει την στοίβα ή την ουρά (δεν έχει σημασια). Αυτό που έχει σημασια είναι ότι στη κλήση δίνουμε όλη την δομή δεδομένων, ουρά ή στοίβα και μας επιστρέφει την αλλαγμένη δομή. Δεν χρειάζεται καν αναδρομή αλλά μια επανάληψη μέχρι να βρεθεί το τέλος ή να αδειάσει η ουρά ή στοιβα. Η εκκίνηση γίνεται με πέρασμα στη δομή του πρώτου στοιχείου.
Η μαγική λέξη εδώ είναι το Ξεχειλωμα, που γίνεται είτε έχουμε ουρά είτε έχουμε στοίβα.

[nikolasmer]

Βασικά το όλο θέμα προέκυψε καθώς επεξεργαζόμουν μια άσκηση.
Έχω δυο πίνακες και θέλω να βρώ το μέγιστο πλήθος συνδυασμών των δυο στοιχείων τους. 
Παράδειγμα:
Έστω οι δύο πίνακες:

• Πίνακας 1: 1,3,5
• Πίνακας 2: 2,4,6

 
 
Όλοι οι δυνατοί συνδυασμοί αθροισμάτων:

• 1+2=3
• 1+4=5
• 1+6=7
• 3+2=5
• 3+4=7
• 3+6=9
• 5+2=7
• 5+4=9
• 5+6=11

Ωραία. Εύκολο.
Αλλά, θυμηθηκα από τα φοιτητικά μου χρόνια σε ενα μάθημα μαθηματικών (Μαθηματικός Λογισμός - Κατερίνης καλή του ώρα) αν θυμάμαι καλά την ευρεση πιθανιτήτων σε σενάριο με σάκο με μπάλες με επανατοποθέτηση ή χωρίς επανατοποθέτηση. και λεω μήπως αλλάζουν οι συνδυασμοί εδώ αν διώξουμε τον αριθμό από το παιχνίδι. 
Επειδή δεν έχω ιδέα το βάζω στο ChatGPT. Μου βγάζει (αντιγράφω):
" η μέθοδος που περιγράφεις, δηλαδή η αντιστοίχιση χωρίς επανάληψη με στόχο τη μεγιστοποίηση ή ελαχιστοποίηση κάποιου αθροίσματος, έχει ευρεία εφαρμογή σε πολλά προβλήματα της πληροφορικής και των μαθηματικών. προβληματα τέτοια είναι: 
1. Πρόβλημα Ανάθεσης (Assignment Problem)
2. Πρόβλημα Αντιστοίχισης Γάμων (Stable Marriage Problem)
3. Πρόβλημα Μεταφοράς (Transportation Problem)
4. Βελτιστοποίηση Πόρων σε Κατανεμημένα Συστήματα
5. Αντιστοίχιση σε Βιοπληροφορική"
 
Έπειτα κάθομαι μια αλλάζω την εκφώνησή μου στην εξής:
 
«Έστω ότι έχουμε έναν πίνακα τιμών με 4 προϊόντα και ένα διαθέσιμο ποσό. Το πρόγραμμα πρέπει να βρει όλους τους συνδυασμούς προϊόντων που μπορούν να αγοραστούν χωρίς να υπερβεί το συνολικό κόστος το διαθέσιμο ποσό.
Πίνακας προϊόντων (τιμές σε ευρώ): 10,20,15,510, 20, 15, 510,20,15,5
Διαθέσιμο ποσό: 40 ευρώ»
 
Το βάζω στο ΑΙ . έβγαλε κάτι χαζαμάρες εκεί, και έπειτα αλλάζω εκφώνηση, τελικό:
«Να γίνει πρόγραμμα το οποίο:

• Διαβάζει τα ονόματα Ν προϊόντων σε πίνακα ΟΝ[Ν] (όπου 4 ≤ Ν ≤ 100).
• Διαβάζει τις αντίστοιχες τιμές τους σε πίνακα Τ[Ν].
• Διαβάζει έναν αριθμό ΠΟΣΟ, που αντιπροσωπεύει το διαθέσιμο ποσό για αγορές. Το ποσό πρέπει να είναι τουλάχιστον ίσο με το φθηνότερο προϊόν του πίνακα.
• Το πρόγραμμα πρέπει να υπολογίζει και να εμφανίζει όλους τους δυνατούς συνδυασμούς προϊόντων που μπορούν να αγοραστούν με το διαθέσιμο ποσό ΠΟΣΟ.

Παράδειγμα:
Έστω ότι έχουμε τον πίνακα με 4 προϊόντα:

• ΟΝ[4] = "Γαˊλα","Ψωμιˊ","Tυριˊ","Mηˊλα""Γάλα", "Ψωμί", "Τυρί", "Μήλα""Γαˊλα","Ψωμιˊ","Tυριˊ","Mηˊλα"
• Τ[4] = 2,1,5,32, 1, 5, 32,1,5,3 (τιμές των προϊόντων σε ευρώ)

Το πρόγραμμα διαβάζει και το διαθέσιμο ποσό: 6 ευρώ.»
 
Το βάζω στο ΑΙ και μου βγάζει (αντιγράφω):
Δυνατοί συνδυασμοί:

• Αγορά του προϊόντος 1: Γάλα→ Κόστος: 2 ευρώ
• Αγορά του προϊόντος 2:  Ψωμί" → Κόστος: 1 ευρώ
• Αγορά του προϊόντος 3: " Τυρί→ Κόστος: 5 ευρώ
• Αγορά του προϊόντος 4: " Μήλα→ Κόστος: 3 ευρώ
• Αγορά των προϊόντων 1 και 2: "ΓαˊλαΨωμιˊ" → Κόστος: 3 ευρώ
• Αγορά των προϊόντων 1 και 4: "Γαˊλα","Mηˊλα→ Κόστος: 5 ευρώ
• Αγορά των προϊόντων 2 και 3: "Ψωμιˊ","Tυριˊ"" → Κόστος: 6 ευρώ (μέγιστο ποσό που επιτρέπεται)
• Αγορά των προϊόντων 2 και 4: "Ψωμιˊ","Mηˊλα → Κόστος: 4 ευρώ

Τελικό αποτέλεσμα:
Οι συνδυασμοί προϊόντων που μπορούν να αγοραστούν με 6 ευρώ ή λιγότερο είναι:

• "Γαˊλα"→ 2 ευρώ
• "Ψωμι→ 1 ευρώ
• "Tυριˊ" → 5 ευρώ
• "Mηˊλα" → 3 ευρώ
• "Γαˊλα", → 3 ευρώ
• "Γαˊλα","Mηˊλα"" → 5 ευρώ
• "Ψωμιˊ","Tυρι→ 6 ευρώ
• "Ψωμιˊ","Mηˊλα" → 4 ευρώ

 
Μπράβο για 4 προϊόντα. Αν είχαμε 50 του λέω;
Για 50 προϊόντα, ο αριθμός των δυνατών συνδυασμών είναι:
2^50−1=1.125.899.906.842.624−1=1.125.899.906.842.6232^{50} - 1 = 1.125.899.906.842.624 - 1 = 1.125.899.906.842.623250−1=1.125.899.906.842.624−1=1.125.899.906.842.623
Άρα, υπάρχουν 1.125.899.906.842.623 δυνατοί συνδυασμοί προϊόντων.
Αυτός ο αριθμός είναι τεράστιος, γι' αυτό και σε πρακτικές εφαρμογές χρησιμοποιούμε αλγοριθμικές τεχνικές (όπως το backtracking που αναφέρθηκε) για να μειώσουμε τον αριθμό των συνδυασμών που υπολογίζουμε, ειδικά αν υπάρχουν περιορισμοί όπως το διαθέσιμο ποσό.
 
Αυτά τα ολίγα. J
 
 
 

[pgrontas]

Στο συγκεκριμένο πρόβλημα που έθεσες το backtracking σου επιτρέπει να σταματήσεις την εξέταση στοιχείων (είτε με αναδρομή είτε με επανάληψη με ουρά) όταν το τρέχον άθροισμα ξεπεράσει το όριο.
Οπότε στην ουσία γλιτώνεις τα υπόλοιπα στοιχεία και έτσι δεν εξετάζεις και τις 2^ν περιπτώσεις.

Είναι μια πρακτική τεχνική που δουλεύει σε κάποια inputs αλλά όχι σε όλα.
Δηλαδή δεν θα δουλέψει αν όλα τα πιθανά αθροίσματα είναι κάτω από το όριο.
Έτσι δεν αλλάζει η πολυπλοκότητα χειρότερης περίπτωσης του προβλήματος που είναι 2^ν.

[nikolasmer]

Στο συγκεκριμένο πρόβλημα που έθεσες το backtracking σου επιτρέπει να σταματήσεις την εξέταση στοιχείων (είτε με αναδρομή είτε με επανάληψη με ουρά) όταν το τρέχον άθροισμα ξεπεράσει το όριο.
Οπότε στην ουσία γλιτώνεις τα υπόλοιπα στοιχεία και έτσι δεν εξετάζεις και τις 2^ν περιπτώσεις.

Είναι μια πρακτική τεχνική που δουλεύει σε κάποια inputs αλλά όχι σε όλα, οπότε δεν αλλάζει η πολυπλοκότητα του προβλήματος που είναι 2^ν.

Δηλαδή δεν κερδίζουμε σε πολυπλοκότητα αλλά κερδίζει ο υπολογιστής σε υπολογιστικούς πόρους ώστε να σταματάει την επανάληψη νωρίτερα. Οκ. 

"Επανάληψη με ουρά";;;;

[pgrontas]

Δηλαδή δεν κερδίζουμε σε πολυπλοκότητα αλλά κερδίζει ο υπολογιστής σε υπολογιστικούς πόρους ώστε να σταματάει την επανάληψη νωρίτερα. Οκ.

"Επανάληψη με ουρά";;;;

Δεν κερδίζεις σε θεωρητική πολυπλοκότητα γιατί αυτή αφορά τη χειρότερη περίπτωση, αλλά μπορεί στην πράξη για κάποια (ίσως και για πολλά) inputs ο αλγόριθμος να μην χρειαστεί να εξετάσει όλες τις περιπτώσεις.
Πχ. αν το πρώτο στοιχείο είναι ήδη μεγαλύτερο από το όριο που θές, ξέρεις ότι δεν υπάρχει περίπτωση να περιέχεται σε καμία αποδεκτή απάντηση οπότε δεν χρειάζεται να δοκιμάσεις ολόκληρο το υποδέντρο των λύσεων που ξεκινάει από αυτό.

Σχετικά με το 'Επανάληψη με ουρά' αναφέρομαι στην υλοποιήση που πρότεινε ο\η Foto (αν κατάλαβα καλά) που μπορείς να κρατάς σε μια ουρά όλα τα στοιχεία που δεν έχεις δοκιμάσει. Πχ. όπως σε ένα γράφημα μπορεί επισκεφτείς όλους τους κόμβους με DFS (αναδρομή) ή BFS (ουρά).

[nikolasmer]

Σας ευχαριστώ όλους για τις απαντήσεις.

[gpapargi]

Το πρόβλημα που περιγράφεις μπορεί να λυθεί λυκειακά χωρίς αναφορά σε backtracking ούτε στοίβα/ουρά.
Έχεις ένα σύνολο από αντικείμενα. Θα πρέπει να φτιάξεις όλα τα υποσύνολά του και για το καθένα από αυτά να βρεις το κόστος. Όσα είναι κάτω από το όριο γίνονται αποδεκτά.
Μπορείς να βρεις όλα τα υποσύνολα ενός συνόλου ως εξής:
Κατασκευάζεις ένα δυαδικό αριθμό με τόσα ψηφία όσα τα αντικείμενά σου. Κάθε ψηφίο αντιστοιχεί σε ένα αντικείμενο και έχει τιμή 0 αν δεν ανήκει το αντικείμενο στο υποσύνολο ή 1 αν ανήκει.
Πχ αν έχεις 5 αντικείμενα ο δυαδικός αριθμός 11001 σημαίνει ότι στο συγκεκριμένο σύνολο ανήκει το πρώτο, το δεύτερο και το πέμπτο αντικείμενο. Παράγοντας όλους δυαδικούς αριθμούς από το 00000 ως το 11111 (2^5-1), παράγεις όλα τα υποσύνολα και βρίσκεις το κόστος του καθενός.
Βελτίωση έρχεται αν στην περίπτωση που κάποιο σύνολο υπερβεί το όριο, τότε το κόβεις και ταυτόχρονα κόβεις και όλα όσα έχουν άσσους εκεί που αυτό έχει μηδενικά.
Έτσι βελτιώνεις τη μέση πολυπλοκότητα αλλά όχι τη χειρότερη που είναι εκθετική Ο(2^ν).

[nikolasmer]

Το πρόβλημα που περιγράφεις μπορεί να λυθεί λυκειακά χωρίς αναφορά σε backtracking ούτε στοίβα/ουρά.
Έχεις ένα σύνολο από αντικείμενα. Θα πρέπει να φτιάξεις όλα τα υποσύνολά του και για το καθένα από αυτά να βρεις το κόστος. Όσα είναι κάτω από το όριο γίνονται αποδεκτά.
Μπορείς να βρεις όλα τα υποσύνολα ενός συνόλου ως εξής:
Κατασκευάζεις ένα δυαδικό αριθμό με τόσα ψηφία όσα τα αντικείμενά σου. Κάθε ψηφίο αντιστοιχεί σε ένα αντικείμενο και έχει τιμή 0 αν δεν ανήκει το αντικείμενο στο υποσύνολο ή 1 αν ανήκει.
Πχ αν έχεις 5 αντικείμενα ο δυαδικός αριθμός 11001 σημαίνει ότι στο συγκεκριμένο σύνολο το πρώτο, το δεύτερο και το πέμπτο αντικείμενο. Παράγοντας όλους δυαδικούς αριθμούς από το 00000 ως το 11111 (2^5-1), παράγεις όλα τα υποσύνολα και βρίσκεις το κόστος του καθενός.
Βελτίωση έρχεται αν στην περίπτωση που κάποιο σύνολο υπερβεί το όριο, τότε το κόβεις και ταυτόχρονα κόβεις και όλα όσα έχουν άσσους εκεί που αυτό έχει μηδενικά.
Έτσι βελτιώνεις τη μέση πολυπλοκότητα αλλά όχι τη χειρότερη που είναι εκθετική Ο(2^ν).

Εξαιρετική σκέψη. 
Η άσκηση στην τελική της μορφή είναι η εξής:
Να γίνει πρόγραμμα σε ΓΛΩΣΣΑ το οποίο:

a.  Διαβάζει τα ονόματα Ν προϊόντων σε πίνακα ΟΝ[Ν] (όπου 4 ≤ Ν ≤ 100).

b. Διαβάζει τις αντίστοιχες τιμές τους σε πίνακα Τ[Ν].

c.  Διαβάζει έναν αριθμό ΠΟΣΟ, που αντιπροσωπεύει το διαθέσιμο ποσό για αγορές. Το ποσό πρέπει να είναι τουλάχιστον ίσο με το ακριβότερο προϊόν του πίνακα.

Το πρόγραμμα πρέπει να υπολογίζει και να εμφανίζει όλους τους δυνατούς συνδυασμούς προϊόντων που μπορούν να αγοραστούν με το διαθέσιμο ποσό ΠΟΣΟ καθώς, ποιο είναι το μέγιστο ποσό χρημάτων που δώθηκε σε κάποιον συνδυασμό και πόσοι ήταν όλοι οι εφικτοί συνδυασμοί. Για παράδειγμα έστω ότι έχουμε έναν πίνακα τιμών με 3 προϊόντα: ΟΝ[3] = "Γάλα", "Ψωμί", "Μήλα" και Τ[3] = 2, 1, 3 (τιμές των προϊόντων σε ευρώ) και ΠΟΣΟ = 4 ευρώ. Όλοι οι συνδυασμοί είναι:

·    "Γάλα" (2 ευρώ) → Εφικτός

·    "Ψωμί" (1 ευρώ) → Εφικτός

·    "Μήλα" (3 ευρώ) → Εφικτός

·    "Γάλα", "Ψωμί" (2 + 1 = 3 ευρώ) → Εφικτός

·    "Γάλα", "Μήλα" (2 + 3 = 5 ευρώ) → Ανέφικτος

·    "Ψωμί", "Μήλα" (1 + 3 = 4 ευρώ) → Εφικτός

·    "Γάλα", "Ψωμί", "Μήλα" (2 + 1 + 3 = 6 ευρώ) → Ανέφικτος

Και το μεγαλύτερο ποσό είναι: 4 ευρώ.