Задача по теории алгоритмов "Функции".
Микросхема вычисляет функцию, значение которой зависит от других функций.
Функции, пронумерованы числами от 1 до N.
Указаны зависимости: для вычисления какой функции какие нужно знать. Получается дерево зависимостей между функциями (от данной функции может зависеть не более одной функции). Корень -- та функция, которую надо вычислить.
В микросхеме есть k ячеек памяти для промежуточных вычислений. Надо вычислить минимальное k и вывести порядок вычисления функций.
Пример: 1(2,3) 2(4,5,6) 3(7,8). Вычислить функцию номер 1.
Ответ: 3 ячейки (порядок 4:1, 5:2, 6:3, 2:1, 7:2, 8:3, 3:2, 1:1) (функция:скольно_ячеек_сейчас_занято).

Решение:
Рассматриваем все листья, ставим на на них пометки 1, добавляем в очередь всех родителей листьев.
Пока очередь не пуста, извлекаем из неё элемент, сортируем потомков этого узла по невозрастанию меток, вычисляем величину max(a[i]+i), где a[i] -- метка i-го потомка (нумеруются от 0). Эта величина и есть пометка данного узла (то есть сколько ячеек памяти нужно для вычисления этого поддерева). В очередь добавляем узлы, у которых рассмотрены все потомки.
Ответ: метка корня. Последовательность вычисления: обратный обход дерева(с учётом сортировки потомков).

Естественно, порядок вычисления неоднозначен.

Вопрос: Как вывести минимальный лексикографически порядок?
Основная проблема в том, что с этим дополнительным условием поддеревья уже не обязательно будут вычисляться оптимальным способом.
Пример: 10(9,8) 9(7,6,5,4) 8(3,1) 3(2). Ответ: (1:1, 2:2, 3:3, 8:1, 4:2, 5:3, 6:4, 7:5, 9:2, 10:1).
Поддерево 8 можно посчитать имея и лишь 2 ячейки памяти (2:1, 3:1, 1:2, 8:1), но мы должны считать за 3 из-за требования лексикографеской минимальности.

Может, кто-нибудь знает решение, полезные советы или книги, где это описано?

Здравствуйте, _Vi, Вы писали:

[skipped]
_Vi>Вопрос: Как вывести минимальный лексикографически порядок?

Можно применить дубовый метод:
1) пишем ф-ю F, отвечающую на вопрос "продолжима ли последовательность до оптимальной?"
2) строим ответ: на каждом шаге делаем ход в минимальный элемент, допускающий продолжение до оптимума

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

Сложность порядка N^3.
Вполне возможно, что можно как-нибудь и по-быстрее.

Здравствуйте, _Vi, Вы писали:

_Vi>Пример: 10(9,8) 9(7,6,5,4) 8(3,1) 3(2). Ответ: (1:1, 2:2, 3:3, 8:1, 4:2, 5:3, 6:4, 7:5, 9:2, 10:1).

Не совсем понятно, почему ответ такой. Разве не будет лучше посчитать 1, 2, 3, 4, 5, 6, 7, 8, 9, 10?

V_>Здравствуйте, _Vi, Вы писали:
_Vi>>Пример: 10(9,8) 9(7,6,5,4) 8(3,1) 3(2). Ответ: (1:1, 2:2, 3:3, 8:1, 4:2, 5:3, 6:4, 7:5, 9:2, 10:1).
V_>Не совсем понятно, почему ответ такой. Разве не будет лучше посчитать 1, 2, 3, 4, 5, 6, 7, 8, 9, 10?

Рассмотрим твой вариант: 1:1, 2:2, 3:2, 4:3, 5:4, 6:5, 7:6, 8:5, 9:2, 10:1. Итого надо 6 ячеек. А можно за 5.

Вообще говоря мой пример не совсем верен, вот исправление:
Пример: 11(10,9) 10(8,7,6,5) 9(4,1) 4(3,2).
Ответ: (1:1, 2:2, 3:3, 4:2, 8:1, 5:2, 6:3, 7:4, 8:5, 10:2, 11:1).
Здесь для вычисления поддерева 9(4(3,2),1) мы используем 3 ячейки, хотя можно за 2. Но на итоговые 5 ячеек в микросхеме оно не влияет.

Здравствуйте, _Vi, Вы писали:

_Vi>В микросхеме есть k ячеек памяти для промежуточных вычислений. Надо вычислить минимальное k и вывести порядок вычисления функций.

Давай пойдём по индукции.
Пусть выражение y = f(x1 ... xm), и для вычисления каждого x требуется Ki ячеек.
Порядок вычисления мы можем выбирать произвольно, поэтому допустим, что оптимальный порядок — это именно от первого к последнему (если не так — перетасуем, чтобы было так).
Тогда нам потребуется
1) K1 для вычисления x1
2) 1+K2 для хранения x1 и вычисления x2
...
m) m-1+Km для хранения всех предыдущих аргументов и вычисления последнего
m+1) m для хранения всех аргументов, готовых к использованию.

Итого, нужно минимизировать max(K1, 1+K2, 2+K3, ..., m-1+Km, m)
Очевидно, что когда K1 >= K2 >= ... >= Km, мы достигаем этой минимизации.

Теперь становится всё очевидно.
— каждому листу дерева (т.е. константе) назначаем вес K=0 (её не нужно вычислять, она есть сама по себе)
— каждому узлу дерева, дочерние узлы которого взвешены, назначаем вес

kParent = maximum(zipWith(+) [0..m] ((reverse(sort ksChildren)) ++ [0]))

где kParent — вес родителя (искомый), ksChildren — список весов детей (известный). zipWith(+) — почленно суммирует списки.

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

-- синтаксическое дерево
type Name = String -- идентификатор узла
data Expr = E Name [Expr] -- т.е. имя + (возможно пустой) список аргументов
-- E "hello" [] - константа
-- E "foo" [E "bar" [], E "buz" []] - foo(bar,buz) - двухместная функция

-- для отчётности: последовательность действий
data Application = A Name [Name] -- одиночное действие
type Applications = [Application] -- последовательность, от самых независимых до корня

-- для решения задачи: нам нужен список весов
type Dependency = (Int, Applications)
type Dependencies = [Dependency]

optimize :: Expr -> Dependency -- на входе дерево, на выходе последовательность и вес

optimize (E name []) = ([], 0) -- константу вычислять не нужно
-- либо, если всегда пихаем константу в стек, то
optimize (E name []) = ([A name []], 1)

optimize (E name exprs) = (total, apps++[lastapp]) where
    args = map (\(E n _) -> n) exprs
        -- получили список имён аргументов
    lastapp = A name args
        -- так будет выглядеть вызов корневой функции
    deps = sortByWeight (map optimize exprs)
        -- для каждого аргумента нашли оптимальный способ вычисления
        -- и отсортировали эти способы по убыванию веса
        where
            comparator (w1,_) (w2,_) =
                if      w1<w2 then GT
                else if w1>w2 then LT
                else               EQ
                -- компаратор по убыванию
            sortByWeight ds = sortBy comparator ds
    apps = concat (map snd deps)
        -- склеили последовательности (второй элемент кортежа - snd)
    weights = filter (> 0) (map fst deps')
        -- получили весы аргументов
        -- константы нас не интересуют, мы не будем резервировать для них место
    total = maximum (zipWith (+) [0..(length weights)] (weights++[0]))
        -- нашли итоговый вес
        -- для функции, зависящей от констант, очевидно, вес будет равен 1
        -- потому что результат вычислений всё-таки надо запомнить

не проверял, с листа наваял...

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, _Vi, Вы писали:

_Vi>>В микросхеме есть k ячеек памяти для промежуточных вычислений. Надо вычислить минимальное k и вывести порядок вычисления функций.

К>Давай пойдём по индукции.
К>Пусть выражение y = f(x1 ... xm), и для вычисления каждого x требуется Ki ячеек.
К>Порядок вычисления мы можем выбирать произвольно, поэтому допустим, что оптимальный порядок — это именно от первого к последнему (если не так — перетасуем, чтобы было так).

Вот тут теряем возможность найти лексикографически наименьшее оптимальное решение.
Хотя какое-то оптимальное конечно найдем.
Во-первых как уже было замечено не все поддеревья обязательно вычислять оптимально.
Во-вторых модель вычислений может быть сложнее чем последовательная, т.е. посчитали немного в первом поддереве, потом во втором и т.д.

Здравствуйте, Иванков Дмитрий, Вы писали:

К>>Давай пойдём по индукции.
К>>Пусть выражение y = f(x1 ... xm), и для вычисления каждого x требуется Ki ячеек.
К>>Порядок вычисления мы можем выбирать произвольно, поэтому допустим, что оптимальный порядок — это именно от первого к последнему (если не так — перетасуем, чтобы было так).

ИД>Вот тут теряем возможность найти лексикографически наименьшее оптимальное решение.

Ну, если такое требование существовало... То конечно, придётся попотеть.

ИД>Хотя какое-то оптимальное конечно найдем.
ИД>Во-первых как уже было замечено не все поддеревья обязательно вычислять оптимально.

ИД>Во-вторых модель вычислений может быть сложнее чем последовательная, т.е. посчитали немного в первом поддереве, потом во втором и т.д.

В этом случае мы не можем улучшить ситуацию. Допустим, некое поддерево целиком считается и занимает K ячеек стека. Если перед вычислением этого поддерева мы решили посчитать что-то постороннее, то по окончании вычислений оно займёт 1 ячейку. И к этому добавляем K на вычисление нашего поддерева. K+1. Хорошо, если мы не выбежим из глобального оптимума, а если выбежим?

---

Мне кажется, что глобальный лексикографический (лг-) минимум обеспечивается в случае локальных лг-минимумов.
То есть, в выражении f(x1,...,xn)
— находим веса аргументов w1...wn
— сортируем (W -> W') и находим значения K = {w'i+(i-1)}U{n}
— находим вес всего выражения m = max K
— переупорядочиваем, чтобы лг-минимизировать, не вылезая из m. (сейчас нет времени, чтобы придумать алгоритм)

Здравствуйте, _Vi, Вы писали:

Если плясать от того, что мы имеем дело с графом, то порядок вычислений выдаст топологическая сортировка,
а для вычисления необходимого количества ячеек похоже надо найти вершину,
у которой максимальное количество входящих ребер исходит из "вычисляемых" вершин,
вот это количество похоже и будет искомой величиной.

К>Ну, если такое требование существовало... То конечно, придётся попотеть.

Не обратил внимание на тему Ладно, будем думать.

Да, кстати! Если под константу не нужно резервировать память, то можно с самого начала выполнить редукцию: выкинуть все константы.
Это приведёт к сокращению арностей всех функций, некоторые из них станут даже нуль-арными (константами времени исполнения). Но уже они — требуют памяти под запись результата.
Таким образом, мы получили формулу, в которой все элементы равноправны.

К>Мне кажется, что глобальный лексикографический (лг-) минимум обеспечивается в случае локальных лг-минимумов.

На самом деле, конечно, нет.
Тем не менее, давайте сперва найдём вес (потребный размер стека) для каждого узла дерева, ну и для задачи целиком.

После чего начинаем строить последовательность:

Берём самый первый аргумент, смотрим — можем ли вычислить его, не выбежав из глобального ограничения по памяти (подробнее об этом позже). Для этого корректируем вес всех узлов, зависящих от него (вверх до корня).
Смогли? Записали в последовательность, пометили узел как готовый, вычеркнули.
Нет? Смотрим на лг-следующий аргумент.
И так продолжаем до тех пор, пока не выпишем всех.

Замечание: лг-порядок элементов формулы обязан топографически упорядочивать её. При этом более естественной будет обратная польская запись — вместо f(x,y,z) — (x,y,z)f.

---

Что касается коррекции веса — и проверки выбегания из памяти.
Мне очевидно*, что узел, идущий не вовремя, может ухудшить вес родителя не более чем на единицу. Т.е. может не ухудшить; улучшить всяко не удастся, т.к. мы уже нашли минимум.
Соответственно, утяжеление родителя на 1 приведёт к утяжелению прародителя не более чем на 1. И т.д.

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

Так что нужно ещё каким-то образом найти не только персональный вес, но и два признака:
— дельта веса родителя при внеочередном выполнении
— дельта веса родителя при собственном утяжелении
как функции от весов всех своих братьев (но, к счастью, не от их дельт).

Что-то мне подсказывает, что эти дельты можно найти за O(n), сразу после сортировки весов. Но пока ещё не додумал.