Corrigé Mines-Ponts 2025 Informatique commune MP-PC-PSI — Partie 8 (Q24) : Comparaison des méthodes : temps, optimalité, réglage de l'ACO

Sujet officiel du concours Mines-Ponts, session 2025, épreuve Informatique commune MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Sujet officiel (PDF, site du concours)

Énoncé

La simulation. $20$ objets, de ressources et de profits entiers compris entre $1$ et $100$ , et $b = 200$ . Pour chaque méthode, le sujet affiche le temps d'exécution, la solution et son profit, et pour l'ACO ( $α = 2$ , $β = 5$ , $ρ = 0, 8$ , $τ_{m a x} = 6$ , $τ_{m i n} = 0, 01$ ) le début de la liste T des traces :

Méthode	Temps (s)	Profit
Force brute	$1, 28$	$567$
Glouton	$2, 3 \times 1 0^{- 5}$	$548$
PSE	$2, 7 \times 1 0^{- 2}$	$567$
Programmation dynamique	$8, 5 \times 1 0^{- 4}$	$567$
ACO, $5$ fourmis, $1$ itération	$3, 0 \times 1 0^{- 4}$	$548$
ACO, $5$ fourmis, $5$ itérations	$1, 3 \times 1 0^{- 3}$	$567$
ACO, $5$ fourmis, $50$ itérations	$1, 1 \times 1 0^{- 2}$	$567$

Toutes les méthodes à $567$ rendent la même solution (objets $4$ , $6$ , $7$ , $8$ , $10$ , $11$ , $12$ ) ; le glouton et l'ACO à une itération rendent celle à $548$ . Début de T : $[4, 8; 5, 8; 4, 8; 4, 8; 5, 8; \dots]$ après $1$ itération, $[1, 966; 2, 967; 1, 966; 1, 966; 4, 767; \dots]$ après $5$ , $[0, 01; 0, 065; 0, 01; 0, 01; 3, 799; \dots]$ après $50$ .

Q24. Commenter ces résultats (temps d'exécution, qualité de la solution) ; pour l'ACO, dire sur quels paramètres on peut jouer et avec quelles conséquences.

Corrigé

Q24. Qualité. Quatre méthodes sont exactes et trouvent l'optimum $567$ : force brute, PSE, programmation dynamique (garanties), et l'ACO dès $5$ itérations (sans garantie). Le glouton rend $548$ , soit $19$ de moins, environ $3, 4%$ sous l'optimum : solution admissible et correcte, mais non optimale, comme prévu en Q11.

Temps. Les écarts suivent les complexités établies plus haut.

Force brute : $1, 28 s$ pour $2^{20} \approx 1 0^{6}$ feuilles évaluées chacune en $O (n)$ (Q6). Ajouter $10$ objets multiplierait ce temps par plus de $1000$ : la méthode est inutilisable au-delà de quelques dizaines d'objets.
PSE : même résultat, environ $50$ fois plus vite ( $1, 28/0, 027 \approx 47$ ) grâce à l'élagage ; mais dans le pire cas, rien n'est élagué et la complexité reste exponentielle.
Programmation dynamique : $1500$ fois plus rapide que la force brute, car $n b = 20 \times 200 = 4000$ cases seulement (Q13). Elle est ici le meilleur choix ; mais son coût est pseudo-polynomial, et pour des ressources de l'ordre de $1 0^{9}$ le tableau ne tiendrait plus en mémoire.
Glouton : le plus rapide ( $2, 3 \times 1 0^{- 5} s$ , coût quasi linéaire), au prix de l'optimalité ; il sert de point de départ ( $P_{m i n}$ ) à la PSE.
ACO : coût proportionnel à $n b_{A n t s} \times n b_{i t}$ (le temps est multiplié par $\approx 4$ puis par $\approx 9$ quand $n b_{i t}$ passe de $1$ à $5$ puis à $50$ ) et indépendant de la valeur de $b$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →