3.4.5. Случай S = SD
При решении дискретных задач оптимизации очень естественно использовать метод случайного поиска. Это связано с тем, что всякого рода градиентные представления, свойственные детерминированным методам, в дискретном случае теряют смысл.
Простейшая схема случайного поиска здесь опирается на случайный выбор точки в 
-окрестности исходной. Пусть 
-окрестность исходной точки 
имеет вид
и пусть для простоты множество 
образовано целочисленными векторами 
Иначе говоря, принимаем, что все координаты векторов 
имеют целочисленные значения (более общий случай легко сводится к этому). Пусть 
— множество целочисленных точек, попавших в 
-окрестность, т. е. удовлетворяющих условию (3.4.26). Например, при 
таких точек будет 
и образуются они изменением каждой из координат 
Тогда процедура случайного поиска на 
шаге будет связана со случайным выбором такой точки множества 
для которой выполняются очевидные условия
Введем случайное целочисленное единичное смещение 
Например, для 
вектор смещения 
будет
где лишь одна случайная компонента равна ±1, а остальные равны нулю, т. е.
Можно сделать векторы 
не равновероятными и изменять их вероятности в соответствии с выбранным законом самообучения — например, увеличивая вероятность тех векторов смещений, которые на предыдущем шаге дали уменьшение критерия качества (с последующим нормированием, разумеется). Процесс самообучения здесь естественно дополнить условием запоминания уже проверенных точек, с тем чтобы не повторять проверку условий (3.4.27) в одной и той же точке.
Критерием остановки процесса является отсутствие такой точки при достаточно большом 8. Легко заметить, что при 
метод вырождается в обычный случайный перебор. Поэтому величина 
не должна быть слишком большой и в начале поиска 
Очевидно, что этот процесс можно варьировать в широких пределах — например, изменять характер меры в неравенстве (3.4.26) или адаптировать ее в процессе поиска. Большинство существующих эффективных методов решения дискретных задач оптимизации в той или иной степени использует изложенный подход (см., например, [109, 200]).
