Véletlenszerű keresési (Random Search) algoritmus itt Java: Bevezetés, Hogyan működik, Példa

A Random Search algoritmus, más néven Monte Carlo keresés, egy véletlenszerűségen alapuló keresési módszer. Ahelyett, hogy szekvenciálisan ellenőrizné az adattömb minden elemét, ez az algoritmus véletlenszerűen választ ki több elemet a vizsgálathoz. Ez a megközelítés időt és erőforrásokat takarít meg a szekvenciális kereséshez képest.

Hogyan működik

1. 1. lépés: Kezdje a keresni kívánt adattömbbel.

2. 2. lépés: Véletlenszerűen válasszon ki bizonyos számú elemet a vizsgálathoz.

3. 3. lépés: Ellenőrizze a kiválasztott elemeket, hogy megfelelnek-e a keresési feltételnek.

4. 4. lépés: Ha talál egyező elemet, adja vissza az eredményt; ha nem, térjen vissza a 2. lépéshez.

5. 5. lépés: Folytassa a folyamatot, amíg egyezést nem talál, vagy el nem éri a kísérletek maximális számát.

Előnyök és hátrányok

Előnyök:

• Erőforrás-hatékony: Időt és memóriát takarít meg, különösen nagy adattömbök esetén.
• Véletlenszerűség: Nem könnyen kiszámítható, véletlenszerűséget igénylő helyzetekre alkalmas.

Hátrányok:

• Nincs garancia a sikerre: Nincs garancia arra, hogy az algoritmus megtalálja a kívánt eredményt.
• Hosszú ideig tarthat: A legrosszabb esetben az algoritmus tovább tarthat, mint a szekvenciális keresés.

Példa és magyarázat

Tekintsük a következő példát a Véletlenszerű keresési algoritmus használatával egy egész szám keresésére egy tömbben:

import java.util.Random;  
  
public class RandomSearchExample {  
    static int randomSearch(int[] arr, int target) {  
        Random rand = new Random();  
        int maxAttempts = arr.length; // Maximum number of attempts  
        for(int i = 0; i < maxAttempts; i++) {  
            int randomIndex = rand.nextInt(arr.length); // Randomly select an index  
            if(arr[randomIndex] == target) {  
                return randomIndex; // Return the index if found  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = {1, 5, 9, 3, 7};  
        int target = 3;  
        int result = randomSearch(numbers, target);  
        if(result != -1) {  
            System.out.println("Number " + target + " found at index " + result);  
        } else {  
            System.out.println("Number " + target + " not found in the array.");  
        }  
    }  
}  

Ebben a példában a Véletlenszerű keresési algoritmust használjuk egy egész szám megkeresésére egy tömbben. Végigfutunk a tömbön, véletlenszerűen kiválasztunk egy indexet, és ellenőrizzük, hogy az adott index eleme megegyezik-e a célszámmal. Ha megtaláltuk, visszaadjuk az indexet; ha nem, addig folytatjuk a kísérletek maximális számát.