Prořezávej a hledej

Prořezávej a hledej (Prune and search) je typ algoritmu založený na vyřazování neperspektivních dat – redukci velikosti problému. Toto paradigma je velmi podobné algoritmům typu rozděl a panuj (divide and conquer), zásadní rozdíl je ovšem v tom, že při prořezávání neprocházíme všechny větve, ale pouze ty, které pro nás dávají smysl.

Příklad

Pokud hledáme n-té nejvyšší číslo v neseřazeném poli, tak by řešením zajisté bylo pole seřadit a podívat se na zadaný index. Toto řešení ovšem není příliš efektivní. Lepším řešením je upravit například Quicksort tak, aby se po rozdělení pole dle pivota prohledávala pouze ta část, která obsahuje řešení - Quicksort v každém svém kroku umístí pivota na korektní místo v seřazeném poli, není proto problém rozhodnout, ve které části se nachází ono hledané číslo.

Složitost

Zatímco asymptotická složitost Quicksortu je $O(n^{2})$ a očekáváná $O(n \\cdot \\log(n))$ , tak díky eliminaci větví, které nemohou obsahovat řešení, je očekávaná složitost prune and search algoritmu $O(c \\cdot n)$ , kde c je malá konstanta.

Kód

Java

   /**
     * Prorezavej a hledej
     * @param array prohledavane pole
     * @param index kolikatou nejvyssi hodnotu hledame (cislovano od 0)
     * @param left prvni levy prvek, na ktery muzeme sahnout
     * @param right prvni prvek, na ktery uz nemuzeme sahnout
     * @return index-ta nejvyssi hodnota
     */
    public static int pruneAndSearch(int[] array, int index, int left, int right) {
        int boundary = left;
        for (int i = left + 1; i < right; i++) { 
            if (array[i] > array[left]) { //primo za pivot posleme vse vetsi, nez je on sam
                swap(array, i, ++boundary);
            }
        }
        swap(array, left, boundary);
        //konec quicksortu

        if (boundary == index) return array[boundary]; //nalezli jsme
        else if (boundary > index) return pruneAndSearch(array, index, left, boundary); //odrizneme pravou vetev
        else return pruneAndSearch(array, index, boundary + 1, right); //odrizneme levou vetev        
    }

    /**
     * Prohodi prvky v zadanem poli
     * @param array pole
     * @param left prvek 1
     * @param right prvek 2
     */
    private static void swap(int[] array, int left, int right) {
        int tmp = array[right];
        array[right] = array[left];
        array[left] = tmp;
    }

Literatura

Prune-and-search. In . [s.l.] : [s.n.], 2006 [cit. 2010-03-15]. Dostupné z WWW: <http://www.cs.duke.edu/courses/fall05/cps230/L-03.pdf>.

Příklad

Složitost

Kód

Literatura

Doporučujeme