Algoritmus náhodného vyhledávání (Random Search) v Java: Úvod, Jak to funguje, Příklad

Algoritmus náhodného vyhledávání, také známý jako vyhledávání Monte Carlo, je metoda vyhledávání založená na náhodnosti. Namísto postupné kontroly každého prvku v datovém poli tento algoritmus náhodně vybere řadu prvků k prozkoumání. Tento přístup šetří čas a zdroje ve srovnání se sekvenčním vyhledáváním.

Jak to funguje

1. Krok 1: Začněte s datovým polem, které chcete prohledávat.

2. Krok 2: Náhodně vyberte určitý počet prvků, které chcete prozkoumat.

3. Krok 3: Zkontrolujte vybrané prvky, zda odpovídají podmínkám vyhledávání.

4. Krok 4: Pokud je nalezen odpovídající prvek, vraťte výsledek; pokud ne, vraťte se ke kroku 2.

5. Krok 5: Pokračujte v procesu, dokud není nalezena shoda nebo dokud není dosaženo maximálního počtu pokusů.

Výhody a nevýhody

výhody:

• Efektivní na zdroje: Šetří čas a paměť, zejména u velkých datových polí.
• Náhodnost: Není snadno předvídatelná, vhodná pro situace, které vyžadují náhodnost.

Nevýhody:

• Žádná záruka úspěchu: Neexistuje žádná záruka, že algoritmus najde požadovaný výsledek.
• Může trvat dlouho: V nejhorším případě může algoritmus trvat déle než sekvenční vyhledávání.

Příklad a vysvětlení

Zvažte následující příklad použití algoritmu náhodného vyhledávání k nalezení celého čísla v poli:

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.");  
        }  
    }  
}  

V tomto příkladu používáme algoritmus Random Search Algorithm k nalezení celého čísla v poli. Iterujeme pole, náhodně vybereme index a zkontrolujeme, zda prvek v tomto indexu odpovídá cílovému číslu. Pokud je nalezen, vrátíme index; pokud ne, pokračujeme, dokud není dosaženo maximálního počtu pokusů.