Αλγόριθμοι: Κόστος Υπολογισμών και Ελεγκτές

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

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

Αντιπροσωπεύοντας το πρόβλημα ως χώρο

Ένα πρόβλημα χώρου είναι ένα περιβάλλον στο οποίο πραγματοποιείται αναζήτηση μιας λύσης. Ένα σύνολο κρατών και οι χειριστές που χρησιμοποιούνται για την αλλαγή αυτών των καταστάσεων αντιπροσωπεύουν το χώρο προβλημάτων. Για παράδειγμα, εξετάστε ένα παιχνίδι κεραμιδιών που έχει οκτώ κεραμίδια σε ένα πλαίσιο 3-x-3. Κάθε κεραμίδι εμφανίζει ένα μέρος μιας εικόνας και τα κεραμίδια ξεκινούν με κάποια τυχαία σειρά έτσι ώστε η εικόνα να είναι κωδικοποιημένη. Ο στόχος είναι να μετακινήσετε ένα κεραμίδι κάθε φορά για να τοποθετήσετε όλα τα κεραμίδια στη σωστή σειρά και να αποκαλύψετε την εικόνα.

Ο συνδυασμός της κατάστασης έναρξης, των τυχαιοποιημένων πλακιδίων και της κατάστασης στόχου - τα κεραμίδια σε μια συγκεκριμένη σειρά - είναι η περίπτωση προβλήματος. Θα μπορούσατε να αναπαριστάτε το γράφημα γραφικά χρησιμοποιώντας ένα γράφημα χώρου προβλημάτων. Κάθε κόμβος του γραφήματος χώρου προβλημάτων παρουσιάζει μια κατάσταση (τα οκτώ κεραμίδια σε μια συγκεκριμένη θέση). Οι άκρες αντιπροσωπεύουν λειτουργίες, όπως για να μετακινήσετε τον αριθμό κεραμιδιών οκτώ. Όταν μετακινείτε πλακίδιο οκτώ, η εικόνα αλλάζει - μετακινείται σε άλλη κατάσταση.

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

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

Πηγαίνοντας τυχαία και ευτυχισμένος με τύχη

Είναι δυνατή η επίλυση ενός προβλήματος αναζήτησης χρησιμοποιώντας τεχνικές ωμής βίας. Το πλεονέκτημα αυτής της προσέγγισης είναι ότι δεν χρειάζεστε καμία γνώση συγκεκριμένου τομέα για να χρησιμοποιήσετε έναν από αυτούς τους αλγόριθμους. Ένας αλγόριθμος βίαιης δύναμης τείνει να χρησιμοποιεί την απλούστερη δυνατή προσέγγιση για την επίλυση του προβλήματος. Το μειονέκτημα είναι ότι μια προσέγγιση ωμής βίας λειτουργεί καλά μόνο για ένα μικρό αριθμό κόμβων. Εδώ είναι μερικοί από τους κοινούς αλγόριθμους αναζήτησης brute-force:

• Breadth-first search: Αυτή η τεχνική ξεκινά από τον κόμβο ρίζας, εξερευνά πρώτα τον κάθε κόμβο και μετά μετακινείται προς το επόμενο επίπεδο. Προχωρεί επίπεδο μέχρι το επίπεδο μέχρι να βρει μια λύση. Το μειονέκτημα αυτού του αλγορίθμου είναι ότι πρέπει να αποθηκεύει κάθε κόμβο στη μνήμη, πράγμα που σημαίνει ότι χρησιμοποιεί μια σημαντική ποσότητα μνήμης για μεγάλο αριθμό κόμβων. Αυτή η τεχνική μπορεί να ελέγξει για διπλούς κόμβους, που εξοικονομεί χρόνο και πάντα έρχεται με μια λύση.
• Η πρώτη αναζήτηση βάθους: Η τεχνική αυτή αρχίζει στον κόμβο ρίζας και διερευνά ένα σύνολο συνδεδεμένων παιδικών κόμβων μέχρι να φτάσει σε έναν κόμβο φύλλων. Προχωράει κλάδος κατά υποκατάστημα μέχρι να βρει λύση. Το μειονέκτημα αυτού του αλγορίθμου είναι ότι δεν μπορεί να ελέγξει για διπλούς κόμβους, πράγμα που σημαίνει ότι μπορεί να διασχίσει τις ίδιες διαδρομές κόμβων περισσότερες από μία φορές. Στην πραγματικότητα, αυτός ο αλγόριθμος μπορεί να μην βρει μια λύση καθόλου, πράγμα που σημαίνει ότι πρέπει να ορίσετε ένα σημείο αποκοπής για να διατηρήσετε τον αλγόριθμο να ψάξει απεριόριστα. Ένα πλεονέκτημα αυτής της προσέγγισης είναι ότι η μνήμη είναι αποτελεσματική.
• Αμφίδρομη αναζήτηση: Αυτή η τεχνική αναζητά ταυτόχρονα από τον κόμβο ρίζας και τον κόμβο στόχου μέχρι να συναντηθούν οι δύο διαδρομές αναζήτησης στη μέση. Ένα πλεονέκτημα αυτής της προσέγγισης είναι ότι είναι καιρός αποτελεσματικός επειδή βρίσκει τη λύση γρηγορότερα από πολλές άλλες λύσεις ωμής βίας. Επιπλέον, χρησιμοποιεί μνήμη πιο αποτελεσματικά από άλλες προσεγγίσεις και πάντα βρίσκει λύση. Το κύριο μειονέκτημα είναι η πολυπλοκότητα της εφαρμογής, η οποία μεταφράζεται σε μεγαλύτερο αναπτυξιακό κύκλο.

Χρησιμοποιώντας μια ευρετική και μια συνάρτηση κόστους

Για μερικούς ανθρώπους η λέξη ευρετική ακούγεται απλά περίπλοκη. Θα ήταν εξίσου εύκολο να πούμε ότι ο αλγόριθμος κάνει μια εκπαιδευμένη εικασία και στη συνέχεια προσπαθεί πάλι όταν αποτύχει. Σε αντίθεση με τις μεθόδους βίαιης δύναμης, οι ευρετικοί αλγόριθμοι μαθαίνουν. Χρησιμοποιούν επίσης λειτουργίες κόστους για να κάνουν καλύτερες επιλογές. Συνεπώς, οι ευρετικοί αλγόριθμοι είναι πιο περίπλοκοι, αλλά έχουν ένα ξεχωριστό πλεονέκτημα στην επίλυση σύνθετων προβλημάτων. Όπως συμβαίνει με τους αλγορίθμους βίαιης δύναμης, υπάρχουν πολλοί ευρετικοί αλγόριθμοι και κάθε ένα έρχεται με το δικό του σύνολο πλεονεκτημάτων, μειονεκτημάτων και ειδικών απαιτήσεων. Η παρακάτω λίστα περιγράφει ορισμένους από τους πιο κοινούς ευρετικούς αλγορίθμους:

• Καθαρή ευρετική αναζήτηση: Ο αλγόριθμος επεκτείνει τους κόμβους με βάση το κόστος τους.Διατηρεί δύο λίστες. Ο κλειστός κατάλογος περιέχει τους κόμβους που έχει ήδη διερευνήσει. η ανοιχτή λίστα περιέχει τους κόμβους που πρέπει να εξερευνήσει ακόμα. Σε κάθε επανάληψη, ο αλγόριθμος επεκτείνει τον κόμβο με το χαμηλότερο δυνατό κόστος. Όλοι οι κόμβοι του παιδιού τοποθετούνται στον κλειστό κατάλογο και υπολογίζονται τα μεμονωμένα κόστη παιδικού κόμβου. Ο αλγόριθμος αποστέλλει τους κόμβους παιδιού με χαμηλό κόστος πίσω στην ανοικτή λίστα και διαγράφει τους παιδικούς κόμβους με υψηλό κόστος. Συνεπώς, ο αλγόριθμος εκτελεί μια έξυπνη αναζήτηση με βάση το κόστος της λύσης.
• f (n) g Ο αλγόριθμος παρακολουθεί το κόστος των κόμβων καθώς τις διερευνά χρησιμοποιώντας την εξίσωση: n) h (n), όπου n
  • είναι το αναγνωριστικό κόμβου. g
  • (n) είναι το κόστος επίτευξης μέχρι τώρα του κόμβου. h
  • (n) είναι το εκτιμώμενο κόστος για την επίτευξη του στόχου από τον κόμβο. f
  • (n) είναι το εκτιμώμενο κόστος της διαδρομής από το n στο στόχο. Η ιδέα είναι να ψάξετε πρώτα τα πιο ελπιδοφόρα μονοπάτια και να αποφύγετε ακριβά μονοπάτια.

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

• f (n) = (n). Αυτός ο συγκεκριμένος αλγόριθμος μπορεί να βρει λύσεις αρκετά γρήγορα, αλλά μπορεί επίσης να κολλήσει σε βρόχους, έτσι πολλοί άνθρωποι δεν θεωρούν ότι είναι η βέλτιστη προσέγγιση για την εξεύρεση λύσης.