On Tue, Jun 20, 2006 at 08:11:47PM +0400, Денис Смирнов wrote:
> AT> Тогда возникает только вычислительная проблема.  Придется анализировать
> AT> т.н. power set отстойника (т.е. всевозможные подмножества, которые можно
> AT> составить из пакетов в отстойнике).  Т.е. если в отстойнике находится 10
> AT> пакетов, то в поисках максимального "хорошего" подмножества пакетов
> AT> придется анализировать 2^{10} = 1024 подмножества (включая полное и
> AT> пустое).  Если же в отстойнике 100 пакетов, то имеем порядка 10^{30}
> AT> вариантов, и задачу в строгом смысле вряд ли удастся решить.  Есть
> AT> конечно градиентные методы и всякая прочая хрень...
> 
> Эта задача решается куда проще. При условии что у нас есть алгоритм,
> который по группе пакетов дает четкий ответ есть там unmet'ы или нет. И
> если есть, то какой пакет не устанавливается, и каких provides ему не
> хватает. Ну и, разумеется, есть информация по requires/provides всех
> пакетов.

Есть только предикат, который для данной группы (точнее, подмножества;
слово группа здесь лучше не произносить) дает однозначный ответ:
появились новые анметы или нет.

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

Если исходить только из предиката, то получается экспоненциально трудная
задача -- найти максимальное подмножество, удовлетворяющее критерию.
То есть перебор подмножеств B(U) aka булеан aka power set.

> Берем пакет. Если unmet'ов нет -- сразу переносим. Если unmet'ы есть, то
> смотрим какие из пакетов во временном репозитории имеют соответствующие
> provides, повторяя этот процесс рекурсивно до получения либо группы
> пакетов, которые можно установить, либо информации о том, что этот пакет
> нельзя установить вообще.

Я склоняюсь к тому, что автоматически ничего волшебно-простого сделать
нельзя.  Сказывается также отсутствие постановки задачи.  Так может быть
стоит посмотреть примеры анметов за последний год...