конкретные примеры эвристики

Question

Какие конкретные примеры (например, альфа-бета-обрезка, пример: крестики-нолики и как это применимо там) эвристики.Я уже видел ответ на вопрос о том, что такое эвристика, но я все еще не понимаю, где он использует оценку.Можете ли вы дать мне конкретный пример эвристики и как она работает?

Answer 1

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

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

Manhattan distance = abs(x2-x1) + abs(y2-y1)

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

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

Answer 2

Наиболее показательным является использование эвристики в алгоритмах информированного поиска, таких как A-Star . Для реалистичных задач у вас обычно есть большое пространство поиска, что делает невозможным проверку каждой его части. Чтобы избежать этого, т. Е. Сначала попробовать самые перспективные части пространства поиска, вы используете эвристику. Эвристика дает оценку того, насколько хороши доступные последующие шаги поиска. Вы выберете наиболее многообещающий следующий шаг, то есть best-first . Например, если вы хотите найти путь между двумя городами (т.е. вершинами, соединенными набором дорог, то есть ребрами, которые образуют график), вы можете выбрать прямое расстояние до цели в качестве эвристики определите, какой город посетить первым (и посмотрите, является ли он целевым городом).

Эвристика должна иметь свойства, аналогичные метрикам для пространства поиска, и они обычно должны быть оптимистичными, но это другая история. Проблема обеспечения эвристики, которая работает эффективно и не имеет побочных эффектов, является еще одной проблемой ...

Для применения различных эвристик, используемых для поиска пути через данный лабиринт, также посмотрите на этот ответ .

Answer 3

Конкретный пример: я делал решатель для игры Блок JT , что примерно эквивалентно Same Game .Алгоритм выполняет поиск в ширину по всем возможным попаданиям, сохраняет значения и выполняет следующий слой.Проблема в том, что количество возможных попаданий быстро выходит из-под контроля (10e30 оценочных позиций за игру), поэтому мне нужно сокращать список позиций на каждом ходу и брать только «лучшие» из них.

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

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

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

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

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

Answer 4

Ваш вопрос меня интересует, так как я тоже слышал об эвристике во время учебы, но никогда не видел применения для нее, я немного погуглил и нашел это: http://www.predictia.es/blog/aco-search

Этот код имитирует алгоритм "оптимизации колоний муравьев" для поиска по сайту. «Муравьи» - это работники, которые будут искать по сайту, некоторые будут искать случайно, другие будут следовать «лучшему пути», определенному предыдущими.

Answer 5

В первоначальном вопросе задали конкретные примеры для эвристики.

Некоторые из этих конкретных примеров уже были приведены.Другим из них будет количество неуместных плиток в 15-головоломке или ее улучшение, расстояние Манхэттен, основанное на неуместных плитах.

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

Следовательно, существуют также различные виды проблемно-независимой эвристики.Таким образом, определенным образом каждая такая эвристика может рассматриваться как конкретный эвристический пример, не будучи приспособленной к конкретной проблеме, такой как 15-головоломка.(Примерами эвристики, не зависящей от задачи, взятой из планирования, являются эвристика FF или эвристика Add.)

Эти эвристики, не зависящие от проблемы, основаны на языке общего описания, а затем выполняют релаксацию проблемы.То есть ослабление проблемы основывается только на синтаксисе (и, конечно, на его базовой семантике) описания проблемы, не «зная», что она представляет.Если вы заинтересованы в этом, вы должны ознакомиться с «планированием» и, в частности, с «планированием как эвристическим поиском».Я также хочу упомянуть, что эти эвристики, будучи независимыми от проблем, конечно же, зависят от языка описания проблем.(Например, мои вышеупомянутые эвристики относятся к «проблемам планирования», и даже для планирования существуют различные классы подзадач с разными видами эвристики.)

Answer 6

Пара конкретных примеров: для решения проблемы Knight's Tour можно использовать правило Варнсдорфа - эвристику.Или для решения загадки Пятнадцать возможной эвристикой является A * алгоритм поиска .