Αλγόριθμος προβλήματος qssort

Question

Έχω γράψει σε Python δύο αλγορίθμους αναζήτησης για το πρόβλημα qssort:

• Ο πρώτος είναι εντελώς εξαντλητικός (δηλ. τερματίζει όταν ελέγξει ότι η ουρά ταξινομήθηκε), αλλά τρέχει με απαγορευτική ταχύτητα για $Ν > 10$.
• Ο δεύτερος εφαρμόζει μια πιο έξυπνη συνθήκη τερματισμού, ελέγχοντας αν η ουρά και η στοίβα ικανοποιούν μια (εύκολη) ιδιότητα, η οποία
  οδηγεί σε λύση με επαναλαμβανόμενες κινήσεις 'S'. Αυτός ο αλγόριθμος
  τρέχει με καλή ταχύτητα ακόμα και για $Ν = 30$, ωστόσο πρόσεξα (αφού
  τον έγραψα) ότι μάλλον δεν είναι πάντα ορθός, καθώς π.χ. ελέγχει
  πρώτα την περίπτωση QQQQSSSS και μετά την QQSSQS, το οποίο είναι
  λάθος αφού η δεύτερη έχει μικρότερο μήκος.

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

Answer 1

Αν πρέπει να διαλέξεις ανάμεσα σε έναν μη αποδοτικό σωστό αλγόριθμο και έναν αποδοτικό αλγόριθμο που όμως δεν απαντάει σωστά σε όλες τις περιπτώσεις, προτείνω να διαλέξεις τον πρώτο. Ο δεύτερος είναι αρκετά πιθανό να χάσει test cases λόγω λανθασμένης απάντησης.

Η εκφώνηση της άσκησης εγγυάται ότι ο εξαντλητικός αλγόριθμος με BFS (σωστά υλοποιημένος, φυσικά) θα περνάει τα test cases εντός του χρονικού ορίου. Αυτό σημαίνει ότι αν σας δώσω test case με N=17 (θα το κάνω), αυτό θα είναι έτσι φτιαγμένο ώστε η τελική κατάσταση να μην αργεί να βρεθεί.

Προσέξτε ότι το πρόβλημα έχει πάντα λύση, επομένως με τον εξαντλητικό αλγόριθμο δεν πρόκειται ποτέ να αδειάσει η ουρά.

Comments

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