prune and search

Angol

Főnév

prune and search (tsz. prune and searches)

1. (informatika) A prune and search (magyarul: metszés és keresés) egy algoritmikus stratégia, amely a problématér rendszeres csökkentésére épül: minden iterációban a problématér egy részét eldobjuk (prune), majd a maradék részben folytatjuk a keresést. Ez a megközelítés gyakran lineáris vagy loglineáris időkomplexitású algoritmusokhoz vezet, és különösen hatékony optimalizálási problémák vagy kiválasztási problémák esetén.

---

🧠 1. Mi az a prune and search?

A prune and search algoritmus lényege:

1. Prune (metszés): A probléma bizonyos részeit kizárjuk, amelyek biztosan nem tartalmazzák a megoldást.
2. Search (keresés): A kisebbé vált problémateret újraértékeljük, és ismételjük a folyamatot.

A cél: minden lépésben garantáltan csökkenteni a problémaméretet valamilyen arányban (pl. legalább 25–50%-kal).

---

📐 2. Klasszikus példa: Median of Medians – lineáris időbeli kiválasztás

Feladat: Adott egy ${\textstyle n}$ elemű tömb, és egy ${\textstyle k}$, keressük meg a ${\textstyle k}$-adik legkisebb elemet (kiválasztási probléma).

Megoldás prune and search stratégiával:

1. Osszuk fel a tömböt ötfős csoportokra.
2. Minden csoportban határozzuk meg a mediánt.
3. Az összes mediánból válasszuk ki a medián mediánját — ez a pivot.
4. Osszuk ketté az eredeti tömböt:
   • kisebbek, mint a pivot
   • nagyobbak, mint a pivot
5. A pivot helyzete alapján:
   • ha ott van a keresett rang, visszatérünk vele
   • ha nem, akkor a megfelelő részproblémában folytatjuk

🔁 A probléma mérete minden körben bizonyíthatóan csökken → lineáris idő.

---

📉 3. Időkomplexitás

Legyen ${\textstyle T(n)}$ az idő. A prune and search algoritmusok gyakran:

$$T(n)=T(\alpha n)+O(n)$$

ahol ${\textstyle \alpha <1}$, pl. ${\textstyle \alpha ={\frac {3}{4}}}$

Ez rekurzívan ${\textstyle O(n)}$-hez konvergál.

---

🧮 4. Egyéb alkalmazások

📌 4.1 Legközelebbi pontpár síkban (geometria)

• A síkot két részre bontjuk.
• A középsávban is csak néhány pontot kell ellenőrizni (pruning).
• A kombinálás lépése gyors.

📌 4.2 Lineáris programozás 2D-ben

• A lehetséges megoldási teret csökkentjük minden iterációban.
• Minden lépés: egyenletek metszésének vizsgálata → egy része biztosan eldobható.

📌 4.3 Unimodális függvény minimuma

• Ha tudjuk, hogy a függvénynek egyetlen minimuma van,
• Akkor két pontban kiértékelve eldönthetjük, melyik irányba “metszhetjük” le a keresési teret.

---

🔁 5. Általános sablon (pszeudokód)

def prune_and_search(problem):
    if is_small(problem):
        return solve_directly(problem)

    pivot = choose_good_pivot(problem)
    pruned_problem = discard_irrelevant_part(problem, pivot)

    return prune_and_search(pruned_problem)

---

⚠️ 6. Előnyök és hátrányok

Előny	Hátrány
Hatékony méretcsökkentés	Bonyolult implementáció lehet
Garantált lépésenkénti haladás	Néha sok konstans overhead
Lehetséges lineáris futási idő	Csak bizonyos problémákra alkalmas

---

📊 7. Összehasonlítás más technikákkal

Módszer	Röviden
Brute-force	Minden lehetőséget kipróbál
Divide and conquer	Feloszt és kombinál
Greedy	Mindig lokálisan optimális lépést választ
Dynamic programming	Részeredmények újrafelhasználása
Backtracking	Kipróbálás + visszalépés
Prune and search	Méretcsökkentés + újrakezdés

---

📌 8. Összefoglalás

Tulajdonság	Leírás
Cél	Problématér fokozatos csökkentése
Lépések	Pivotválasztás, metszés, keresés
Időkomplexitás	Gyakran ${\textstyle O(n)}$, ha jól kivitelezett
Használati terület	Kiválasztás, LP, geometria, optimalizálás
Kulcsgondolat	Egy lépésben garantáltan csökkentjük a problémaméretet

További információk

• prune and search - Szótár.net (en-hu)
• prune and search - Sztaki (en-hu)
• prune and search - Merriam–Webster
• prune and search - Cambridge
• prune and search - WordNet
• prune and search - Яндекс (en-ru)
• prune and search - Google (en-hu)
• prune and search - Wikidata
• prune and search - Wikipédia (angol)