Алгоритмы против эвристики

Алгоритмы против эвристики

Алгоритмы и эвристика — это не одно и то же. В этом посте вы узнаете, как их различать.

Введение

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

По-видимому, это верно при работе над проблемами оптимизации, где цель состоит в том, чтобы найти наилучшее возможное решение данной проблемы. Пример задачи оптимизации известен как TSP, аббревиатура от задача коммивояжера, где вам дан набор вершин, и вы должны найти кратчайший путь, соединяющий их все. посетив каждую вершину только один раз. Чтобы было понятнее, давайте изобразим следующий набор вершин:

Сценарий состоит из 4 вершин квадрата. Подход может состоять в том, чтобы случайным образом выбрать вершину в качестве начальной точки и перейти к ближайшей непосещенной вершине. После посещения удалите вершину из набора непосещенных вершин и повторяйте подход, пока не будут посещены все вершины. В этот момент мы соединяем ребром последнюю посещенную вершину с первой. В псевдокоде это будет примерно так:

Pick a random vertex v0 from the set of unvisited vertices V 
v = v0 
Mark v as visited and remove from V 
Until V is not empty: 
    Choose the point w as the nearest point to v 
    Visit w and remove it from V 
    v = w 
Connect v with v0

Следуя этому подходу, мы нашли бы следующее решение для предыдущего определенного сценария:

где мы определили путь A->B->C->D->A. Решение является оптимальным, и мы могли бы подумать, что такой подход на самом деле является правильным алгоритмом для решения проблемы TSP. Но давайте применим тот же подход к следующему сценарию, где мы выбираем вершину A в качестве начальной вершины:

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

Как видите, очевидно, что в какой-то момент метод обречен на провал. Эта процедура действительно является не алгоритмом, а эвристикой, известной как эвристика ближайшего соседа.

Что такое алгоритм?

Чтобы понять разницу между алгоритмами и эвристиками, нам нужно дать некоторые определения. Итак, когда мы можем считать процедуру, достойную называться «алгоритмом»?

Алгоритм – это процедура с конечным числом шагов, которая всегда дает правильное решение для данной проблемы.

Разберем это определение. Во-первых, алгоритм должен привести к решению за ограниченное количество шагов. Причина этого определения заключается в том, что алгоритмы должны производить решение на конечных машинах (например, компьютерах), которые имеют ограниченное время и ограниченное пространство. Подумайте, например, о проблеме определения π: вы бы выбрали между алгоритмом, который производит все цифры π, но никогда не заканчивается, или вы выбрали бы алгоритм, который производит только первые 100 цифр π, но завершается через несколько миллисекунд? Я бы пошел по второму варианту.

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

Что такое эвристика?

С другой стороны, эвристика может быть определена следующим образом:

Эвристика — это процедура решения проблемы без доказательства правильности.

Демонстрировать неправильность проще, чем делать обратное. Требуется только найти контрпример: действительно никто не может претендовать на правильность после того, как контрпример найден. Если оглянуться на то, что мы делали раньше, то это именно процесс демонстрации неправильности.

Означает ли это, что эвристики неверны и бесполезны? Абсолютно нет. Наоборот, они широко используются для нахождения приближенного решения задач, точное решение которых было бы невозможно найти из-за ограничений во времени или пространстве. Проблема TSP снова является допустимым примером: как комбинаторная NP-задача, ее точное решение может быть найдено только с помощью алгоритма перебора грубой силы, который имеет O(n!) сложность.

Как найти контрпримеры

Нахождение контрпримеров — важный навык для разработчиков, поскольку он ускоряет процесс выявления слабых мест на этапе разработки алгоритма, который обычно начинается с определения жадной эвристики, который совершенствуется сбой за сбоем, пока не начинает все больше и больше выглядеть как алгоритм. Этот навык может пригодиться во многих ситуациях, от работы до собеседований. Итак, позвольте мне дать несколько советов по поиску контрпримеров: