Разница между стохастическим и эвристическим алгоритмом

TTBOMK, «стохастический алгоритм» не является стандартным термином. Однако «рандомизированный алгоритм» есть, и, вероятно, здесь имеется в виду именно это.

Случайный выбор: как-то использует случайность. Есть два варианта: алгоритмы Монте-Карло всегда завершаются за ограниченное время, но не гарантируют оптимального решения, а алгоритмы Лас-Вегаса не обязательно гарантируют завершение в любое время. конечное время, но обещают найти оптимальное решение. (Обычно они также должны иметь конечное ожидаемое время работы.) Примеры распространенных алгоритмов Монте-Карло: MCMC, имитация отжига и проверка простоты Миллера-Рабина. Быстрая сортировка со случайным выбором опорной точки — это алгоритм Лас-Вегаса, который всегда завершается за конечное время. Алгоритм, который не использует никакой случайности, является детерминированным.

Эвристика: не гарантируется правильный ответ. Алгоритм, который не является эвристическим, точен.

Многие эвристики чувствительны к «случайным» свойствам входных данных, которые не влияют на истинное решение, например, элементы заказа учитываются в эвристике «первое соответствие» для задачи упаковки в корзину. В этом случае их можно рассматривать как рандомизированные алгоритмы Монте-Карло: вы можете случайным образом переставлять входные данные и запускать их повторно, всегда сохраняя лучший найденный ответ. OTOH, другие эвристики не обладают этим свойством, например. эвристика First-Fit-Decreasing является детерминированной, поскольку она всегда сначала сортирует элементы в порядке убывания размера.

Если набор возможных выходных данных конкретного рандомизированного алгоритма конечен и содержит истинный ответ, то его достаточно долгое выполнение "практически гарантировано" для его нахождения (в том смысле, что вероятность ненахождение может быть сделано сколь угодно малым, но никогда не равным 0). Обратите внимание, что некоторая перестановка входных данных эвристики не приводит автоматически к получению точного ответа — в случае первого подбора оказывается, что это верно верно, но это было доказано только в 2009 году.

Иногда могут быть сделаны более сильные утверждения о сходимости рандомизированных алгоритмов: обычно они имеют вид «Для любого заданного малого порога d после t шагов мы будем в пределах d от оптимального решения с вероятностью f (t, d)», с f(t, d) — возрастающая функция от t и d.

Бут-подходы обычно используются для ускорения генерирования и тестирования решений NP-полных задач.

1. Стохастические алгоритмы используют случайность

   Они используют все комбинации, но не по порядку, а вместо этого используют случайные из всего диапазона возможностей, надеясь быстрее найти решение. Внедрение выполняется быстро и легко, а одна итерация также выполняется быстро (постоянное время).

2. Эвристические алгоритмы

   Они подбирают комбинации не случайным образом, а на основе некоторых знаний об используемом процессе, наборе входных данных или использовании. Таким образом, они значительно сокращают количество комбинаций до тех, которые, вероятно, являются решением, и используют только их, но обычно все до тех пор, пока решение не будет найдено.

   Сложность реализации зависит от проблемы, одна итерация обычно намного медленнее, чем стохастический подход (постоянное время), поэтому эвристика используется только в том случае, если количество возможностей снижено настолько, чтобы фактическое ускорение было видно, потому что даже если сложность алгоритма с эвристикой обычно намного ниже иногда постоянное время достаточно велико, чтобы даже замедлить работу... (с точки зрения времени выполнения)

Стендовые подходы можно комбинировать вместе