On Wed, Aug 30, 2006 at 08:10:50PM +0400, Dmitry V. Levin wrote:
> > (Алгоритм оптимизации BuildRequires обсуждался вчера в частной
> > переписке.  Правда, спросонья я потерял к нему интерес.  Если это
> > интересно кому-то ещё, тогда можно перенести обсуждение сюда.)
> 
> Думаю, что лучше перенести сюда - вдруг среди нас есть специалист/практик
> по теории графов?

Вот математическая постановка задачи.  Дан список (множество) пакетов P.
Найти минимальное подмножество P_0, при котором множество P является
подмножеством транзитивного замыкания P_0:

P_0\subset P
P\subset [P_0]
\forall P_n P\subset [P_n] \Rightarrow |P_n|\geq|P_0|

Здесь [P] -- транзитивное замыкание множества, |P| -- мощность множества.
Подмножества не обязательно собственные.

Говорить о транзитивном замыкании множества не совсем корректно.
Речь идет о транзитивном замыкании пакетов по отношению "зависеть".
Например, если дан пакет A, и при этом известно, что пакет A требует
пакет B, тогда B входит в [A].  Если же пакет B зависит от пакета C,
тогда C снова входит в [A] и т.д.

Последнее условие выражает ту мысль, что подмножество P_0 должно быть
в некотором смысле минимальным.  А именно, все другие подмножества с
транзитивным замыканием [P] или больше обладают не меньшей мощностью.

Решение этой задачи в лоб означает перебор всех подмножеств P_n и
построение для каждого из них транзитивного замыкания.  Среди
подмножеств, у которых транзитивное замыкание не меньше [P] (а
фактически совпадает с [P]), нужно выбрать наименьшее по числу
элементов.

Однако известно, что перебор подмножеств -- это чрезвычайно трудоемкая
задача.

Кто ничего не понял, транзитивное замыкание -- это, грубо говоря, список
пакетов в чруте, который hasher/apt разворачивает по строчке
BuildRequires.  Т.е. список пакетов в чруте -- это транзитивное
замыкание [BuildRequires].  Оптимизация списка BuildRequires тогда
состоит в том, чтобы при удалении некоторых элементов из этого списка
содержимое чрута в конечном счете не менялось.  Остается только выбрать
наилучшую их всех возможных оптимизаций, при которой список
BuildRequires становится минимальным.

Кстати, можно изменить условие задачи:
-P_0\subset P
+P_0\subset [P]

Я реализовал это в buildreq2 и получил интересные результаты.
В buildreq2 решена задача построения транзитивного замыкания,
но не до конца не решена задача оптимизации.