Πρόβλημα μέγιστου αθροίσματος υποακολουθίας

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Στην επιστήμη των υπολογιστών το πρόβλημα μέγιστου αθροίσματος υποακολουθίας (Αγγλικά: Maximum subarray problem) είναι να πρόβλημα όπου έχουμε μια σειρά (πίνακα) από θετικούς και αρνητικούς αριθμούς μια ψάχνουμε την συνεχή μεγαλύτερη υποσειρά (υποπίνακα) αριθμών όπου έχουμε το μεγαλύτερο άθροισμα των στοιχείων. Για παράδειγμα στην σειρά των αριθμών −2, 1, −3, 4, −1, 2, 1, −5, 4 η υποσειρά αριθμών με μέγιστο άθροισμα είναι η 4, −1, 2, 1, με άθροισμα 6. [1] [2]

Αλγόριθμος Kadane[Επεξεργασία | επεξεργασία κώδικα]

Σύμφωνα με τον αλγόριθμο του Kadane σαρώνουμε τις τιμές του πίνακα, και κάθε φορά υπολογίζουμε την θέση με το μέγιστο θετικό άθροισμα της υποσειράς που τερματίζεται στο συγκεκριμένο σημείο. Η υποσειρά μπορεί να είναι άδεια (στην περίπτωση που το άθροισμα είναι μηδέν) ή να περιέχει περισσότερους από ένα αριθμούς από την προηγούμενη κατάσταση. [3] Στην γλώσσα Python η υλοποίηση του αλγορίθμου είναι:

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

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

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Παρακάτω βρίσκεται η υλοποίηση σε C++ όπου μπορεί να επιστρέψει (βρίσκονται σχολιασμένα) και του δείκτες αρχής και τέλος της υποσειράς:

int sequence(std::vector<int> const & numbers) {
        // Αρχικοποίηση μεταβλητών
        int max_so_far  = numbers[0], max_ending_here = numbers[0];
 
        // ΠΡΟΑΙΡΕΤΙΚΟ: Αυτές οι μεταβλητές μπορούν να χρησιμοποιηθούν για να έχουμε τους δείκτες αρχής και τέλους της υποσειράς
        // size_t begin = 0;
        // size_t begin_temp = 0;
        // size_t end = 0;
 
        // Βρες την υποσειρά κάνοντας επανάληψη μέχρι το τέλος του πίνακα
        for(size_t i = 1; i < numbers.size(); i++) {
                // υπολογισμός max_ending_here
                if(max_ending_here < 0) {
                        max_ending_here = numbers[i];
 
                        // begin_temp = i;
                }
                else {
                        max_ending_here += numbers[i];
                }
 
                // υπολογισμός max_so_far
                if(max_ending_here >= max_so_far ) {
                        max_so_far  = max_ending_here;
 
                        // begin = begin_temp;
                        // end = i;
                }
        }
        return max_so_far ;
}

Ο αλγόριθμος μπορεί εύκολα να τροποποιηθεί και να αποθηκεύει τα σημεία της υποσειράς η οποία έχει μέγιστο άθροισμα (δείτε σχολιασμένο κώδικα). Η πολυπλοκότητα του αλγόριθμου Kadane είναι \mathcal{O}(n).

Διαιρώ και βασιλεύω[Επεξεργασία | επεξεργασία κώδικα]

Ένα αλγόριθμος Διαιρώ και Βασιλεύω ο οποίος λύνει το πρόβλημα αυτό παρουσιάστηκε από τον Jon Bentley του 1984 με πολυπλοκότητα \mathcal{O}(n \log n). [4]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Brodal, Gerth Stølting; Jørgensen, Allan Grønlund (2007), «A linear time algorithm for the k maximal sums problem», Mathematical Foundations of Computer Science 2007, Lecture Notes in Computer Science, 4708, Springer-Verlag, σελ. 442–453, doi:10.1007/978-3-540-74456-6_40 
  2. Takaoka, T. (2002), «Efficient algorithms for the maximum subarray problem by distance matrix multiplication», Electronic Notes in Theoretical Computer Science 61, http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf 
  3. Κλεάνθους Λοίζου, Στέλλα. «1 ΕΠΛ 231 – Δομές Δεδομένων και Αλγόριθμοι Εργαστήριο 03: Πίνακες / Συλλογές Μέγιστο Άθροισμα Υπο‐ακολουθίας». ΕΠΛ 231 : Δομές Δεδομένων και Αλγόριθμοι. Τμήμα Πληροφορικής Πανεπιστήμιου Κύπρου. https://www.cs.ucy.ac.cy/courses/EPL231/labs/2014S.EPL231.lab.03.arrays.pdf. Ανακτήθηκε στις 5 Ιουνίου 2014. 
  4. Bentley, Jon (1984), «Programming pearls: algorithm design techniques», Communications of the ACM 27 (9): 865–873, doi:10.1145/358234.381162 
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Maximum subarray problem της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).