Путешествия во времени, программирование, фракталы миров

Введение

Прочитав статьи TimeCoder ^[1] — «Путешествия во времени и программирование» [1, ^[2]2 ^[3]] я вспомнил свои скромные практические исследования в программировании, связанные с реализацией разветвляющихся миров. Однажды товарищ по работе подкинул мне интересную задачу, но решить я ее до сих пор не смог. Задача о том, как нагрузить станки на производстве. Даже не программисту было понятно, что нужен простой перебор, но я так и не смог придумать подходящую структуру данных для обеспечения вычисляющего алгоритма. Задача из реального мира, поэтому я решил попробовать реализовать в программе реальный мир в той части, который требуется для вычисления задачи. Каждый раз, когда в дальнейших вычислениях стоял выбор между двумя действиями — происходило «создание двух новых миров» с разным решением в каждом. Дальше каждый мир развивался своим путем.

Под катом я расскажу, как развивалась идея, и чем мне помог ерланг. Практика — критерий истины!

Содержание

Терминология — Древо Времен ^[4]
Первые проблемы ^[5]
Вспомнить то, что уже было проделано ^[6]
Схождения миров ^[7]
Методология ^[8]
Шаг 1. Уложить описание любого состояния мира в кортеж ^[9]
Шаг 2. Описать функцию, которая определяет достиг ли мир цели ^[10]
Шаг 3. Описать функцию, которая определяет нужно ли дальнейшее развитие миру ^[11]
Шаг 4. Описать функцию ветвления мира ^[12]
Шаг 5. Описать функцию вычисления ХЭШа мира ^[13]
Остальные функции ^[14]
Фреймворк версии №1 ^[15]
Применение фреймворка №1 для решения задач ^[16]
Расчет вариантов выдачи 120 рублей разными бумажками ^[17]
Расчет счастливых билетиков ^[18]
Расчет счастливых билетиков, попытка №2 ^[19]
Задача “Волк, коза и капуста” ^[20]
Минутка юмора ^[21]
Выводы ^[22]
Список использованных источников ^[23]

Терминология — Древо Времен

Головачёв называет такое представление развития истории мира — Древом Времен или фракталом [3]. Далее метод поиска результата с помощью данного подхода я буду называть «методом Древа Времен».

Мир — это перечень свойств мира и их значений, задающих его состояние.

Решение задачи — решая задачу методом Древа Времен мы заранее знаем результат, либо значения определенных свойств мира, которые мы хотим получить. То есть результат нам известен, но неизвестен путь его получения. Решение задачи — это нахождение пути.

Начальный мир — точка отсчета, мир, с которого мы начинаем свой путь в решении задачи.

Целевой мир — мир (а если точнее, то его состояние) к которому мы стремимся при решении задачи.

Развитие мира — развивая изначальный мир мы стремимся достичь целевого мира.

Тупиковый мир — не тупиковая ветвь, а тупиковый мир. Это мир, дальнейшее развитие которого не приведет к целевому миру.

Первые проблемы

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

Во сне мне пришла аналогия с атомным реактором и делением частиц в нем. Происходит деление и цепная реакция, в итоге взрыв. Чтобы взрыва не было процесс деления контролируется. Стало понятно, что процесс создания новых веток миров надо контролировать, причем очень жестко: если мир не приводит к нужному результату — мы его уничтожаем, если мир достиг цели своего развития — выводим результат. Вывод результата показал, что путь достижения результата тоже нужно контролировать и уничтожать миры со слишком дорогим путем (выдача 1000 рублей 10-ти рублевыми купюрами. Еще одной проблемой стало обнаружение нескольких одинаковых результатов. Разные пути развития миров могут в итоге привести к одинаковому результату.

Таким образом, при вычислениях методом Древа Времен нужно решать следующие проблемы:

• Ограничивать бездумное распараллеливание реальностей, потому что ресурсы ограничены
• Анализировать путь к получению результата, если мы достигли мира «тяжелым» путем или путем, который нам не нужен — дальше не идти
• Надо что-то делать с дублями результатов. Фактически, разные миры разными путями могут прийти к одному состоянию — что с этим делать?

Давняя история с вычислением результатов «методом Древа Времен» до поры лежала у меня «в столе». Потому что не все проблемы вычислений были решены. Да и понятно, что пора уже применять параллельные вычисления, новые, отличные от привычных мне языков программирования. Но простых решений не было.

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

Но что же с клонами миров? Дело с мертвой точки сдвинули статьи TimeCoder ^[1]. Нужно уметь не только разделять ветви развития миров, но и соединять между собой.

Вооружившись новыми новыми идеями и инструментами, я решил вернуться к исследованиям Деревьев Времен.

Вспомнить то, что уже было проделано

Задача — счастливые билетики. Билетик будем считать счастливым, если у него сумма первых трех цифр равна сумме остальных.

Си 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?

1. Запускаем Эрланг:

   erl

2. Компилируем модуль:

   c(we01).

3. Запускаем расчет выдачи на 120 рублей:

   we01:sum_money(120).

4. Результат:

   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        ^
             |
             +---- количество купюр
   

Очевидно, что надо как-то игнорировать дубли (одинаковые миры). Натренированный на правильное программирование мозг ^[24] сразу же начинает размышлять о том, как нужно оптимизировать алгоритм, чтобы такого не происходило, оптимизации, оптимизации… На самом деле это очень простой пример, но даже тут становится сложно придумать оптимизацию. А что будет в более сложных мирах? В общем, если такая возможность есть, то не нужно плодить очевидно лишние миры, во всех остальных случаях надо придумывать методы схождения миров.

Схождения миров

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

Итак, 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);
}

Для анализа того, в какие миры мы попадаем разремарим вывод, если нашли и если не нашли. Во всех условиях заменим <10 на <2, чтобы ограничить объем вычислений. Запускаем. Результат:

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) = 1000x0 500x0 100x1 50x0 10x2
120 (4) = 1000x0 500x0 100x0 50x2 10x2
120 (8) = 1000x0 500x0 100x0 50x1 10x7
120 (12) = 1000x0 500x0 100x0 50x0 10x12

Расчет счастливых билетиков

Шаг 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).

Очевидно, что ветвление миров задано не лучшим образом и получается, что одинаковые миры создаются многократно, постоянно идут проверки и выясняется, что миры уже были. Это наводит на мысли о том, что в таких ресурсоемких задачах все же придется применять головной мозг ^[24].

Расчет счастливых билетиков, попытка №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. Сошлось, ура!!! ^[25]

Время вычисления результата не радует: в 16:49 начали расчет, а закончили в 17:23. То есть более 30 минут. Но что дало решение задачи с билетами и что пришлось преодолеть? В первую очередь это один миллион миров в хранилище. Изначально я записывал в хранилище не хэши миров, а прямо кортежи мира. При поиске в списке с таким количеством записей мы уже начинаем сталкиваться с большими задержками. Применение хеша увеличило скорость. А размышления в шаге 5 так же подтвердили правильность применения хешей. Хотя в принципе можно хранить и кортеж мира, но удалив из него не значащую информацию. Кроме того, текущая архитектура показывает, что есть еще резервы для качественного роста в плане производительности, ведь миры, которые нужно рассчитать, даны в массиве и элементы массива миров можно вычислять параллельно, на нескольких нодах Erlang. Все вычисления миров каждый раз запускаются в новом процессе. И теоретически можно достичь максимального количества процессов в виртуальной машине Erlang, что должно привести к ошибке. Вычисление билетиков позволило «упереться» в ограничение, обработать ошибку и убедиться в том, что результат получается верным.

Задача “Волк, коза и капуста”

“Крестьянину нужно перевезти через реку волка, козу и капусту. Но лодка такова, что в ней может поместиться только крестьянин, а с ним или один волк, или одна коза, или одна капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевез свой груз крестьянин?”

Подробнее про задачу, а так же о двух вариантах её решения можно прочитать по ссылке ^[26][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(r) -> 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 ^[26]].

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 методом решения математических задач ^[27].

Дальнейшее развитие
Кластерные вычисления. Экспериментирую с erlang pool.

Разработка фреймворка №2 для решения другого класса зада, когда сначала строится дерево, а потом находятся решения по нему. Например, AI для реализация игры в крестики нолики. Для нее строится дерево из любых возможных комбинаций в игре в сторону выигрыша. При наступлении хода в игре, AI находит мир в дереве, выбирает одну из ветвей развития, которая приведет мир к выигрышному целевому миру и делает соответствующий шаг.

Список использованных источников

1. Путешествия во времени и программирование — habrahabr.ru/post/150300/ ^[2]
2. Путешествия во времени и программирование 2: парадоксы — habrahabr.ru/post/178959/ ^[3]
3. Головачев Василий — Палач времен
4. qt-project.org/ ^[28]
5. Начала работы с Erlang — rsdn.ru/article/erlang/GettingStartedWithErlang.xml ^[29]
6. www.erlang.org/ ^[30]
7. Задача “Волк, коза и капуста” — suhin.narod.ru/mat4.htm ^[26]

Автор: UA3MQJ

Источник ^[31]