Le problème de l'installabilité d'un paquet, étant donné un certain nombre de contraintes, est NP-complet[1]. Il y a donc peu de chances que tu puisses le résoudre en un temps qui a l'air linéaire en la taille du dépôt.
Il semble donc probable que ton algo soit incomplet. Si tu t'intéresses à ce genre de chose, le projet européen EDOS[2] et son successeur MANCOOSI[3] ont fait pas mal de boulot sur le sujet.
# NP-complet
Posté par arenthis . En réponse au journal Résolution des dépendances par système de branches. Évalué à 10.
Il semble donc probable que ton algo soit incomplet. Si tu t'intéresses à ce genre de chose, le projet européen EDOS[2] et son successeur MANCOOSI[3] ont fait pas mal de boulot sur le sujet.
[1] http://www.edos-project.org/xwiki/bin/download/Main/Delivera(...)
[2] http://www.edos-project.org
[3] http://www.mancoosi.org