DemonScript: Размещения ящиков

Рассмотрим мир прямоугольных закрытых ящиков различных размеров. Ящики можно вкладывать друг в друга. Когда ящик X находится внутри ящика Y, считается истинным отношение X in Y. Если информации о размерах ящиков нет, то существует достаточно большее число вариантов размещения ящиков друг в друге. Например, для двух ящиков a,b, возможно три варианта: 1) ящик a находится в ящике b; 2) ящик b находится в a; 3) ящики не находятся друг в друге. Для четырёх ящиков таких вариантов 16 и т.д.:

   1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691,..

В общем случае для N ящиков число размещений равно (N+1)^(N-1) и образует последовательность A000272. Задача состоит в получении всех этих моделей при помощи логического программирования.

Определим тип отношения и создадим граф с четырмя безымянными узлами:

edges in                           // объявляем типы рёбер
GRAPH.add_nodes(4)                 // будет 4 узла (ящика)

Теперь добавим в объект Mind аксиомы, которые описывают отношение in:

Mind.add( 
  X !in X,                  				 // антирефлексивно
  X in Z & Z in Y -> X in Y,				 // транзитивно
  Z in X & Z in Y -> X in Y | Y in X | X==Y, // дерево
)

Антирефлексивность означает, что ящик X сам в себе находиться не может, а транзитивность подразумевает возможность сколь угодно глубокой вложенности ящиков, подобно матрёшкам. Третья аксиома древесности звучит как: если Z находится и в X, и в Y, то либо X внутри Y, либо Y внутри X, либо это один и тот же ящик.

Идея порождения моделей состоит в следующем. Если в графе между двумя узлами (ящиками) нет ребра in (т.е. оно имеет неопределённое значение Undef), это означает что ящики как могут находится друг в друге (отношение равно True) так могут и не находиться (отношение равно False). Поэтому допустимы две модели со значениями ребра в одной True, а во второй False. Каждая из них, в свою очердь может породить ещё два графа для другого ребра и т.д.

Поэтому, возьмём граф с N узлами без рёбер и поместим его в очередь (массив Open). На каждой итерации из очереди извлекается один граф и в нём ищется неопределённое ребро. Если такого ребра нет, это означает, что сформировалась полностью определённая модель размещения ящиков. Если же ребро найдено, то делаются две копии этого графа. В одном графе ребро помечаем как True, а в другом - как False. Эти графы снова помещаем в очередь и повторяем процедуру до тех пор пока очередь не опустеет.

Перейдём к реализации алгоритма. Создадим двух демонов. Первый будет добавлять в очередь (массив) Open новый граф, устанавливая ребро X in Y в значение Val:

def add_graph(Open, X, Y, Val)
{
   var GV = GRAPH.copy()           // делаем копию графа
   GRAPH  = GV                     // делаем её активной
   X in Y = Val                    // меняем ребро
   Mind.set_graph(GV)              // запускаем логический вывод
   Open.push(GV)                   // добавляем граф в очередь
}

Второй демон находит первое неопределённое ребро и порождает два графа, которые после установки ребра помещаются в очередь Open:

def set_edges(Open)
{
   for X in True :                      // бежим по всем узлам графа
      if exists(Y, (X in Y) == Undef){  // если есть узел с неопределённым ребром
         add_graph(Open, X, Y, True)    // создаём две копии графа 
         add_graph(Open, X, Y, False)   // в которых определяем это ребро
         return True
      }
    return False
}

Основной код алгоритма выглядит следующим образом:

var G = GRAPH                          // для краткости
//G[1] in G[2];                        // можем задать ограничения

Mind.set_graph(G)                      // устанавливаем антирефлексивность

var Open = [ G.copy() ]                // помещаем в очередь начальный граф
var N_MODELS = 0                       // число сгенерённых моделей       

while !Open.empty() {                  // пока очередь не пустая
   GRAPH = Open.pop()                  // извлекаем из неё граф
   if !set_edges(Open){                // если не нашли Undef рёбер
      N_MODELS++                       // это финальная модель
      //out GRAPH                      // выводим её
   }
}

out "Count of graphs: ", N_MODELS      // выводим число моделей
out System.time(),"ms"                 // выводим время работы

Описанный выше алгоритм встроен в объект Mind. Ему необходимо передать текущий граф (первый аргумент) и тип ребра (in) которые следует устанавливать в графе в значения True и False при неопределённом значении (Undef):

GRAPH.clear_edges()                    // убиваем  все рёбра
System.time(0)                         // сбрасываем таймер

out "Count of graphs: ", 
out Mind.count_models(GRAPH, in)       // Mind подсчитывает число моделей

out System.time(),"ms"                 // выводим время работы

Полный код этого примера находится в файле in_models_calc.ds.

---