Путешествия во времени, программирование, фракталы миров
Введение
Прочитав статьи TimeCoder — «Путешествия во времени и программирование» [1, 2] я вспомнил свои скромные практические исследования в программировании, связанные с реализацией разветвляющихся миров. Однажды товарищ по работе подкинул мне интересную задачу, но решить я ее до сих пор не смог. Задача о том, как нагрузить станки на производстве. Даже не программисту было понятно, что нужен простой перебор, но я так и не смог придумать подходящую структуру данных для обеспечения вычисляющего алгоритма. Задача из реального мира, поэтому я решил попробовать реализовать в программе реальный мир в той части, который требуется для вычисления задачи. Каждый раз, когда в дальнейших вычислениях стоял выбор между двумя действиями — происходило «создание двух новых миров» с разным решением в каждом. Дальше каждый мир развивался своим путем.Под катом я расскажу, как развивалась идея, и чем мне помог ерланг. Практика — критерий истины!
Содержание Терминология — Древо ВременПервые проблемыВспомнить то, что уже было проделаноСхождения мировМетодологияШаг 1. Уложить описание любого состояния мира в кортежШаг 2. Описать функцию, которая определяет достиг ли мир целиШаг 3. Описать функцию, которая определяет нужно ли дальнейшее развитие мируШаг 4. Описать функцию ветвления мираШаг 5. Описать функцию вычисления ХЭШа мираОстальные функцииФреймворк версии №1Применение фреймворка №1 для решения задачРасчет вариантов выдачи 120 рублей разными бумажкамиРасчет счастливых билетиковРасчет счастливых билетиков, попытка №2Задача «Волк, коза и капуста«Минутка юмораВыводыСписок использованных источниковТерминология — Древо Времен Головачёв называет такое представление развития истории мира — Древом Времен или фракталом [3]. Далее метод поиска результата с помощью данного подхода я буду называть «методом Древа Времен».Мир — это перечень свойств мира и их значений, задающих его состояние.
Решение задачи — решая задачу методом Древа Времен мы заранее знаем результат, либо значения определенных свойств мира, которые мы хотим получить. То есть результат нам известен, но неизвестен путь его получения. Решение задачи — это нахождение пути.
Начальный мир — точка отсчета, мир, с которого мы начинаем свой путь в решении задачи.
Целевой мир — мир (а если точнее, то его состояние) к которому мы стремимся при решении задачи.
Развитие мира — развивая изначальный мир мы стремимся достичь целевого мира.
Тупиковый мир — не тупиковая ветвь, а тупиковый мир. Это мир, дальнейшее развитие которого не приведет к целевому миру.
Первые проблемы Для проверки методики выбрал задачу типа подбора купюр до заданной суммы или поиска счастливых билетиков. В каждом случае написал рекурсивные функции поиска результата. Сделал класс, хранящий экземпляр мира и всего его состояния. Возможности создавать копию мира, я пока не стал. Задачи простые и входной параметр полностью описывает скромный мир. Но даже на таких простых задачах стали понятны все минусы такого подхода. Ветви развития расширяются очень быстро.Во сне мне пришла аналогия с атомным реактором и делением частиц в нем. Происходит деление и цепная реакция, в итоге взрыв. Чтобы взрыва не было процесс деления контролируется. Стало понятно, что процесс создания новых веток миров надо контролировать, причем очень жестко: если мир не приводит к нужному результату — мы его уничтожаем, если мир достиг цели своего развития — выводим результат. Вывод результата показал, что путь достижения результата тоже нужно контролировать и уничтожать миры со слишком дорогим путем (выдача 1000 рублей 10-ти рублевыми купюрами. Еще одной проблемой стало обнаружение нескольких одинаковых результатов. Разные пути развития миров могут в итоге привести к одинаковому результату.
Таким образом, при вычислениях методом Древа Времен нужно решать следующие проблемы:
Ограничивать бездумное распараллеливание реальностей, потому что ресурсы ограничены Анализировать путь к получению результата, если мы достигли мира «тяжелым» путем или путем, который нам не нужен — дальше не идти Надо что-то делать с дублями результатов. Фактически, разные миры разными путями могут прийти к одному состоянию — что с этим делать? Давняя история с вычислением результатов «методом Древа Времен» до поры лежала у меня «в столе». Потому что не все проблемы вычислений были решены. Да и понятно, что пора уже применять параллельные вычисления, новые, отличные от привычных мне языков программирования. Но простых решений не было.
Время идет, технологии в области программирования развиваются. Стало ясно, что повышать мегагерцы бесконечно нельзя. Нужно распараллеливать вычисления. И такие возможности стали появляться, поддержка параллельности в языках стала упрощаться.
Но что же с клонами миров? Дело с мертвой точки сдвинули статьи TimeCoder. Нужно уметь не только разделять ветви развития миров, но и соединять между собой.
Вооружившись новыми новыми идеями и инструментами, я решил вернуться к исследованиям Деревьев Времен.
Вспомнить то, что уже было проделано Задача — счастливые билетики. Билетик будем считать счастливым, если у него сумма первых трех цифр равна сумме остальных.Си QT [4]:
void bilet (int x1, int x2, int x3, int x4, int x5, int x6) { //проверка достижения результата if ((x1+x2+x3)==(x4+x5+x6)) { qDebug () << x1<< x2<< x3<< x4<< x5<< x6; } //новые ветки if((x1+1)<3) bilet(x1 + 1, x2, x3, x4, x5, x6); if((x2+1)<10) bilet(x1, x2 + 1, x3, x4, x5, x6); if((x3+1)<10) bilet(x1, x2, x3 + 1, x4, x5, x6); if((x4+1)<10) bilet(x1, x2, x3, x4 + 1, x5, x6); if((x5+1)<10) bilet(x1, x2, x3, x4, x5 + 1, x6); if((x6+1)<3) bilet(x1, x2, x3, x4, x5, x6 + 1); }
//запуск bilet (0, 0, 0, 0, 0, 0); Дожидаться результата я не стал. Долго. Поэтому часть кода убрал:
void bilet (int x1, int x2, int x3, int x4, int x5, int x6) { //проверка достижения результата if ((x1+x2+x3)==(x4+x5+x6)) { qDebug () << x1<< x2<< x3<< x4<< x5<< x6; } //новые ветки if((x1+1)<3) bilet(x1 + 1, x2, x3, x4, x5, x6); if((x6+1)<3) bilet(x1, x2, x3, x4, x5, x6 + 1); } Результат был следующим: 000000 200002 100001 200002 200002 100001 200002 200002 200002 Алгоритм не подвергался никакой оптимизации. Особо не продуман. И результат соответствующий — дубли.Задача — размен денег. Пусть есть купюры 1000, 500, 100, 50, 10 рублей. Надо посчитать варианты выдачи.
Erlang [5,6]:
Файл we01.erl:
-module (we01). -export ([sum_money/6, sum_money/1]).
sum_money (Itog) → sum_money (Itog, 0, 0, 0, 0, 0).
sum_money (Itog, X1000, X500, X100, X50, X10) → if ((X1000 + X500 + X100 + X50 + X10) > 100) → ok; (Itog == ((1000*X1000)+(500*X500)+(100*X100)+(50*X50)+(10*X10))) → io: format («Itog (~w)(~w) = 1000*~w + 500*~w + 100*~w + 50*~w + 10*~w ~n», [Itog,(X1000 + X500 + X100 + X50 + X10), X1000, X500, X100, X50, X10]); (Itog > ((1000*X1000)+(500*X500)+(100*X100)+(50*X50)+(10*X10))) → sum_money (Itog, 1+X1000, X500, X100, X50, X10), sum_money (Itog, X1000, 1+X500, X100, X50, X10), sum_money (Itog, X1000, X500, 1+X100, X50, X10), sum_money (Itog, X1000, X500, X100, 1+X50, X10), sum_money (Itog, X1000, X500, X100, X50, 1+X10); (true) → ok end. Как запустить этот файл на Erlang?
Запускаем Эрланг: erl Компилируем модуль: c (we01). Запускаем расчет выдачи на 120 рублей: we01: sum_money (120). Результат: Itog (120)(3) = 1000×0 + 500×0 + 100×1 + 50×0 + 10×2 Itog (120)(4) = 1000×0 + 500×0 + 100×0 + 50×2 + 10×2 Itog (120)(4) = 1000×0 + 500×0 + 100×0 + 50×2 + 10×2 Itog (120)(4) = 1000×0 + 500×0 + 100×0 + 50×2 + 10×2 Itog (120)(8) = 1000×0 + 500×0 + 100×0 + 50×1 + 10×7 Itog (120)(3) = 1000×0 + 500×0 + 100×1 + 50×0 + 10×2 Itog (120)(4) = 1000×0 + 500×0 + 100×0 + 50×2 + 10×2 Itog (120)(4) = 1000×0 + 500×0 + 100×0 + 50×2 + 10×2 Itog (120)(8) = 1000×0 + 500×0 + 100×0 + 50×1 + 10×7 Itog (120)(3) = 1000×0 + 500×0 + 100×1 + 50×0 + 10×2 Itog (120)(4) = 1000×0 + 500×0 + 100×0 + 50×2 + 10×2 Itog (120)(8) = 1000×0 + 500×0 + 100×0 + 50×1 + 10×7 Itog (120)(8) = 1000×0 + 500×0 + 100×0 + 50×1 + 10×7 Itog (120)(8) = 1000×0 + 500×0 + 100×0 + 50×1 + 10×7 Itog (120)(8) = 1000×0 + 500×0 + 100×0 + 50×1 + 10×7 Itog (120)(8) = 1000×0 + 500×0 + 100×0 + 50×1 + 10×7 Itog (120)(8) = 1000×0 + 500×0 + 100×0 + 50×1 + 10×7 Itog (120)(12) = 1000×0 + 500×0 + 100×0 + 50×0 + 10×12 ok ^ | ±--- количество купюр Очевидно, что надо как-то игнорировать дубли (одинаковые миры). Натренированный на правильное программирование мозг сразу же начинает размышлять о том, как нужно оптимизировать алгоритм, чтобы такого не происходило, оптимизации, оптимизации… На самом деле это очень простой пример, но даже тут становится сложно придумать оптимизацию. А что будет в более сложных мирах? В общем, если такая возможность есть, то не нужно плодить очевидно лишние миры, во всех остальных случаях надо придумывать методы схождения миров.
Схождения миров Попробуем при попадении в мир проверять есть ли такой. Если есть, то ничего больше не делать (не создавать дочерних миров).Итак, QT, задача опять та же — билетики:
QHash hash; //хэш для хранения миров
void bilet (int x1, int x2, int x3, int x4, int x5, int x6) { int result = x1×100000+x2×10000+x3×1000+x4×100+x5×10+x6;
if (hash.contains (result)) { //вывод поскипанного мира. такой уже есть //qDebug () << x1<< x2<< x3<< x4<< x5<< x6 << "skip"; return; } else { //нету. добавляем в хеш hash.insert(result, ((x1+x2+x3)==(x4+x5+x6))); } //проверка достижения результата if ((x1+x2+x3)==(x4+x5+x6)) { //вывод, если нашли //qDebug() << x1<< x2<< x3<< x4<< x5<< x6 << "*"; } else { //вывод, если не нашли //qDebug() << x1<< x2<< x3<< x4<< x5<< x6; } //новые ветки if((x1+1)<10) bilet(x1 + 1, x2, x3, x4, x5, x6); if((x2+1)<10) bilet(x1, x2 + 1, x3, x4, x5, x6); if((x3+1)<10) bilet(x1, x2, x3 + 1, x4, x5, x6); if((x4+1)<10) bilet(x1, x2, x3, x4 + 1, x5, x6); if((x5+1)<10) bilet(x1, x2, x3, x4, x5 + 1, x6); if((x6+1)<10) bilet(x1, x2, x3, x4, x5, x6 + 1); } Для анализа того, в какие миры мы попадаем разремарим вывод, если нашли и если не нашли. Во всех условиях заменим Результат start "00:19:04.394" 0 0 0 0 0 0 * 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 * 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 * 1 1 0 1 1 1 1 1 0 1 0 1 * 1 1 0 0 1 0 1 1 0 0 1 1 * 1 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 * 1 0 1 1 1 1 1 0 1 1 0 1 * 1 0 1 0 1 0 1 0 1 0 1 1 * 1 0 1 0 0 1 1 0 0 1 0 0 * 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 * 1 0 0 0 1 1 1 0 0 0 0 1 * 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 * 0 1 1 1 1 1 0 1 1 1 0 1 * 0 1 1 0 1 0 0 1 1 0 1 1 * 0 1 1 0 0 1 0 1 0 1 0 0 * 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 * 0 1 0 0 1 1 0 1 0 0 0 1 * 0 0 1 0 0 0 0 0 1 1 0 0 * 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 1 0 * 0 0 1 0 1 1 0 0 1 0 0 1 * 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 end "00:19:04.407" В общем строк 64, то есть 2^6, то есть верно. В полном объеме алгоритм работает быстро, примерно 155мс. Распараллелить с помощью QtConcurect навскидку не получилось.А что же Erlang?
Задача та же — перебор билетиков. Но в Erlang нет глобальных переменных. В качестве хранилища у нас будет процесс.
%хранилище списка существующих миров (узкое место, замена глобальной переменной) world_server (World_list) → receive finished → io: format («World server is down~n», []); list → io: format («World list ~w ~n», [World_list]), world_server (World_list); {new_world, PID, New_world, Par} → %ищем новый мир case lists: keymember (New_world, 1, World_list) of true → PID! world_exist, world_server (World_list); % не добавляем мир false → PID! world_new, world_server ([{New_world, Par}|World_list]) % добавляем мир end end.
world_server_start () → register (ws, spawn (? MODULE, world_server, [[]])). world_server_stop () → ws! finished. Как оно работает
Для запуска сервера вызывается функция world_server_start (). Она запускает функцию world_server в новом потоке и связывает ее с именем ws. Функция вызывает рекурсивно сама себя, а в качестве параметра передает список миров. Изначально ей передается [], то есть пустой массив. При работе функция все время ждет сообщений от других процессов:
Если принято сообщение — атом finished, то функция выводит сообщение об остановке и не вызывает себя рекурсивно, тем самым сервер останавливается. Если принято сообщение — атом list, то выводится список миров и работа продолжается (используется для отладки) Если принят кортеж {new_world, PID, New_world, Par}, то это значит, что у сервера спрашивают, есть ли такой мир в списке? Если мир есть, то процессу возвращается сообщение world_exist или world_new, а функция выполняется дальше с добавлением нового мира в список (если такого еще нет) Попадая в функцию мы по сути попадаем в мир. И первым делом выполняем проверку его на существование — отправляем запрос серверу-хранилищу миров. Если получили ответ world_exist, то дальше не работаем (возврат ok). Иначе выводим информацию о мире (со звездочкой, если он целевой — билет счастливый).
new_ww (X1, X2, X3, X4, X5, X6) → ws! {new_world, self (), X1×10+X2×100+X3×1000+X4×10000+X5×100000+X6×1000000, (X1+X2+X3 == X4+X5+X6) }, receive world_exist → ok; world_new → if (X1+X2+X3 == X4+X5+X6) → io: format (»~w ~w ~w ~w ~w ~w *~n», [X1, X2, X3, X4, X5, X6]); true→ io: format (»~w ~w ~w ~w ~w ~w ~n», [X1, X2, X3, X4, X5, X6]) end, if ((X1+1) < 10) -> new_ww (X1+1, X2, X3, X4, X5, X6); true → ok end, if ((X2+1) < 10) -> new_ww (X1, X2+1, X3, X4, X5, X6); true → ok end, if ((X3+1) < 10) -> new_ww (X1, X2, X3+1, X4, X5, X6); true → ok end, if ((X4+1) < 10) -> new_ww (X1, X2, X3, X4+1, X5, X6); true → ok end, if ((X5+1) < 10) -> new_ww (X1, X2, X3, X4, X5+1, X6); true → ok end, if ((X6+1) < 10) -> new_ww (X1, X2, X3, X4, X5, X6+1); true → ok end end. Что в итоге мы получили от новых технологий в виде Erlang? Пока ничего:
считается дольше, чем на С++ QT
нет никаких распараллеливаний и многомашинных вычислений
нет изящного и компактного кода, присущего ФП, вместо этого простыни однотипного кода
в целом, рекурсивной функцией решен простой перебор значений, который в процедурных языках решается циклами проще и понятнее. не все понимают и любят рекурсии
Что же делать? Нужна методология! Простая, пошаговая, понятная даже школьнику.Методология
После экспериментов я пришел к выводу, что определенные части кода получаются одинаковыми для любых расчетов, меняются только условия. Поэтому при постановке задачи и ее программировании можно полностью отстраниться от рекурсий, распараллеливания и других технических ухищрений и сосредоточиться на задании условий для вычисления. То есть, создать некий фреймворк для расчета. В методологиях erlang это называется behaviour. Суть в том, что для реализации, например, сервера, нужно реализовать его поведение: что делать при старте, остановке и т.д.
Что это дает? Каждое поведение — это одна простая и понятная функция. Чистая функция, результат работы которой зависит только от входных данных. Ее можно проверить независимо от других.
Таким образом, появился фреймворк версии №1. Для того, чтобы решить задачу, нужно пройти шаги
Шаг 1. Уложить описание любого состояния мира в кортеж Важным моментом в программировании вычислений по Деревьям Времен является соглашение о том, как хранить описание мира. То, что в фантастике называют «матрица мира». Описание мира содержит информацию о состоянии мира в данный момент, но только то, что требуется.В более ранних своих исследованиях по Деревьям Времен я пробовал использовать классы, поля, но программирование под каждую отдельную задачу заставляло делать много кода, который быстро переставал быть понятным и универсальным. Поэтому описывать мир нужно как можно проще.
Соглашение об описании мира: мир должен быть описан одним кортежем.
Кортеж — это набор значений ограниченной длины. Кортеж ограничивается фигурными скобками, а элементы кортежа отделяются друг от друга запятыми. Кортежи могут быть вложенными друг в друга.
Пример 1. Кортеж, описывающий состояние мира в начальный момент времени при расчете вариантов счастливых билетиков.
{0,0,0,0,0,0} Каждая цифра — это отдельная цифра в номере билета.Более правильно было бы написать не «в начальный момент времени», а «в начальном состоянии мира», потому что для данного мира время не имеет значения. Имеет значение только состояние мира. Если время в том виде, в котором мы привыкли его понимать, будет иметь значение для расчетов, то оно будет добавлено как еще одно значение в кортеже.
Пример 2. Кортеж, описывающий состояние мира, при котором мы нашли способ выдать 120 рублей в виде 1×100р и 2×10р. Видов банкнот у нас пять: 1000, 500, 100, 50, 10. Поэтому и параметров у мира будет пять. Решено так, что следовать они будут от большего к меньшему, то есть первое число — это кол-во 1000 рублевых и т.д.
{0,0,1,0,2} Шаг 2. Описать функцию, которая определяет достиг ли мир цели Функции в качестве параметра передается мир. Её задача — определить, является ли он целевым. Если да, то выводить результат и возвращать true. Иначе false. Если мир достиг цели, то фреймворку, очевидно, не нужно дальше его развивать. Дальнейшее развитие мира в комбинаторной задаче может привести к другим решениям.Шаг 3. Описать функцию, которая определяет нужно ли дальнейшее развитие миру Функции в качестве параметра передается мир. Её задача — определить, нужно ли дальше его развивать. Если дальнейшее развитие мира не может привести к цели, то и развивать его дальше не имеет смысла. Тупиковая ветвь. Если развитие нужно, возвращаем true. Иначе false. В то же время если дальнейшее развитие мира — тупик, то это не значит, что мир не может быть целевым.Шаг 4. Описать функцию ветвления мира Развитие мира может пойти разными направлениями. Функции в качестве параметра передается мир. В ответ выдается список миров, в которые можно развиться из данного мира.Шаг 5. Описать функцию вычисления ХЭШа мира По умолчанию функция вычисления ХЭШа мира имеет следующий вид: %%хеш мира w2hash (Wrld) → erlang: phash2(Wrld). Стандартная функция erlang: phash2 выдает хэш — число по переданному кортежу. Но не всегда требуется точное соответствие одного мира другому. Об этом написано в статьях [1, 2], суть в том, что независимо от того, какие были приняты промежуточные решения, прийти можно к одному результату и ветви развития сойдутся. Миры сойдутся не «с точностью до атома», а сойдутся в контексте решения задачи. Если задача — добраться на работу на машине, то можно приехать разными дорогами, но в 12 часов мы будем на совещании. Разница, конечно, будет в пробеге у машины, но этот момент для нас не имеет значения.Схождение миров во фреймворке №1 реализуется через хранилище уже созданных миров. Вернее, хеш-чисел этих миров. И если мир, в который мы попали в процессе развития какой-либо ветви, уже существует в хранилище, то дальнейшее развитие мира не происходит. По сути дела происходит схождение миров, потому что два пути развития миров пришли к одному результату и дальше пошли одной дорогой. Поэтому, если какие-то из параметров мира не влияют на результат, то нужно скорректировать функцию вычисления хэша мира, чтобы этот параметр не участвовал в преобразовании кортеж→хэш-число.
Остальные функции Такие функции, как перебор, миров, схождение миров, для любой задачи будут одинаковы. Они будут входить во фреймворк и пользователю их менять/понимать не обязательно. И если точно придерживаться методологии, то фреймворк можно совершенствовать в плане параллельных вычислений, не меняя при этом функций, задающих правила мира.Фреймворк версии №1 wf1.erl
-module (wf1).
-export ([start/0, stop/0, br/1, is_target/1, is_dead/1, ent/1, lib/0]).
%%хеш мира w2hash (Wrld) → erlang: phash2(Wrld).
%%хранилище миров lib () → lib ([]). lib (List) → receive stop → ok; {Wrld, Pid} → WHash = w2hash (Wrld), NewList = case lists: member (WHash, List) of false → Pid! ok, [WHash]++List; true → Pid! exist, List end, lib (NewList); _ → ok end. ent ([]) → ok;
%%на вход подается список кортежей миров, список делится на первый мир в списке Wrld %%и на хвост Tail из оставшихся ent ([Wrld|Tail]) → try spawn (? MODULE, ent, [Wrld]) of _Pid → ent (Tail) catch _:_ → io: format («spawn overload~n», []), ent (Wrld), ent (Tail) end;
%%на вход подается кортеж одного мира ent (Wrld) → lib_srv! {Wrld, self ()}, %% проверяем существует ли такой мир уже receive ok → is_target (Wrld), %% является ли целевым Is_dead = is_dead (Wrld), %% является ли тупиком if (Is_dead==false) → %% если не тупик — плодим ветки и идем в них NewBranches = br (Wrld), ent (NewBranches); true → ok end; exist → ok end. stop () → lib_srv! stop.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% функции, определяемые пользователем %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%Мир достиг цели? is_target (Wrld) → true.
%%Мир — тупиковая ветвь is_dead (Wrld) → false.
%%Ветвление мира
br (Wrld) →
[].
%%запуск расчета
start () →
register (lib_srv, spawn (? MODULE, lib, [])),
io: format («start~n», []),
%% внутри [] нужно передать начальный мир
spawn (? MODULE, ent, [[]]).
Применение фреймворка №1 для решения задач
Расчет вариантов выдачи 120 рублей разными бумажками
Шаг 1 — Уложить мир в кортеж
Мир описывается пятью цифрами
{0,0,0,0,0} Шаг 2. Описать функцию, которая определяет достиг ли мир цели
%%Мир достиг цели? is_target (Wrld) → {X1000, X500, X100, X50, X10} = Wrld, if ((X1000×1000 + X500×500 + X100×100 + X50×50 + X10×10)==120) → io: format (»120 (~w) = 1000p*~w 500p*~w 100p*~w 50p*~w 10p*~w~n», [X1000+X500+X100+X50+X10, X1000, X500, X100, X50, X10]); true → ok end, (X1000×1000 + X500×500 + X100×100 + X50×50 + X10×10)==120. Небольшое примечание по синтаксису Erlang. Самая первая операция — это не присваивание, а матчинг. В переменной Wrld находится кортеж с пятью элементами. При выполнении операции, значения элементов в кортеже присвоятся переменным X1000, X500, X100, X50, X10. Более подробно про матчинг в Erlang, пожалуйста, прочитайте самостоятельно. Либо просто примите такой синтаксис, как способ вытащить значения из кортежа.Шаг 3. Описать функцию, которая определяет нужно ли дальнейшее развитие миру
%%Мир — тупиковая ветвь is_dead (Wrld) → {X1000, X500, X100, X50, X10} = Wrld, (X1000×1000 + X500×500 + X100×100 + X50×50 + X10×10)>120. Шаг 4. Описать функцию ветвления мира
%%Ветвление мира br (Wrld) → {X1000, X500, X100, X50, X10} = Wrld, [ {X1000+1, X500, X100, X50, X10}, {X1000, X500+1, X100, X50, X10}, {X1000, X500, X100+1, X50, X10}, {X1000, X500, X100, X50+1, X10}, {X1000, X500, X100, X50, X10+1} ]. Запуск расчета
%%запуск расчета start () → register (lib_srv, spawn (? MODULE, lib, [])), io: format («start~n», []), %% внутри [] нужно передать начальный мир spawn (? MODULE, ent, [{0,0,0,0,0}]). В итоге получили:
1> c (wf1).
{ok, wf1}
2> wf1: start ().
start
<0.455.0>
120 (3) = 1000×0 500×0 100×1 50×0 10×2
120 (4) = 1000×0 500×0 100×0 50×2 10×2
120 (8) = 1000×0 500×0 100×0 50×1 10×7
120 (12) = 1000×0 500×0 100×0 50×0 10×12
Расчет счастливых билетиков
Шаг 1 — Уложить мир в кортеж
Мир описывается шестью цифрами
{0,0,0,0,0,0} Шаг 2. Описать функцию, которая определяет достиг ли мир цели
%%Мир достиг цели? is_target (Wrld) → {X1, X2, X3, X4, X5, X6} = Wrld, if ((X1+X2+X3)==(X4+X5+X6)) → cnt_srv! inc, cnt_srv! {cnt, self ()}, receive X → ok end, io: format (»~w ~w ~w ~w ~w ~w (~w)~n», [X1, X2, X3, X4, X5, X6, X]); true → ok end, ((X1+X2+X3)==(X4+X5+X6)). Шаг 3. Описать функцию, которая определяет нужно ли дальнейшее развитие миру
%%Мир — тупиковая ветвь is_dead (Wrld) → {X1, X2, X3, X4, X5, X6} = Wrld, if (X1>9)→ true; (X2>9)→ true; (X3>9)→ true; (X4>9)→ true; (X5>9)→ true; (X6>9)→ true; true → false end. Шаг 4. Описать функцию ветвления мира
%%Ветвление мира br (Wrld) → {X1, X2, X3, X4, X5, X6} = Wrld, [ {X1+1, X2, X3, X4, X5, X6}, {X1, X2+1, X3, X4, X5, X6}, {X1, X2, X3+1, X4, X5, X6}, {X1, X2, X3, X4+1, X5, X6}, {X1, X2, X3, X4, X5+1, X6}, {X1, X2, X3, X4, X5, X6+1} ]. Для подсчета количества счастливых билетиков сделаем еще один сервер, который будет хранить, увеличивать и отдавать кол-во найденных миров с положительным результатом:
%%кол-во результатов cnt () → cnt (0).
cnt (N) → receive inc → cnt (N+1); {cnt, Pid} → Pid! N, cnt (N) end. При запуске расчета стартуем и его тоже:
%%запуск расчета start () → register (lib_srv, spawn (? MODULE, lib, [])), register (cnt_srv, spawn (? MODULE, cnt, [])), io: format («start~n», []), %% внутри [] нужно передать начальный мир spawn (? MODULE, ent, [{0,0,0,0,0,0}]). Но если задать правила таким образом, то ждать результата придется очень долго. Процессов создается так много, что нода Erlang перестает справляться с таким количеством и перестает создавать новые процессы. И это хорошо, потому что пришлось найти решение и этой проблемы (через try).
Очевидно, что ветвление миров задано не лучшим образом и получается, что одинаковые миры создаются многократно, постоянно идут проверки и выясняется, что миры уже были. Это наводит на мысли о том, что в таких ресурсоемких задачах все же придется применять головной мозг.
Расчет счастливых билетиков, попытка №2
Решение задачи счастливых билетиков оказалось весьма полезным занятием. В процессе решения выяснился ряд очень важных нъюансов по каждому шагу, потребовал корректировки основной цикл обработки миров. И даже выявилась необходимость в шаге №5 (которого изначально не было).
Прошлая попытка решения задачи с билетиками показала нам, что мы не эффективно выполняли ветвления миров, что приводило к большому количеству дублей. А ведь нет никакой проблемы рассчитать все варианты развития мира сразу из изначального состояния. Но у нас же Эрланг, поэтому мы сделаем это рекурсивно, методом деления отрезка пополам. Отрезок у нас будет от 0 до 999999, будем его делить до тех пор, пока границы диапазонов не совпадут. Поэтому свойств мира станет на два больше: добавится левая и правая граница. В то же время эти границы нужны только для рекурсивной функции вычисления списка миров и на результат не влияют. Более того, деление отрезка пополам у нас целочисленное и где-то в алгоритме я допустил ошибку, которая дает нам одинаковые миры на разных отрезках. Поэтому потребуется корректировка вычисления хэша мира.
Шаг 1 — Уложить мир в кортеж
Первые два параметра — диапазон. Остальное — как раньше — цифры.
{0,999999,0,0,0,0,0,0} Шаг 2. Описать функцию, которая определяет достиг ли мир цели
%%Мир достиг цели? is_target (Wrld) → {_St_d,_En_d, X1, X2, X3, X4, X5, X6} = Wrld, if ((X1+X2+X3)==(X4+X5+X6)) → cnt_srv! inc, cnt_srv! {cnt, self ()}, receive X → ok end, io: format (»~w ~w ~w ~w ~w ~w (~w)~n», [X1, X2, X3, X4, X5, X6, X]); true → ok end, ((X1+X2+X3)==(X4+X5+X6)). Шаг 3. Описать функцию, которая определяет нужно ли дальнейшее развитие миру
Развития миров в данном варианте расчета не предполагается, потому что мы сразу знаем все варианты развития. То есть у развития только один шаг — самый первый шаг, когда указан диапазон 0 — 999999. Когда диапазон у нас разложен в список, развития мира быть уже не должно. Мир — тупик всегда, кроме первого шага.
%%Мир — тупиковая ветвь is_dead (Wrld) → {St_d, En_d,_X1,_X2,_X3,_X4,_X5,_X6} = Wrld, (St_d == En_d). Шаг 4. Описать функцию ветвления мира
%%Ветвление мира br (Wrld) → {St_d, En_d, X1, X2, X3, X4, X5, X6} = Wrld, THalf = round ((St_d + En_d) / 2), if (St_d == En_d) → []; ((En_d — St_d) == 1) → XX6 = En_d rem 10, XX5 = trunc ((En_d rem 100)/10), XX4 = trunc ((En_d rem 1000)/100), XX3 = trunc ((En_d rem 10000)/1000), XX2 = trunc ((En_d rem 100000)/10000), XX1 = trunc ((En_d rem 1000000)/100000), [{St_d, St_d, XX1, XX2, XX3, XX4, XX5, XX6}] ++ [{En_d, En_d, XX1, XX2, XX3, XX4, XX5, XX6}]; true → br ({St_d, THalf, X1, X2, X3, X4, X5, X6}) ++ br ({THalf, En_d, X1, X2, X3, X4, X5, X6}) end. Шаг 5. Описать функцию ХЭШа мира
%%хеш мира w2hash (Wrld) → {_St_d,_En_d, X1, X2, X3, X4, X5, X6} = Wrld, X1×100000 + X2×10000 + X3×1000 + X4×100 + X5×10 + X6. Либо можно собрать кортеж, но без диапазона %%хеш мира w2hash (Wrld) → {_St_d,_En_d, X1, X2, X3, X4, X5, X6} = Wrld, erlang: phash2({X1, X2, X3, X4, X5, X6}). Запуск
%%запуск расчета start () → register (lib_srv, spawn (? MODULE, lib, [])), register (cnt_srv, spawn (? MODULE, cnt, [])), io: format («start~n», []), %% внутри [] нужно передать начальный мир spawn (? MODULE, ent, [{0,999999,0,0,0,0,0,0}]). Итог
В процессе выполнения программа выдала список счастливых билетов, которых оказалось 55252. Сошлось, ура!!!
Время вычисления результата не радует: в 16:49 начали расчет, а закончили в 17:23. То есть более 30 минут. Но что дало решение задачи с билетами и что пришлось преодолеть? В первую очередь это один миллион миров в хранилище. Изначально я записывал в хранилище не хэши миров, а прямо кортежи мира. При поиске в списке с таким количеством записей мы уже начинаем сталкиваться с большими задержками. Применение хеша увеличило скорость. А размышления в шаге 5 так же подтвердили правильность применения хешей. Хотя в принципе можно хранить и кортеж мира, но удалив из него не значащую информацию. Кроме того, текущая архитектура показывает, что есть еще резервы для качественного роста в плане производительности, ведь миры, которые нужно рассчитать, даны в массиве и элементы массива миров можно вычислять параллельно, на нескольких нодах Erlang. Все вычисления миров каждый раз запускаются в новом процессе. И теоретически можно достичь максимального количества процессов в виртуальной машине Erlang, что должно привести к ошибке. Вычисление билетиков позволило «упереться» в ограничение, обработать ошибку и убедиться в том, что результат получается верным.
Задача «Волк, коза и капуста»
«Крестьянину нужно перевезти через реку волка, козу и капусту. Но лодка такова, что в ней может поместиться только крестьянин, а с ним или один волк, или одна коза, или одна капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевез свой груз крестьянин?»
Подробнее про задачу, а так же о двух вариантах её решения можно прочитать по ссылке[7].
Шаг 1. Уложить описание любого состояния мира в кортеж
Где (r — правый, l — левый) — берег, на котором находится дед, коза, волк, капуста и предыдущий путь ([] — это список). Для чего список? Нам ведь нужно знать путь, которым мы пришли к результату.
{{ded, r},{koza, r},{volk, r},{kapusta, r},[]} Шаг 2. Описать функцию, которая определяет достиг ли мир цели
%%Мир достиг цели? is_target (Wrld) → {{ded, DedBereg},{koza, KozaBereg},{volk, VolkBereg},{kapusta, KapustaBereg}, History} = Wrld, if ((DedBereg==r) and (KozaBereg==r) and (VolkBereg==r) and (KapustaBereg==r)) → cnt_srv! inc, cnt_srv! {cnt, self ()}, receive X → ok end, io: format (»~w) movs=~w ~w ~n», [X, length (History), History]); true → ok end, ((DedBereg==r) and (KozaBereg==r) and (VolkBereg==r) and (KapustaBereg==r)). То есть, если все на правом берегу — задача решена.
Шаг 3. Описать функцию, которая определяет нужно ли дальнейшее развитие миру
%%Мир — тупиковая ветвь is_dead (Wrld) → {{ded, DedBereg},{koza, KozaBereg},{volk, VolkBereg},{kapusta, KapustaBereg}, History} = Wrld, if (length (History) > 8) → true; ((KozaBereg==VolkBereg)and (DedBereg/=KozaBereg)) → true; %%волк съел козу, если дед на другом берегу ((KozaBereg==KapustaBereg)and (DedBereg/=KozaBereg)) → true; %%коза съела капусту, если дед на другом берегу true → false end. Если дед слишком долго катается туды-сюды, то это тупик.
Если берег у козы и волка совпадает, а деда рядом с ними нет (дед на другом берегу), то волк скушает козу.
Если берег у козы и капусты совпадает, а деда рядом с ними нет (дед на другом берегу), то коза скушает капусту.
В остальных случаях можно жить дальше и надеяться на будущее.
Шаг 4. Описать функцию ветвления мира
Вот тут сразу не получилось, потому что решил помудрить и упростил. А упрощать ничего не надо. Надо вот как есть — так все и делать.
сначала напишу функцию, которая возвращает противоположный берег от переданного (она нам пригодится ниже):
na_drugoi_bereg (l) → r; na_drugoi_bereg® → l. Строим список вариантов развития по переданному миру. Но перед этим добавляем переданный мир в список — историю. Нам ведь нужно знать путь, которым мы пришли к результату.
%%Ветвление мира br (Wrld) → {{ded, DedBereg},{koza, KozaBereg},{volk, VolkBereg},{kapusta, KapustaBereg}, History} = Wrld, NewHistory = History ++ [{{ded, DedBereg},{koza, KozaBereg},{volk, VolkBereg},{kapusta, KapustaBereg}}], %%каждый раз, дед однозначно переплывает с берега на берег %%но перевезти с собой на другой берег он сможет только того, кто с ним сейчас на одном берегу %%либо он плывет один, не взяв никого %%есть коза — везем её, иначе вариант не вариант if (DedBereg==KozaBereg) → Variant1 = {{ded, na_drugoi_bereg (DedBereg)},{koza, na_drugoi_bereg (KozaBereg)},{volk, VolkBereg},{kapusta, KapustaBereg}, NewHistory}; true → Variant1 = [] end,
%%есть волк — везем его, иначе вариант не вариант if (DedBereg==VolkBereg) → Variant2 = {{ded, na_drugoi_bereg (DedBereg)},{koza, KozaBereg},{volk, na_drugoi_bereg (VolkBereg)},{kapusta, KapustaBereg}, NewHistory}; true → Variant2 = [] end,
%%есть капуста — везем её, иначе вариант не вариант if (DedBereg==KapustaBereg) → Variant3 = {{ded, na_drugoi_bereg (DedBereg)},{koza, KozaBereg},{volk, VolkBereg},{kapusta, na_drugoi_bereg (KapustaBereg)}, NewHistory}; true → Variant3 = [] end,
%%никого не везем — едем порожняком — вполне себе вариант Variant4 = {{ded, na_drugoi_bereg (DedBereg)},{koza, KozaBereg},{volk, VolkBereg},{kapusta, KapustaBereg}, NewHistory},
%%при сложении списков получается список [Variant1]++[Variant2]++[Variant3]++[Variant4]. Шаг 5. Описать функцию вычисления ХЭШа мира
Нам вполне подойдет стандартный ХЭШ по миру.
%%хеш мира w2hash (Wrld) → erlang: phash2(Wrld). А если мы будем вычислять только хэш итогового мира? Да он нам, в общем-то и не нужен. Итог мы и так знаем — все на правом берегу. Нам важен путь — значение массива истории. Поэтому перед вычислением хеша мира нет смысла из него что-то убирать.
Запуск
%%запуск расчета start () → register (lib_srv, spawn (? MODULE, lib, [])), register (cnt_srv, spawn (? MODULE, cnt, [])), io: format («start~n», []), %% внутри [] нужно передать начальный мир spawn (? MODULE, ent, [{{ded, l},{koza, l},{volk, l},{kapusta, l},[]}]). Анализ результата
Вариантов решения задачи получилось несколько, в заданном количестве перемещений деда через реку. Среди них самые короткие решения — это за 7 движений. Таких решений два, как и пишут в статье[7].
1) movs=7 [ {{ded, l},{koza, l},{volk, l},{kapusta, l}}, — все на левом берегу {{ded, r},{koza, r},{volk, l},{kapusta, l}}, — перевез козу на правый берег {{ded, l},{koza, r},{volk, l},{kapusta, l}}, — вернулся на левый берег {{ded, r},{koza, r},{volk, r},{kapusta, l}}, — перевез волка на правый берег {{ded, l},{koza, l},{volk, r},{kapusta, l}}, — вернулся на левый берег вместе с козой {{ded, r},{koza, l},{volk, r},{kapusta, r}}, — перевез капусту на правый берег {{ded, l},{koza, l},{volk, r},{kapusta, r}}] — вернулся на левый берег за козой, чтобы перевезти ее на правый берег 5) movs=7 [ {{ded, l},{koza, l},{volk, l},{kapusta, l}}, — все на левом берегу {{ded, r},{koza, r},{volk, l},{kapusta, l}}, — перевез козу на правый берег {{ded, l},{koza, r},{volk, l},{kapusta, l}}, — вернулся на левый берег {{ded, r},{koza, r},{volk, l},{kapusta, r}}, — перевез капусту на правый берег {{ded, l},{koza, l},{volk, l},{kapusta, r}}, — вернулся на левый берег вместе с козой {{ded, r},{koza, l},{volk, r},{kapusta, r}}, — перевез волка на правый берег {{ded, l},{koza, l},{volk, r},{kapusta, r}}] — вернулся на левый берег за козой, чтобы перевезти ее на правый берег Другие варианты требуют больше движений, но очевидно, что эти телодвижения будут бессмысленными:
2) movs=9 [
{{ded, l},{koza, l},{volk, l},{kapusta, l}}, — все на левом берегу
{{ded, r},{koza, r},{volk, l},{kapusta, l}}, — отвез козу на правый берег
{{ded, l},{koza, r},{volk, l},{kapusta, l}}, — вернулся на левый берег
{{ded, r},{koza, r},{volk, r},{kapusta, l}}, — отвез волка на правый берег
{{ded, l},{koza, l},{volk, r},{kapusta, l}}, — вернулся на левый вместе с козой
{{ded, r},{koza, l},{volk, r},{kapusta, r}}, — отвез капусту на правый берег
{{ded, l},{koza, l},{volk, r},{kapusta, l}}, — отвез капусту обратно на левый
{{ded, r},{koza, l},{volk, r},{kapusta, r}}, — отвез еще раз капусту на правый берег
{{ded, l},{koza, l},{volk, r},{kapusta, r}}] — вернулся за козой
Минутка юмора
Картинка — иллюстрация метода Древа Времен
Американская версия задачи про волка, козу и капусту
Выводы Подводя итог, можно сказать, что метод действительно может быть использован для расчетов, а язык erlang, как инструмент, дал все необходимые возможности для реализации метода на практике. Разработана методика и фреймворк для упрощения программирования расчетов данным методом.Критика метода.Метод антинаучен с математической точки зрения. Для решения задач, например, по загрузке производства могут быть применены Теории Массового Обслуживания и т.д. Суть же метода заключается в переборе вариантов (метод «грубой силы»), который бессмысленно тратит огромные вычислительные ресурсы и может не найти решения, если область вычисления плохо ограничить. Хотя, википедия считает brute force методом решения математических задач.
Дальнейшее развитиеКластерные вычисления. Экспериментирую с erlang pool.
Разработка фреймворка №2 для решения другого класса зада, когда сначала строится дерево, а потом находятся решения по нему. Например, AI для реализация игры в крестики нолики. Для нее строится дерево из любых возможных комбинаций в игре в сторону выигрыша. При наступлении хода в игре, AI находит мир в дереве, выбирает одну из ветвей развития, которая приведет мир к выигрышному целевому миру и делает соответствующий шаг.
Список использованных источников 1. Путешествия во времени и программирование — habrahabr.ru/post/150300/2. Путешествия во времени и программирование 2: парадоксы — habrahabr.ru/post/178959/3. Головачев Василий — Палач времен4. qt-project.org/5. Начала работы с Erlang — rsdn.ru/article/erlang/GettingStartedWithErlang.xml6. www.erlang.org/7. Задача «Волк, коза и капуста» — suhin.narod.ru/mat4.htm
