¿Podemos definirlo como la búsqueda con el límite de probabilidad de encontrar una solución para ser 1?
Respuestas
1 para la respuesta № 1respuesta corta: si
respuesta más larga: Para reclamar un algoritmo de búsqueda [incluso el estocástico] está "completo", debe demostrar que si hay una respuesta, el algoritmo encontrará una respuesta, en un tiempo finito. Esto significa que debe mostrar que si hay una respuesta, no puede haber, con ninguna probabilidad, un camino que no termine [o que termine con una respuesta incorrecta]. Por lo tanto, debe mostrar que se encontrará una solución con probabilidad 1 [¡exactamente! no aproximadamente!], para mostrar un algoritmo estocástico es "completo"
Por ejemplo, ascenso más empinado colina Con paseos laterales [puedes ir a un vecino conel mismo valor de utilidad] - no está completo, ya que puede ingresar un ciclo infinito y nunca encontrar ninguna solución. Sin embargo, si limita el número de caminatas laterales a un número finito K, está completo, porque si hay un mínimo local, eventualmente el algoritmo lo encontrará, con probabilidad 1.