Есть ли способ избежать ненужной рекурсии?

Я разместил этот вопрос в CodeReview, но я понял, что это не так много вопросов Haskell, поскольку это вопрос алгоритма.

Код Haskell можно найти в моем реестре github, но я думаю, что код не так важен, как общая концепция.

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

Плата Kalaha http://www.graf-web.at/mwm/kalaha.jpg

Плата начинается с пустых магазинов и равного количества мрамора в каждом банке.

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

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

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

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

Есть ли какой-либо путь вокруг этого или вычисляет все пути, необходимые по определению?

Ответ 1

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

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

Это типичное пространство для скоростной торговли.

Ответ 2

Вы можете попробовать выполнить параллелизм с помощью этой параллельной версии карты:

parMap :: (a -> b) -> [a] -> Eval [b]
parMap f xs = map f xs `using` parList rseq

Затем вы будете запускать новый поток для каждого выбора в своей ветке.

если вы используете как parMap pathFunction kalahaPots как свою рекурсию, она заработает много потоков, но может быть быстрее, вы можете ее обрезать, но я не настолько хорош в параллельном haskeller.