Wikiszótár

Las Vegas-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈlɒʃvɛɡɒʃɒlɡoritmuʃ]

Főnév

Las Vegas-algoritmus

  1. (matematika, algoritmusok) A Las Vegas-algoritmus egy olyan véletlenített algoritmus, amely mindig helyes eredményt ad, de a futási ideje véletlenszerű lehet. Más szóval, garantáltan helyes, de a végrehajtási idő a bemenettől és a véletlenszerű választásoktól függ.


Tulajdonságai

  1. Determinált kimenet:
    • Az algoritmus soha nem ad hibás eredményt, azaz ha véget ér, akkor biztosan helyes megoldást szolgáltat.
  2. Véletlen futási idő:
    • A futási idő véletlenszerű, és a bemenettől függően különböző lehet.
  3. Eltérés a Monte Carlo-algoritmusoktól:
    • Míg a Monte Carlo-algoritmusok gyorsak, de nem garantáltan helyesek, a Las Vegas-algoritmusok mindig helyesek, de a futási idejük változó.


Hogyan működik?

  • Az algoritmus véletlenszerű stratégiákat próbál ki, amíg meg nem talál egy helyes megoldást.
  • Ha egy adott stratégia nem működik, az algoritmus újraindul egy másik véletlenszerű választással.
  • Amikor az algoritmus megtalálja a helyes megoldást, leáll.


Példa: Gyors rendezés (Randomized QuickSort)

A gyorsrendezés egyik véletlenített változata Las Vegas-algoritmus, amely a partíciós lépés során véletlenszerűen választ pivot elemet. Ez nem befolyásolja az eredmény helyességét, de véletlenszerűvé teszi a futási időt.

Algoritmus lépései

  1. Véletlenszerűen válassz egy pivot elemet.
  2. Oszd két részre a tömböt a pivot szerint.
  3. Rekurzívan alkalmazd az algoritmust a két részre.

Python implementáció

import random

def randomized_quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot_index = random.randint(0, len(arr) - 1)
    pivot = arr[pivot_index]
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return randomized_quicksort(less) + equal + randomized_quicksort(greater)

# Példa használat
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = randomized_quicksort(arr)
print("Rendezett tömb:", sorted_arr)

Kimenet: 

Rendezett tömb: [1, 1, 2, 3, 6, 8, 10]

Példa: Las Vegas-alapú prímteszt

Egy prímteszt, amely garantáltan helyes eredményt ad, de a futási ideje a bemenettől és a véletlenszerű választásoktól függ.

Python implementáció

import random

def is_prime_las_vegas(n, k=5):  # k az ismétlések száma
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False

    # Írjuk fel n-1 = 2^r * d alakban
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)  # a^d % n
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # Kompozit
    return True  # Prím

# Példa használat
print("29 prím?", is_prime_las_vegas(29))  # True
print("30 prím?", is_prime_las_vegas(30))  # False

Időbonyolultság

  • Átlagos eset: Az algoritmus általában gyors, de a futási idő véletlenszerűen változik.
  • Legrosszabb eset: Ritkán, de előfordulhat, hogy az algoritmus sokáig fut (például ha sok véletlen választás sikertelen).


Előnyök

  1. Helyesség:
    • Mindig garantáltan helyes megoldást ad.
  2. Egyszerűség:
    • Véletlenítés révén gyakran elkerüli a speciális eseteket, amelyek egy determinisztikus algoritmus számára problémát jelenthetnek.
  3. Hatékonyság:
    • Gyakran gyorsabb, mint determinisztikus algoritmusok, különösen rosszul strukturált bemeneteknél.


Hátrányok

  1. Nem kiszámítható futási idő:
    • A véletlenszerű döntések miatt nehéz előre meghatározni a futási időt.
  2. Véletlenszám-generátor minősége:
    • Az algoritmus megbízhatósága nagyban függ a véletlenszám-generátor minőségétől.


Alkalmazások

  1. Rendezési algoritmusok:
    • Randomized QuickSort.
  2. Prímtesztelés:
    • Véletlenszerűen generált tesztek alkalmazása.
  3. Adatstruktúrák:
    • Hash-alapú algoritmusok optimalizálása véletlenszerű eljárásokkal.
  4. Játék- és stratégiaoptimalizálás:
    • Például mesterséges intelligencia algoritmusokban.


Összegzés

A Las Vegas-algoritmusok olyan véletlenített algoritmusok, amelyek garantáltan helyes eredményt adnak, de a futási idejük változó. Az egyszerűsége és hatékonysága miatt számos területen alkalmazható, különösen olyan problémák esetén, ahol determinisztikus algoritmusok nehezen alkalmazhatók vagy lassúak. A véletlenszerűség segítségével elkerülik a problémás eseteket, miközben megbízható eredményeket adnak.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Las_Vegas-algoritmus&oldid=3479604”