[devel] [sisyphus -> devel] Стабильный Сизиф

[Денис Смирнов]

On Mon, Jun 19, 2006 at 07:18:02PM +0400, Алексей Турбин wrote:

AT> Тогда возникает только вычислительная проблема.  Придется анализировать
AT> т.н. power set отстойника (т.е. всевозможные подмножества, которые можно
AT> составить из пакетов в отстойнике).  Т.е. если в отстойнике находится 10
AT> пакетов, то в поисках максимального "хорошего" подмножества пакетов
AT> придется анализировать 2^{10} = 1024 подмножества (включая полное и
AT> пустое).  Если же в отстойнике 100 пакетов, то имеем порядка 10^{30}
AT> вариантов, и задачу в строгом смысле вряд ли удастся решить.  Есть
AT> конечно градиентные методы и всякая прочая хрень...

Эта задача решается куда проще. При условии что у нас есть алгоритм,
который по группе пакетов дает четкий ответ есть там unmet'ы или нет. И
если есть, то какой пакет не устанавливается, и каких provides ему не
хватает. Ну и, разумеется, есть информация по requires/provides всех
пакетов.

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

-- 
С уважением, Денис

http://freesource.info
----------------------------------------------------------------------------
плохо закрыл - вот теперь закрываю :)
		-- lav in #575