Рассчитать изображение набора для функции, представленной в виде массива ROBDD - PullRequest
Новая
       47

Рассчитать изображение набора для функции, представленной в виде массива ROBDD

2 голосов
/ 15 октября 2011

У меня есть набор целых чисел, представленный в виде Сокращенная упорядоченная двоичная диаграмма принятия решения (ROBDD) (интерпретируется как функция, которая оценивается как истинная, если вход находится в наборе), которую я назову Доменом, и целочисленная функция (которую я назову F), представленная в виде массива ROBDD (одна запись на бит результата).

Теперь я хочу вычислить изображение домена для F. Это определенно возможно, потому что это можно сделать тривиально, перечислив все элементы из домена, применив F и вставив результат в изображение. Но это ужасный алгоритм с экспоненциальной сложностью (линейный по размеру домена), и моя интуиция подсказывает мне, что он может быть быстрее. Я смотрю в направлении:

  1. применить ограничение (домен) ко всем битам F
  2. сотвори волшебство

Но второй шаг оказался трудным. Результат первого шага содержит информацию, которая мне нужна (по крайней мере, я уверен в этом на 90%), но не в правильной форме. Есть эффективный алгоритм, чтобы превратить его в «набор, закодированный как ROBDD»? Нужен ли другой подход?

Ответы [ 2 ]

1 голос
/ 16 октября 2011

Определите две функции с множественными значениями: 

N(d1...dn): The subset of the image where members start with a particular sequence of digits d0...dn. 
D(d1...dn): The subset of the inputs that produce N(d1...dn).

Тогда, когда последовательности пусты, у нас есть полная проблема: 

D(): The entire domain. 
N(): The entire image.

Из полного домена мы можем определить два подмножества: 

D(0) = The subset of D() such that F(x)[1]==0 for any x in D().
D(1) = The subset of D() such that F(x)[1]==1 for any x in D().

Этот процесс может быть применен рекурсивно для генерации D для каждой последовательности. 

D(d1...d[m+1]) = D(d1...dm) & {x | F(x)[m+1]==d[m+1]}

Затем мы можем определить N (x) для полных последовательностей: 

N(d1...dn) = 0 if D(d1...dn) = {}
N(d1...dn) = 1 if D(d1...dn) != {}

Родительские узлы могут быть получены от двух дочерних элементов, пока мы не создадим N ().

Если в какой-то момент мы определим, что D (d1 ... dm) пусто, то мы знаем, что N (d1 ... dm) также пусто, и мы можем избежать обработки этой ветви. Это основная оптимизация.

Следующий код (в Python) описывает процесс: 

def createImage(input_set_diagram,function_diagrams,index=0):
  if input_set_diagram=='0':
    # If the input set is empty, the output set is also empty
    return '0'
  if index==len(function_diagrams):
    # The set of inputs that produce this result is non-empty
    return '1'
  function_diagram=function_diagrams[index]
  # Determine the branch for zero
  set0=intersect(input_set_diagram,complement(function_diagram))
  result0=createImage(set0,function_diagrams,index+1)
  # Determine the branch for one
  set1=intersect(input_set_diagram,function_diagram)
  result1=createImage(set1,function_diagrams,index+1)
  # Merge if the same
  if result0==result1:
    return result0
  # Otherwise create a new node
  return {'index':index,'0':result0,'1':result1}
1 голос
/ 15 октября 2011

Пусть S (x1, x2, x3 ... xn) будет индикаторной функцией для множества S, так что S (x1, x2 ... xn) = true, если (x1, x2, ... xn)является элементом S. Пусть F1 (x1, x2, x3 ... xn), F2 (), ... Fn () будут отдельными функциями, которые определяют F. Тогда я мог бы спросить, является ли конкретный битовый шаблон с wildкарточек, в образе F, формируя уравнение, например, S () и F1 () & ~ F2 () для битовой комбинации 10, а затем решая это уравнение, которое я предполагаю, что я могу сделать, так как это ROBDD.

Конечно, вам нужна общая индикаторная функция, которая сообщает мне, есть ли на изображении abc.Расширяя вышесказанное, я думаю, вы получите S () & (a & F1 () | ~ a & ~ F1 ()) & (b & F2 () | ~ b & ~ F2 ()) & ... Если вы затем переставите переменные так,что исходные x1, x2, ... xn встречаются последними в порядке ROBDD, тогда вы сможете обрезать дерево, чтобы вернуть true для случая, когда любая настройка x1, x2, ... xn приводит к значениюtrue и возвращать false в противном случае.

(конечно, вы можете использовать пробел или терпение в ожидании повторного заказа на работу).

...