Алгоритм решения Peg Solitaire / Senku
Мне нужно запрограммировать решатель для игры в пасьянс Peg / Senku
Здесь уже есть вопрос, но предложенный ответ - это алгоритм грубой силы с возвратом, который не является решением, которое я ищу.
Мне нужно найти эвристику, чтобы применить алгоритм A*. Оставшиеся колышки не являются хорошей эвристикой, так как каждый ход отбрасывает один колышек, поэтому стоимость всегда одинакова.
Есть идеи?
2 ответа
Я читал газету, рассказывающую об этой проблеме, и они предлагают 3 эвристики:
1 - Количество узлов, доступных для следующего шага, с учетом того, какие из следующих шагов доступны, тем лучше узел.
2 - Количество изолированных колышков - чем меньше изолированных колышков, тем лучше узел.
3 - Чем меньше колышков на доске, тем лучше узел.
Это может быть не лучшая эвристика для этой проблемы, но кажется простым подходом.
Вы можете сделать как предложено Россумом. Другой вариант - использовать сумму расстояний (или некоторую другую функцию расстояний) от центра. Или вы могли бы объединить два.