(Random Search) Algorytm wyszukiwania losowego w Java: Wprowadzenie, Jak to działa, Przykład

Algorytm wyszukiwania losowego, znany również jako wyszukiwanie Monte Carlo, to metoda wyszukiwania oparta na losowości. Zamiast sekwencyjnie sprawdzać każdy element tablicy danych, algorytm ten losowo wybiera liczbę elementów do sprawdzenia. Takie podejście pozwala zaoszczędzić czas i zasoby w porównaniu z wyszukiwaniem sekwencyjnym.

Jak to działa

1. Krok 1: Rozpocznij od tablicy danych, którą chcesz przeszukać.

2. Krok 2: Losowo wybierz określoną liczbę elementów do sprawdzenia.

3. Krok 3: Sprawdź wybrane elementy, czy spełniają kryteria wyszukiwania.

4. Krok 4: Jeśli zostanie znaleziony pasujący element, zwróć wynik; jeśli nie, wróć do kroku 2.

5. Krok 5: Kontynuuj proces do momentu znalezienia dopasowania lub osiągnięcia maksymalnej liczby prób.

Zalety i wady

Zalety:

• Oszczędność zasobów: Oszczędza czas i pamięć, szczególnie w przypadku dużych tablic danych.
• Losowość: Niełatwa do przewidzenia, odpowiednia w sytuacjach wymagających losowości.

Niedogodności:

• Brak gwarancji sukcesu: Nie ma pewności, że algorytm znajdzie pożądany wynik.
• Może zająć dużo czasu: w najgorszym przypadku algorytm może zająć więcej czasu niż wyszukiwanie sekwencyjne.

Przykład i wyjaśnienie

Rozważmy następujący przykład użycia algorytmu wyszukiwania losowego do znalezienia liczby całkowitej w tablicy:

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

W tym przykładzie używamy algorytmu wyszukiwania losowego, aby znaleźć liczbę całkowitą w tablicy. Wykonujemy iterację po tablicy, losowo wybieramy indeks i sprawdzamy, czy element w tym indeksie pasuje do liczby docelowej. Jeśli zostanie znaleziony, zwracamy indeks; jeśli nie, kontynuujemy aż do osiągnięcia maksymalnej liczby prób.