FuzzyLogic
Advanced Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Эвристика в программировании это обычно решение задачи при помощи разбора частных случаев. Например хочешь ты посчитать площадь треугольника для этого можно написать просто общую формулу которая будет работать для любого треугольника. А можно попытаться определить вид треугольника (равносторонний, прямоугольный итд) и использовать различные правила в зависимости от типа треугольника. Зачем это надо? В приведенном мной примере этого нет, но обычно каждая ветвь эвристического алгоритма эффективнее чем общее решение.
Замечание: эвристический алгоритм зачастую не решает задачу в общем виде а работает только для определенных случаев; некоторые задачи не имеют (не найдены) общие решения и они решаются при помощи эвристики.
А про обход доски ходом коня...
Правило Варнсдорфа
Оригинальное правило, дающее линейный по времени алгоритм обхода доски, было предложена Варнсдорфом(Warnsdorff) в 1983 году.
Правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.
На практике это реализуется, например, следующим образом. Перед каждым ходом коня вычисляется рейтинг ближайших доступных полей - полей, на которых конь еще не был, и на которые он может перейти за один ход. Рейтинг поля определяется числом ближайших доступных с него полей. Чем меньше рейтинг, тем он лучше. Потом делается ход на поле с наименьшим рейтингом (на любое из таковых, если их несколько), и так далее, пока есть куда ходить.
Эвристика всегда работает на досках от 5x5 до 76x76 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.
Существует линейный алгоритм для досок любого размера, который делит доску на меньшие части, но, из-за обилия особых случаев, он довольно сложный и не такой интересный, как эта элегантная эвристика
|
