Нет, дамп я не выводил.
Haskell работает со списками лениво. Думаю, что столь медленная скорость работы связана именно с ленивостью вычислений (в совокупности с не самым лучшим выбором структуры данных).
Окей, запишем количество путей следующим образом: n^12, n из промежутка [2,5].
если отключить проверку на то, что следующее состояние уже было ранее, то лодка по кругу будет бесконечно возить одно и то же.
В том то и дело, что бесконечно возить она не будет. Вернее, так: будет возить бесконечно, но решение (хотя бы одно) все-таки найдет.
Смотрите: у нас есть изначальное состояние, с глубиной 0. Из него мы строим три продолжения. Берем первое состояние с глубиной 1, и пробуем продолжить его — получаем состояния с глубиной 2. После получения первых состояний с глубиной 2, мы не пытаемся сразу же продолжить их. Мы должны сначала посетить все состояния с глубиной 1, и попытаться достроить их. В этом смысл поиска в ширину.
Насчет дубликатов — обязательно посмотрю на днях на код еще раз.
не совсем понятно почему так медленно, целая секунда.
Ну, на самом деле это не так уж сложно. Моя программа сделана на списках, а Haskell работает со списками своеобразным образом — для того, скажем, чтобы произвести какую-либо операцию с концом списка (взять последний элемент, или сконкатенировать список с другим списком), он последовательно обойдет каждый элемент. В процессе построения дерева решений мой список списков разрастается неимоверно — после нахождения первых одиннадцати состояний он состоит из (примерно) 5*4^9 путей.
А теперь представьте себе процесс нахождения двенадцатого, финального состояния. Берем первый путь из списка, строим дополнения. Ни одно из них не привело к финальному состоянию -> кладем их в конец списка (последовательно проходим 5*4^9 элементов, и кладем новые построенные пути в конец). Затем берем второй путь. Затем третий. И всякий раз, меняя дерево решений, мы последовательно проходим его полностью. :) Отсюда и медлительность.
C# же, я уверен, хранит в списках указатель на последний элемент — раз. Вы строили список, состоящий из объектов-состояний, ссылающихся на своего родителя (я, кстати, писал эту задачу на python точно так же), а не список путей — два. Потому ваше решение так шустро и отработало.
Тут проблема не в языке, а в том, что я выбрал не самое (самое не) оптимальное решение.
хаскель это интерпретируемый язык?
Программу можно, написанную на нем, можно запустить через интерпретатор runhaskell. А можно получить исполняемый файл через ghc.
Пример: на левом берегу три миссионера и ноль каннибалов.
Ваш вариант проверки дает (3 >= 0) && (0 >= 3) == False. Получается, что состояние небезопасно, хотя это не так.
Все четыре решения находит за 1.2 секунды. Как запустить функцию solve так, чтобы она вернула результат после нахождения первого же решения, я пока не сообразил — монады для меня дремучий лес.:) Но результат получится явно быстрее, чем мое решение, не основанное на этом фреймворке.
Можно конечно, отчего б не написать.:)
Вот и решение.
import RCFramework
prn_M3C3 = (take 6 . cycle) [Actor "Missionaire" 1 True, Actor "Cannibal" 1 True]
rst_M3C3 side = not $ or [3 == f "Cannibal" side && 2 == f "Missionaire" side,
3 == f "Cannibal" side && 1 == f "Missionaire" side,
2 == f "Cannibal" side && 1 == f "Missionaire" side]
where
f nm = (length . filter (\actor -> name actor == nm))
tsk_M3C3 = Crossing
2
prn_M3C3
rst_M3C3
(Here prn_M3C3 [])
(There [] prn_M3C3)
main = do
mapM_ print $ solve tsk_M3C3 []
Вы точно нашли эту фразу именно в той статье, с которой я делал перевод? Потому что я сейчас проверил оригинал и ее там не нашел.
foldl1 (+) list. Сложение происходит не итеративно, а рекурсивно.Haskell работает со списками лениво. Думаю, что столь медленная скорость работы связана именно с ленивостью вычислений (в совокупности с не самым лучшим выбором структуры данных).
В том то и дело, что бесконечно возить она не будет. Вернее, так: будет возить бесконечно, но решение (хотя бы одно) все-таки найдет.
Смотрите: у нас есть изначальное состояние, с глубиной 0. Из него мы строим три продолжения. Берем первое состояние с глубиной 1, и пробуем продолжить его — получаем состояния с глубиной 2. После получения первых состояний с глубиной 2, мы не пытаемся сразу же продолжить их. Мы должны сначала посетить все состояния с глубиной 1, и попытаться достроить их. В этом смысл поиска в ширину.
Насчет дубликатов — обязательно посмотрю на днях на код еще раз.
Ну, на самом деле это не так уж сложно. Моя программа сделана на списках, а Haskell работает со списками своеобразным образом — для того, скажем, чтобы произвести какую-либо операцию с концом списка (взять последний элемент, или сконкатенировать список с другим списком), он последовательно обойдет каждый элемент. В процессе построения дерева решений мой список списков разрастается неимоверно — после нахождения первых одиннадцати состояний он состоит из (примерно) 5*4^9 путей.
А теперь представьте себе процесс нахождения двенадцатого, финального состояния. Берем первый путь из списка, строим дополнения. Ни одно из них не привело к финальному состоянию -> кладем их в конец списка (последовательно проходим 5*4^9 элементов, и кладем новые построенные пути в конец). Затем берем второй путь. Затем третий. И всякий раз, меняя дерево решений, мы последовательно проходим его полностью. :) Отсюда и медлительность.
C# же, я уверен, хранит в списках указатель на последний элемент — раз. Вы строили список, состоящий из объектов-состояний, ссылающихся на своего родителя (я, кстати, писал эту задачу на python точно так же), а не список путей — два. Потому ваше решение так шустро и отработало.
Тут проблема не в языке, а в том, что я выбрал не самое (самое не) оптимальное решение.
Программу можно, написанную на нем, можно запустить через интерпретатор runhaskell. А можно получить исполняемый файл через ghc.
Ваш вариант проверки дает
(3 >= 0) && (0 >= 3) == False. Получается, что состояние небезопасно, хотя это не так.Вот и решение.