Czy możemy po prostu zdefiniować to jako wyszukiwanie z limitem prawdopodobieństwa znalezienia rozwiązania na 1?
Odpowiedzi:
1 dla odpowiedzi № 1krótka odpowiedź: tak
dłuższa odpowiedź: Aby twierdzić, że algorytm wyszukiwania [nawet stochastyczny] jest „kompletny”, musisz pokazać, że jeśli istnieje odpowiedź, algorytm znajdzie odpowiedź w skończonym czasie. Oznacza to, że musisz pokazać, że jeśli istnieje odpowiedź, to nie może być, z żadnym prawdopodobieństwem, ścieżki nie kończącej się [lub kończącej się błędną odpowiedzią]. Więc musisz pokazać, że rozwiązanie zostanie znalezione z prawdopodobieństwem 1 [dokładnie! nie w przybliżeniu!], aby pokazać, że algorytm stochastyczny jest „kompletny”
Na przykład, stroma wspinaczka na wzniesienie z bocznymi spacerami [możesz iść do sąsiada zta sama wartość użytkowa] - nie jest kompletna, ponieważ można wejść w nieskończoną pętlę i nigdy nie znaleźć żadnego rozwiązania. Jeśli jednak ograniczysz liczbę przejść bocznych do liczby skończonej K, jest kompletny, ponieważ jeśli istnieje lokalne minimum, w końcu algorytm znajdzie taki, z prawdopodobieństwem 1.