короткий ответ: да
более длинный ответ: для того, чтобы утверждать, что алгоритм поиска [даже стохастический] "завершен", вы должны показать, что если ответ существует, алгоритм найдет ответ вконечное времяЭто означает, что вы должны показать, что при наличии ответа с какой-либо вероятностью не может быть не завершающего [или заканчивающего с неправильным ответом] пути.Итак, вам нужно показать, что решение будет найдено с вероятностью 1 [точно!не приблизительно!], чтобы показать, что стохастический алгоритм «завершен»
Например, крутое восхождение на гору с боковыми прогулками [вы можете перейти к соседу с тем же значением полезности] -не является полным, так как вы можете войти в бесконечный цикл и никогда не найти никакого решения.Однако, если вы ограничите число обходов до конечного числа K, оно будет завершено, потому что если существует локальный минимум, в конечном итоге алгоритм найдет его с вероятностью 1.