Объяснение алгоритма вычисления входных и выходных переменных - PullRequest
Новая
       44

Объяснение алгоритма вычисления входных и выходных переменных

0 голосов
/ 26 мая 2018

На этом слайде показан алгоритм вычисления in[n] и out[n] для узла графа потока управления.Мне трудно понять, как это работает.Я видел несколько других вариантов, а также с трудом понимаю их.Я никогда не имел дело с вещами с фиксированной запятой. 

for each n
  in[n] := {}; out[n] = {}
repeat
  for each n
    in’[n] := in[n]; out’[n] := out[n]
    in[n] := use[n] ∪ (out[n] - def[n])
    out[n] := ∪ {in[s] | s ε succ[n]}
  until in’[n] = in[n] and out’[n] = out[n]
  for all n

Вопрос в том, что делает этот алгоритм / более интуитивное объяснение этого.Я не понимаю, что такое in' и out' и что означает конечное условие (until in'...).Не следуя вложенным циклам.Моя попытка реализации JavaScript показывает, где мне не хватает частей: 

var in = {}
var out = {}
var in2 = {}
var out2 = {}
var use = {}
var out = {}
var def = {}

for (var i = 0, n = nodes.length; i < n; i++) {
  var node = nodes[i]
  in[node] = []
  out[node] = []
  // assume these are already filled out:
  use[node] = []
  out[node] = []
  def[node] = []
}

while (true) {
  for (var i = 0, n = nodes.length; i < n; i++) {
    var node = nodes[i]
    in2[node] = in[node]
    out2[node] = out[node]
    // assume ∪ and - work on arrays
    in[node] = use[node] ∪ (out[node] - def[node])
    // ? not sure the ∪
    out[node] = ∪ {in[s] | s ε succ[n]}
  }

  // until in’[n] = in[n] and out’[n] = out[n]
  // for all n
}

Любая помощь будет принята с благодарностью.Спасибо.

1 Ответ

0 голосов
/ 27 мая 2018

Алгоритм наименьшей фиксированной точки применяется к ситуациям, когда у вас есть конечное число наборов, члены которых происходят из конечного юниверса, и где членство в каждом наборе (возможно) зависит от членства других наборов, в частности, путем включения элементовиз конкретных других наборов.

Если зависимости образуют ориентированный ациклический граф (DAG), то проблем нет;наборы могут быть вычислены путем топологического упорядочения наборов в отношении зависимости, а затем вычисления наборов по порядку.(Из-за топологической сортировки ни один набор не зависит от предыдущего набора, поэтому к тому времени, когда набор должен быть вычислен, все его зависимости уже вычислены.)

Но если граф зависимостей имеет циклы, aТопологическая сортировка невозможна, поэтому мы используем алгоритм с наименьшей фиксированной точкой.Мы начинаем с установки всех наборов на пустые, а затем обрабатываем их все в некотором порядке.Когда мы приходим к зависимости, мы просто добавляем элементы, которые оказались в зависимости в тот момент.Если какой-либо набор был изменен во время этого цикла, мы обрабатываем все наборы снова.(Нет необходимости обрабатывать их в одном и том же порядке, но обычно это самый простой способ.) И мы продолжаем делать это снова и снова, пока не пройдем полный цикл без добавления какого-либо нового элемента в какой-либо набор.На данный момент мы достигли согласованного набора зависимостей членства («фиксированная точка»), в которой нет посторонних элементов (так что это «наименее фиксированная точка»).

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

Эти проблемы обычно могут быть решены путем вычисления транзитивного замыканияреляционного уравнения.Поскольку алгоритмы транзитивного замыкания, как правило, быстрее (как с точки зрения теоретической сложности, так и с точки зрения практического времени выполнения внутреннего цикла), они будут предпочтительным решением, если скорость имеет значение.Однако алгоритм с наименьшей фиксированной точкой легче понять, а код несколько менее загадочный.

В конкретном алгоритме определения живучести установленные отношения зависимостей перечислены на предыдущем слайде;Вы можете видеть, что каждый набор in и out определяется некоторыми фиксированными элементами и объединением одного или нескольких других наборов.Как показано, алгоритм сохраняет копию всех наборов в начале цикла и сравнивает каждую копию с соответствующим набором в конце цицила.Если какой-либо набор был изменен в течение цикла, алгоритм еще не завершен.

На практике чаще всего просто установить логический флаг в false в начале цикла и в true, если объединениеоперация вызывает добавление нового элемента к набору (который легко добавить к операции объединения, но его сложно описать в формальном алгоритме).Затем алгоритм завершается, если логическое значение все еще ложно в конце цикла.

...