Cours/TD - algorithmes gloutons

Glouton

I. Découverte⚓︎

Glouton

Les algorithmes gloutons ou "greedy algorithms" forment une catégorie d’algorithmes permettant de donner une solution à des problèmes d’optimisation qui visent à maximiser/minimiser une quantité (GPS (plus court chemin, temps minimum, côut minimum) - plus petit temps d’exécution, meilleure organisation d’un emploi du temps, ....)

Principe d'un algorithme glouton

Un algorithme glouton est un algorithme qui suit le principe suivant :

résout le problème étape par étape, en faisant un choix optimum local dans l'espoir d'obtenir un résultat optimum global.
Ce choix d'étape n'est jamais remis en cause lors des étapes suivantes.

Un exemple⚓︎

grille

Sur la grille ci-dessus, on part de la case tout à gauche marquée de la lettre D. On souhaite atteindre les cases vides sur la partie droite en se déplaçant de case en case. Lorsqu'on est sur une case on peut se déplacer sur une des deux cases voisines situées sur la droite. On note S la somme de toutes les cases traversées.
Par exemple on peut effectuer la trajectoire suivante (on ne note pas la dernière case, qui est vide) : D - 7 – 5 – 3 – 5 – 7 – 9 – 8 – 9 – 6 qui conduit à S = 59.

🤔 On cherche à effectuer la trajectoire qui rend la somme S la plus petite possible. Pour cela, on va utiliser un algorithme glouton.

A chaque étape, nous choisissons le plus petit nombre.
Nous ne revenons jamais en arrière.

trajectoire gloutonne

Quelle trajectoire et quelle somme S obtenez-vous sur cet exemple avec votre algorithme glouton ?

Solution

D – 4 – 4 – 2 – 5 – 7 – 7 – 8 – 8 – 1

S = 46

Trajectoire optimale

Sur cette grille, en cherchant bien, la trajectoire optimale donne une somme S = 23. Déterminer le chemin correspondant

Solution

D - 4 - 4 - 3 - 2 - 3 - 1 - 3 - 1 - 2

Algorithme par force brute

Pour obtenir la solution optimale de façon certaine on souhaite trouver toutes les trajectoires possibles et calculer pour chacune d'elles la somme associée.
On doit faire 9 déplacements, et à chaque déplacement on a deux possibilités.
On a donc $2^9=512$ trajectoires différentes. Il faudrait donc calculer la somme pour chacune de ces 512 trajectoires différentes.
🌵 Cette méthode est exacte, mais beaucoup plus coûteuse en termes de calculs.

II. Le rendu de monnaie⚓︎

Situation :
Dans le pays nommé New Land, la monnaie est constituée de pièces de 4 nl, 3 nl et 1 nl.
L’unité de monnaie est le newland, symbolisé par nl.
Alice et Bob sont deux commerçants qui disposent dans leur caisse de beaucoup de pièces de chaque type, mais ils veulent rendre la monnaie en utilisant le moins de pièces possible.

1. La méthode de Bob : algorithme glouton⚓︎

La méthode gloutonne

Bob a une idée : il se dit que plus il rendra de pièces de grandes valeurs, mieux cela sera.

Pour donner 10 nl :

Il donne une pièce de 4 nl, il lui reste à rendre 6 nl,
puis il donne une pièce de 4 nl, il lui reste à rendre 2 nl,
puis il donne une pièce de 1 nl, il lui reste à rendre 1 nl,
puis il donne une pièce de 1 nl, il lui reste à rendre 0 nl.

La fonction monnaie_Glouton prend en paramètre un entier qui est le montant en nl, et renvoie la liste des pièces correspondantes, obtenue par l'algorithme glouton.

Exemple

🐍 Console Python

>>> monnaie_Glouton(6)
[4, 1, 1]
>>> monnaie_Glouton(9)
[4, 4, 1]

Compléter ci-dessous

Évaluations restantes : 5/5

.128013cPw-7 sSfE.bgn38k9]vei;(h4l,mdo0pI65_:2)=tGayC1/[ur050E0v0Q0S0w0B0h0g0b0B0S0h0h0P010Q0w0H010406050h0Y0D0D0S0Z0T040i0F0B0Y0@0F0o050W0~1012140|0H04051k1d1n0W1k0|0E0w0u0,0.0:0=0.0o0n0Y0S0n0v0e0H0T0Q0z1b0g0z0w0n0z0B1P0z0Q0`050%0m0B0v1w0/0;011O1Q1S1Q0Q1Y1!1W0Q0Z1l1K0,170h0H0S0o0=0N011$1y010j0)0v0o0S0D0v1W1{1}221(251!282a0`0a0g0c0Z0F0H0F0h0w1a0o0g0#1_0Z0Z0v0b2v1d2d0o1l0W1K2I1=1@1?1X0E2f1z0w0o272s1W1t1v0-1%2S2U0o0F2Y1W0H2B1l2G2I2/0}1|2w2!232(0Z110B1W0S1N2B0j0=030L0L0b2)0v1S2%0F0e0V3d0`0g0V1d0S2:2?0{2=2e2^1(2`2|2~300v32013436383a2V3d0e20040g0N3j3l1}3n2G2R013s0S2}1l2 0z313335370#3C2(3E0p3g0p3K2F3m0|3O3q0=3R3T053V3X3y3Z3B2T3D3e0A3g0A3,1e3.3o2@1x3r0F2{3S3u3W3w3Y3A3#3~3%3e0K3g0K442/3/2?3P3?4e3`3z3!394k3c3e0J3g0J4q463:493=4b3t3U3v3x4y3}3b3E0f3g0f4H3M4s3p4K3Q4M4d4O4f4Q3|4j4T3e0q3g0q4Y2H4!482#4%4c3@3_4g3{4i4A4/0e0s3g0s4@3N4t3;4|4N3^4P4h4z3$4C3d0G0`0V0G591o2-1d2Y2L0E1@2Q5c4z2X1u1l2,0v2.3m3-3M054z5G2e0w0E0=352G3E0V3u5O5Q525j5T212j0v5X5i4B5!2I3k474u0`0c0I0k0U0k0i5I2H0g5.5c0F0`0P5`3H5}4$0_040X62644{0D0w0`43455J4J4{660C625|6i236c0`3+6g2H6a236k6m6v1(6q043i6t5M4`6w0`0t620|6E5.5W015R2?3E3G5f6O4-533 3F5#295%6P5Y5*3e6T0W3k6L2;3O6V0L5S3e3)4O6;5)543)0g5$5(4S6Y6^3,6o1(0r0`0#0j6y753=0j0`0D1b280w0v0L0R0B0F191b697c01660y7r5b4$0o7f1b0%0o0Q7w4#6j0`0O0M6K7F2w6;6?0e416_5P6%6{6Y416~6#704.7W1W6,3H0g7*6z3=0`0S0L2B0o0E2B7b7x4{5 04616E6n7_2_7A7D1}7E6E6.5H6:7T6Q1}3E4n7S7!6X4l0e4n7Y2a8g5Z4m7%3k7*7+7s7z041S0h0Q0v7^7G237{7}2/7 8C1(660X6J867M0g7O6R4D5V8a6(544E8l6$6W8o0e4E5,7)8t80760`0j4b8B6G3r0`0H7j0b8A7~7,010F0d0`2T8:5/045;5?5^8O5c667K8N6M895X7P4V8f7U718i4V8Y8n6)0e9h3K8s9t8H8;0=77040d1O1!925c8v7/7;7?8`8G8|7{020n0Q0x8F3m9v938@2C9J888+0=9a7L9d4t8Q8c4:8T9o544;9n9j7#8i4;8(9u9_9T9E0`8x8z984$7{0la04{9F0H0H270Ea46H047v9%8I7-049V8_ab8J7I9$6/9(8U7P569i8!9p569:av54at9s9`9t8|9F7:a97@8{7s8E9D7y7.aH7=aJ9KaL0`0eaNa58?8^9X4Z8O9)0o5T5mau8V6Y5o6!8m9;8h5ka/9^8s8|9y2B0Q0Y0Z1caK9Z3Q9}0w8ya#4^690W5L5r5F5t5C1d0Q5wbh2O2J0S1Zbe0W5u6L0#0%0)0h04.

2. La méthode d'Alice : La force brute⚓︎

La méthode par force brute

Alice est très méthodique. Elle va chercher toutes les possibilités dont la somme correspond, puis ensuite elle prendra celle qui correspond au plus petit nombre de pièces. Cette méthode, qui consiste à chercher toutes les possibilités s'appelle une méthode par force brute. Le nombre maximal de pièces est la somme totale (si on la donne uniquement avec des pièces de 1)

La fonction possibilites renvoie une liste de listes. Chaque liste donne une possibilité pour rendre le montant.
Par exemple [1, 0, 2] signifie qu'on rend une pièce de 4, 0 pièce de 3, et 2 pièces de 1.

Exemple

🐍 Console Python

>>> possibilites(6)
[[0, 0, 6], [0, 1, 3], [0, 2, 0], [1, 0, 2]]

La fonction monnaie_brute renvoie un tuple dont le premier élément est la liste optimale comme décrite ci-dessus, et le deuxième le nombre de pièces.

Exemple

🐍 Console Python

>>> monnaie_brute(6) 
([0, 2, 0], 2)

Compléter les fonctions :

Évaluations restantes : 30/30

.128013cPw*-7 sSfE.bgn38xk9+]èvei;(h4l,mjdo0pI65_:2)=tayC1/[ur050J0z0V0W0A0F0i0h0b0F0W0i0i0U010V0A0M010406050i0$0H0H0W0%0X040j0K0F0$0{0K0p050!12141618100M04051o1h1r0!1o100J0A0y0:0=0@0_0=0p0o0$0W0o0z0f0M0X0V0D1f0h0D0A0o0D0F1T0D0V0~050+0n0F0z1A0?0^011S1U1W1U0V1$1(1!0V0%1p1O0:1b0i0M0W0p0_0S011*1C010k0-0z0p0W0H0z1!1 21261,291(2c2e0~0a0h0c0%0K0M0K0i0A1e0p0h0)1}0%0%0z0b2z1h2h0p1p0!1O2M1_1{1`1#0J2j1D0A0p2b2w1!1x1z0;1+2W2Y0p0K2$1!0M2F1p2K2M2?11202A2(272,0%150F1!0W1R2F0k0_030Q0Q0b2-0z1W2+0K0f0E0f0Z0~0h0Z1h0W2@2`0 2_2i2|1,2~3032340z3601383a3c3e2Z3h0f24040h0S3o3q213s2K2V013x0W311p330D3537393b0)3H2,3J0q3l0q3P2J3r103T3v0_3W3Y053!3$3D3(3G2X3I3i0E3l0E3;1i3?3t2{1B3w0K2 3X3z3#3B3%3F3*433,3i0P3l0P492?3@2`3U3{4j3 3E3)3d4p3g3i0O3l0O4v4b3^4e3`4g3y3Z3A3C4D423f3J0g3l0g4M3R4x3u4P3V4R4i4T4k4V414o4Y3i0r3l0r4%2L4)4d2)4,4h3|3~4l404n4F4@0f0u3l0u4|3S4y3_514S3}4U4m4E3+4H3j0L0~0Z0L5e4~4z4-535l565n4G3J0Z3k045F5v4c5x524B554W4?443j3L0Z3O0!3p3=4(5K5h4A4/4C4=585R0Z3.5H3:5W3Q4}5!4+5$5k4:5m4X5+465H485:5Y5=4O505^544;575o5E4s5H4u614a5Z642}5y5N685C590Z4J5H4L6f4w5?656k5%5O5)6a3i0Z4!5H4$6t3r1s2;1h2$2P0J1{2U5h4E2#1y1p2:0z2=6I6g2L054E6Y2i0A0J0_392K5E3z6*6,695D6C252n0z6=6n5+1!616i1,0t0~0)0k623M6v2}0k0~2v0@0A0n0-2y0z0i77791,0}040C7l713`0~0H1f0+0p0V7r5g4+7o0T0R77106!6(2A6;016-2`3J3L5k7L6A6@3K6_2d6{7M6?597Q5:0h7(0h7m7t042F0p0J2F777*7s010K0~0U7=7+017o0#0w7G7A6)6+7Z6.3i5-7R857T593.0h6`6|5|4q0f897%7)7}73040k4g7|7@0p0~0A8t7B500K0d8w1g7I7?8z2}0n0~0%211J834 277o7q7I7}8v047v7y217z8F7}7_040v8y4*500H0A5s8O3U7D7F8#7@0b5G030h0W0$0h0M1c0/8X7x0V8 0A0x0b7j0h0C2C0Z8 160h0z0s0z0H900z0T828T3T7S0Q873h6:8b7!5R468f7X8h5Q8j5~3P7)9I8G8+278p8r0%8*8P3w0~0I9Q3U8B8D9V5#8J7-8M0z8:5h8R9)5@7u7w8Z9Z4+8%8)8@8H1,8-8/9q9_0_8=9p2^9r9x9u6c8a9D5*8j4s9B2ea86B0fa68m9J9J8o0~9O9;650~0tao279X042Xas3w9#8L1F9(9}9L7n0~8Sa29~3V9.8Y7yax0_9?aO019{5H9,50a07I7HaI846=9u6qa77Z6}8j4Jac7Y8c5Ra(aiaja@alav769^aE7,8xaD9RaP0~0eaV2}0~0c0N0l0Y0l0jb5aF040#be0_aT5ub08;0~81a|b17^0~9@2?9Kbr8V9Ubm5h8%b4bA9-04b8babcbi7~0~bhbE8,8.aUbO8QboaRaQbq4zaqbKbCbK8VbHbbbdbSbfbNa!braT5Vb.bn04bpbv8$7`7{bX5#aL94aR7o8?6ubm9s9u6Ea)a:8j4!a.ae7Uc8a?a@cibwbY7-2b7:aCb=bB0~0mb$0~0W0M0McnbK8Rb-6I8u8wcA0~0GaRbycG04cIb}bFarb+9 bo9oaY8:c67O4^9wce594_cda*8i5p4_2M3p9Ia_2F0V0$0%8Eb_cEcm7/7;cVc5a4cY5ac!c)9E5p5bc(cad66 3paZcD4ycX215E5r4T9sa+5p5t7Wadd4a9dndj3;7@8p75cJ7b8W1f2c0A0z0Q0n0%1dcpdea}bL7pcudBaM8!cq7C0~7Ea1dL7Kd0dh6C5Gc99y8j5Fdpa/d)dnd%a?8U7c2w2x1%7jbV7`cJd?7e7g1W0Vd`cRdNaHdYcl939:e47DdX3R5Kdg0p5E7Q33dlc*eid,c#5+7$c.8nc`8-0pa c_aJ8%b|eydM8Ve9aNc~b=eg5E89ek9xdmeKeodraf5,db3MetaJ9N8scOap041W0ie2bV8Cavc^3rckb~047dd^1(7keb0~c34bc a$d10Z9GeMepd*9A8geR7Uf0eUcia_0Aa{eCbx9#1jcLe6eec`e%e)e_04cUff9W0~020F0V0Bd}8W2Xexe79*e`ed6#a3e~d#3ja6f2f76oabf6d96bfacj7(d=cm12fw0WdSe.b`04eBf%fm0Ae(dK5Ze}86e a(fNfS6Ca-fRd.5Ea=esfVfXevfC3Re/9=d|e!8I0~fifpfkfHaJ8Vfnf/gfdMeceHe7eJ6Cc8f^f}gqeQf_3jcgg0g6508pc;c?e-g57}9+e48V2FfZ0+f$flaJ7ocNfse:g3cLfre|2^0!6%6J6X6L6U1h0V6Og*2S2N0Wd_2M6M7H0)0+0-0i04.

Comparaison des méthodes⚓︎

Le moins de pièces possibles à rendre

Comparer le résultat obtenu pour la méthode par algorithme glouton, ou par force brute pour le cas d'un rendu de monnaie de 6 nl, 10 nl, 22nl . Que constatez vous ?

Solution

montant	algorithme glouton (liste triée)	algorithme par force brute (liste triée)
6	[1, 1, 4]	[3, 3]
10	[1, 1, 4, 4]	[3, 3, 4]
22	[1, 1, 4, 4, 4, 4, 4]	[3, 3, 4, 4, 4, 4]

L'algorithme glouton donne un résultat très rapidement, mais il n'est pas forcément optimal.

III. Le problème du sac à dos ("Knapsack Problem")⚓︎

sac

Le problème est celui-ci : vous disposez d'un sac d'une contenance limitée (sur le dessin ci-dessus, 15kg) et vous souhaitez maximiser la valeur totale des objets que vous mettez dans votre sac. Evidemment, la somme de leur masse ne doit pas dépasser 15 kg.

Ce problème (de la catégorie des problème dits d'analyse combinatoire) malgré sa simplicité est un problème majeur d'optimisation.

Actuellement :

On sait trouver LA meilleure solution, mais en explorant toutes les combinaisons une par une. Cette méthode par force brute est inapplicable si beaucoup d'objets sont en jeu.
On sait facilement trouver une bonne solution, mais pas forcément la meilleure, par exemple en adoptant une stratégie gloutonne.
On ne sait pas trouver facilement (en temps polynomial) la meilleure solution. Si vous y arrivez, 1 Million de $ sont pour vous.

1. Petite aide technique avant de commencer⚓︎

Tri par deuxième élément

Supposons qu'on dispose d'une liste mylist = [["A",3], ["B",2], ["C",8]].

Comment classer les éléments de cette liste par leur deuxième élément ???

Nous allons procéder en 2 temps :

création d'une fonction qui renvoie le deuxième élément d'un objet liste
tri de la liste grâce à cette fonction

Tester ci-dessous

Solution

Il s'affiche : [['C', 8], ['A', 3], ['B', 2]]

2. Retour sur le problème du sac à dos⚓︎

On considère un sac de 40 kg et les objets suivants :

objet	A	B	C	D	E	F
masse	13	12	8	10	14	18
valeur	700	500	200	300	600	800

Quels objets faut-il prendre ?

Stratégie gloutonne

on va classer les objets dans l'ordre décroissant de leur taux de valeur (taux de valeur = valeur / masse). Ainsi le premier élément de la liste sera celui ayant le meilleur rapport valeur/masse.
on prend le premier élément de la liste, puis le deuxième, etc., tant que le sac peut encore les contenir.

trier dans l'ordre décroissant de leur taux de valeur

Évaluations restantes : 5/5

.128013cPw- sSfEbBgn3TxOk9]vei;J(h4l,mjdoqp5_:2)=tay1/[ur050H0w0R0S0x0D0g0f0b0D0S0g0g0Q010R0x0K010406050g0X0F0F0S0Y0T040h0I0D0X0?0I0n050V0}0 11130{0K04051j1c1m0V1j0{0H0x0v0+0-0/0;0-0n0m0X0S0m0w0e0K0T0R0B1a0f0B0x0m0B0D1O0B0R0_050$0k0D0w1v0.0:011N1P1R1P0R1X1Z1V0R0Y1k1J0+160g0K0S0n0;0O011#1x010i0(0w0n0S0F0w1V1`1|211%241Z27290_0a0f0c0Y0I0K0I0g0x190n0f0!1^0Y0Y0w0b2u1c2c0n1k0V1J2H1;1?1=1W0H2e1y0x0n262r1V1s1u0,1$2R2T0n0I2X1V0K2A1k2F2H2.0|1{2v2Z222%0Y100D1V0S1M2A0i0;030M0M0b2(0w1R2$0I0e0L0e0U0_0U1c0S2/2=0`2;2d2@1%2_2{2}2 0w3101333537392U3c0e1 040O3i3k1|3m2F2Q013r0S2|1k2~0B303234360!3B2%3D0o0_0o3I2E3l0{3M3p0;3P3R053T3V3x3X3A2S3C3d0C0_0C3*1d3,3n2?1w3q0I2`3Q3t3U3v3W3z3Z3|3#3d0L0_0L422:1p2,1c2X2K0H1?2P3/013Y2a1k4t1l4r4p2:4A2-2=0f0x0H0;342F3D3f3S4L4N013`4h3a4R202i0w4O4g384i3b3d4S3*3.470;0s0_0!0i3+3K0f453N0n0i0_0Y0S194`2G4}4y0^040A554J3o4;3O0_0I0k0G0#5c575f590P0N5c0{433K4}4M4(4Q3d3F3?4U4(4A3!4,3E4#284%4W4)5G3D5B0V3j5n2!010d0_0f5Y4|5u564:5U0g0H0_020J0X0I0R0y5,5.5:5=5/0y2A0n0v0I0x1!1Z0f520K2q0Y0R0f2+0x0q1p5~0H0*0H02030o0t0y0X2v5i5k0R5^5@5-5_6r0y5s5m3M5x5M5z0e3%4T6A4X4*4Z3d3%0f4$5E3{6J6D1V5R045Z4|5%224?042A0R0X0Y1b5#6U5T2^5h5j5l6*6,1%590W6y4K4y0F0x0_3H6;6X6?0_0u5c6W6`5f0I0_0V756=3:6.6p6_5e5U6@7h465U6|3g7l3N59746*5t2:6z4V4P2=3D3 6F7y5N4+7B5J296O4Y3}0e7C3I7v3l5w7E6C4l7D7K6I7M4l6M5K7X5O4k6S5S717e046o0#0g0M1;5 0g7c7,0179040Q7_775U0n0k0_0g490R0w0H7q580_5b70806-040r0l0z0j0p0h8a5o0_0E7 7i8g0s0w0T8o5U7|7~8e8t3q51530x0I8y22598r6*768D7-2A0v0w0Y0g0w8J1%8A8X4=0b0_0p0Y0X8W8C7m8K0_0P6x6;0V4I1n4r0V4D2I4v1c2L8~0S1Y0w2H4t5t0!0$0(0g04.

Résoudre le problème par la méthode gloutonne

Évaluations restantes : 5/5

.128013cPw-7 sSf.bgn3T8xk9+]vei;(h4l,mjdo0p65_:2)=tay1/[ur050H0x0S0T0y0D0h0g0b0D0T0h0h0R010S0y0K010406050h0Y0F0F0T0Z0U040i0I0D0Y0@0I0n050W0~1012140|0K04051k1d1n0W1k0|0H0y0w0,0.0:0=0.0n0m0Y0T0m0x0e0K0U0S0B1b0g0B0y0m0B0D1P0B0S0`050%0l0D0x1w0/0;011O1Q1S1Q0S1Y1!1W0S0Z1l1K0,170h0K0T0n0=0P011$1y010j0)0x0n0T0F0x1W1{1}221(251!282a0`0a0g0c0Z0I0K0I0h0y1a0n0g0#1_0Z0Z0x0b2v1d2d0n1l0W1K2I1=1@1?1X0H2f1z0y0n272s1W1t1v0-1%2S2U0n0I2Y1W0K2B1l2G2I2/0}1|2w2!232(0Z110D1W0T1N2B0j0=030N0N0b2)0x1S2%0I0e0L0e0V0`0g0V1d0T2:2?0{2=2e2^1(2`2|2~300x32013436383a2V3d0e20040g0P3k3m1}3o2G2R013t0T2}1l2 0B313335370#3D2(3F0o3h0o3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0C3h0C3-1e3/3p2@1x3s0I2{3T3v3X3x3Z3B3$3 3(3e0M3h0M452/3:2?3Q3@4f3{3A3#394l3c3e0L3h0L4r473;4a3?4c3u3V3w3y4z3~3b3F0f3h0f4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0q3h0q4Z2H4#492#4(4d3^3`4h3|4j4B4:0e0t3h0t4^3O4u3=4}4O3_4Q4i4A3%4D3f0J0`0V0J5a1o2-1d2Y2L0H1@2Q5d4A2X1u1l2,0x2.3n3.3N054A5H2e0y0H0=352G3F3g4P5P5R535k5U212j0x5Y5j4C5#2I3l483Q0s0`0#0j5J2H0g5/5d0n0j0`0h0T0b5^5N4{230_040A635{4%0n0`0I0l0G0$0h6a4K4|670E635`6l2_0`2r5P0h0N110r6k5c4%670Q0O630|465K3P5X015S2?3F3H5g6L4.54403G5$295(6M5Z5+3e6Q0W3l0g6+6q6B4|6d040l192T6p6b4|0I0`0R6^6r1(670X0v6G6A5O5Q6!5T3e3*5W776T5!7a6X2a5)4T6V7b3L6,6-4$6/6t0I6v0N60626I5_6_236{046}7y3I7A1(0F0y0`5q7F6H2;6K7d7v6O413v6S6#55420g5%7j4/6V425-3I6,7H3?6e6g6i0N1=0y0x6j7F7p651(7C7E2/7{4v0l5 4c0S0x0H757|0=67697F7-3R7/6h0S7_7P6.660`6o7`8f6:0s0x0U893Q7~8w5|0`0Z0T1a8z6C8o6~8m3s8B0x0w0x0Z0h0x8F6`6|8S230s0b0`0p0Z0Y8R8e6 8b0`0Q748(4u7W790e4o7c7$6U4m8=7h6Z7e6$8{7*7o8f5;040j4c8I7q6s046f8i988a010I0d0`6@8q8)8g9b7:8j7=0Z7@8k5I9m676F7N8w8:7T3d7V7R5*554F7!6Y8^7f9D917o7,9m6:6u0H6w9c0$9e8x8U9l8J7.9o9d8.99700`0X8V7I7K043j9*9f67739z9@0g9B1}4V9E9L8 4W9J7i6!9G6V4W9O9P815d940y5@9#9+9%9T9V9p9Y5d7C0uao6c7s7u7was8T04020D0S0z7 3nadat04al6x0T6zai9^0`9y4s9A7R8;4=8@a77k8`4=a58}7X6VaV7nac9P8r0`6=0@1c9|ap0`0k9/9%0T0K0K2788a=8G68a_9n9W0Sb371b37J7Lb70`0v8,9{8l765Y8;57aW8~5557a#a2bo1W6)7+a+9Q9$9naJawaN9Z040uaE3NaG7raI7t9U0Nb58-bh2w9~0n5U5nbma%8`5p8|br6VbZabbI8W8L0S0Y0Za;80a-6;6?b/478e0W5M5s5G5u5D1d0S5xc02O2J0T1Zb}0W5v6H0#0%0)0h04.

Solution

Il faut donc choisir la combinaison A, F, C. Elle est bien valide (poids 39) et rapporte 1700.

Question

L'algorithme glouton nous a-t-il donné la solution optimale ?
Nous allons pour cela avoir recours à la force brute pour tester toutes les combinaisons possibles.

3. Force brute⚓︎

La méthode par force brute

Nous allons chercher toutes les possibilités pour lequel le poids total est inférieur au poids total autorisé, puis ensuite nous chercherons la possibilité qui donne la valeur totale maximale. Cette méthode, qui consiste à chercher toutes les possibilités s'appelle une méthode par force brute.

La fonction possibilites prend en paramètres la liste objets et l'entier poids qui est le poids maximal. Cette fonction renvoie une liste de listes. Chaque liste donne une possibilité de choix d'objets Par exemple [1, 1, 0, 1, 0, 1] signifie qu'on prend l'objet A, le B, pas le C, le D, pas le E et le F.

Exemple

On a :

🐍 Script Python

objets = [["A", 13, 700], ["B", 12, 500], ["C", 8, 200],\
["D", 10, 300], ["E", 14, 600], ["F", 18, 800]]

Appel de la fonction possibilites

🐍 Console Python

>>> possibilités(objets, 15)
[[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0]]
>>>

La fonction butin_brut renvoie un tuple dont le premier élément est la liste optimale comme décrite ci-dessus, et le deuxième le magot obtenu.

Exemple

🐍 Console Python

>>> butin_brut(objets, 25)
([1, 0, 0, 1, 0, 0], 1000)

Compléter les fonctions :

Évaluations restantes : 5/5

.128013cPw*-7 sSf.bgn38xk9é]vei;(h4l,mjdo0p65_:2)=tay1/[ur050H0x0S0T0y0D0i0h0b0D0T0i0i0R010S0y0K010406050i0Y0F0F0T0Z0U040j0I0D0Y0@0I0o050W0~1012140|0K04051k1d1n0W1k0|0H0y0w0,0.0:0=0.0o0n0Y0T0n0x0f0K0U0S0B1b0h0B0y0n0B0D1P0B0S0`050%0m0D0x1w0/0;011O1Q1S1Q0S1Y1!1W0S0Z1l1K0,170i0K0T0o0=0P011$1y010k0)0x0o0T0F0x1W1{1}221(251!282a0`0a0h0c0Z0I0K0I0i0y1a0o0h0#1_0Z0Z0x0b2v1d2d0o1l0W1K2I1=1@1?1X0H2f1z0y0o272s1W1t1v0-1%2S2U0o0I2Y1W0K2B1l2G2I2/0}1|2w2!232(0Z110D1W0T1N2B0k0=030N0N0b2)0x1S2%0I0f0V0J3d0`0h0V1d0T2:2?0{2=2e2^1(2`2|2~300x32013436383a2V3d3f20040h0P3k3m1}3o2G2R013t0T2}1l2 0B313335370#3D2(3F0f0p3h0p3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0f0C3h0C3.1e3:3p2@1x3s0I2{3T3v3X3x3Z3B3$403(420M3h0M472/3;2?3Q3^4h3|3A3#394n3c420L3h0L4t493=4c3@4e3u3V3w3y4B3 3b3)0g3h0g4K3N4v3q4N3R4P4g4R4i4T3~4m4W420q3h0q4#2H4%4b2#4*4f3_3{4j3}4l4D4=3f0t3h0t4`3O4w3?4 4Q3`4S4k4C3%4F3f3e0`3e5c4|4x4+515j545l4E3)0V0V5q3j0W3l3/4$4a5u504z534U4;415o3H0V3K5G3M4{5K5f4y4-4A4:565R3d3+040V3-5W5I5Y4M4~5#5i4.5k4V5*0V445-465:485J5?2_5v5N4/555m5B4q5-4s624u5Z4)5^52695z573d4H5-4J6g4L5e6j675$5O5(6b420V4Y5-4!6t646v5@6x5_5%6a5A6C4@5-4_6H5=6J665M6y6m5|4o5o595-5b6U5d4(6K6Y6M6z6O6o0P0J0`6@5s6i6.5h6l5{5Q6$0f0P5D04746{654d6/6 5y6#5n733H0P5V5H636V6-6X6~5x5P5)720P5,7u786W7a7p5`7d717f0P5 7F5c1o2-1d2Y2L0H1@2Q5f4C2X1u1l2,0x2.3n5;1l4C7Y2e0y0H0=352G5B3v7)7+6=5}212j0x7;6n7?2I5H790=0s0`0#0k7!0h6|2_0k0`2r0:0y0m0)2u0u0i7!871(0_040A8j7 3R0`0I0m0G0$8i7l7%4}238m0E858k3@8a0I7)8x2;8q8m0Q0O7!0|8y5K7:017,2?3)3H5i8U6A6P3G7@297_8V7=7t1W5W0h8;868q0o8a2B0o0H2B8E8q0I0`0R8~7y0=8m0X0v8Q8p4w8#0N7-425,8!7*8,7{723+0h7^7`7e3)9g8:8=8F0181040k4e937n3s0`0y5F2/8?94010I0d9E1c8y9I9C3@0m0`0Z1}1F9a9R018m8o8S8q0F0y6_9Y8A8l0`8O999%9b9i8W1}3)5 9h9p7D9`8)2a9}7s7f9{9t8=9u8q9x9z0Z9B9-8G040y5V9H9v9L9Nad4x9T049V1B0x9,3Q9#au5f9)9+9=9Z8N8P8y8R8L9?7;9e3f6d9|9j9q4pa08+8$6oaMa6a7aX9vaa9A9P9v8^ag5/aj8 9Mag9Oa+9J0oapar9XaBae9!0`9$aH9Zaz76ax4)aD9;a~2w9caK0f6qaNaT5*4H9n8*a26B3fbbaWaXbn9Qa`a!aca$8@9E61a:9Zala.an5!a?9Wata_ava|b24~b0ai7Z8M9/aE6hbGb88X426Ebc8-7f4Ybga1aO9~bV8/3lbob,aYa90`abbB6j9E6fbxa`bz2Tb=5@bDasbJ8BbIbGay9*b1c4b3bPb5bNaI8,b96RbX9k7f4@b#aSbY3)cgbmb-craZb:a#b_4x9E6scw5fb{a/3nbpao9UbEc19.8ncJ0=bLcMa{049:aFaubT9_426(chaP58aRbi8%0fcYcqcrc,cF5!9U0x2r0o0ibFcA4)900492bt9J96cPa(9FcP8Cb}2_9EbM3N9vd5c~9Zd2a*ccaC0`8Ddda`d2bwdha`dcc_5@b@d4djd69DagczdpbH0498cTbS9@9dbU5o6^4R9cci5B6^clc%6o5p7}3Ic-dX8;a%8H8J0N2Bc=c@dx0=c{c}ds2_ap1fdv8n0Xd1c:d)c^dB5fd0c8dtagd?dEb63Qc{0ed_048t8v0S8Kd}c904d^e0d7e2ejcK0veie5c55qe3d+9wcubsd/dy0yeucCeua=cHc0em95c3eq4)b0dAdabOcR0v0QcbeOcd9^0o5B75cZb(5o5DdRb%a3eYb*dWdYc-ctag84dlcx042rd$d(1bd*e?cB0`020D0S0zeDd#0HeeeUdi04bQ49dGaJdJ3d8Z2 dNc!fhc$e)bjfmdVe.fsc.b?e^8`8|d|f9b`0`0le90T0K0K270Hd?0Aepefe1d3eHcQdkeyafahd?fScEd!a)fWf5agdofAdCfX3NfufOb^fNc204f+2Hf-ek0yeN2Hdb0`eReTf|3PcVeX6C9gfjdHdOg5fnbd725.e,a7e:2B0S0Y0ZcDf,fZ7W8{8}dFe5g35B9{g7dS5}44e(gc7f5~e,aGdBgu6CaMgxfoc(0V4qgBcngJe,e:83eD89040m192T0N0m0Z19fKe9eb8wf#e~fve_f7d?cSbRgtdHb90VbbgLgC5Bbf9ogMdTblb+a8a;8H8c1Z0xf8f@ak91f$8b2t8e1S0S8hg*fQa(g,edg.fT8re^8Ig=fQ8Ng08z0hgI5obWg~gRhFgbhI3dbWaWfZ110reAfQd-eub00JhB8Tg`fg0VcghHg95ockh2g 6Qgfh7dec:0~f20T0SeBhgg/4~96e4fdg_ffcW6%7/g8fl0V59gQh)3dc*h6dZb/9ycvfYbu041S0i0Sfzhea,amh|ekhi8d1!hdhCd~0`fc5Jfecefg6@i5gy7tdQh,hLiHfrbofZ121F0oh_it1(hUiW9S0`d=hza|fMf)c/il0yinipizegi)g1h8eleKh}f~cPe7g+8ug-i%ehe9hSi_f;eocPcOj1h gnigb;iZhvj4ij9JeCjfeEaqcIj1a}f:1(eMg?f gsgHh!i373eZh(fl74hKibjEiPbne:0ye=hua(iS27iVhuc{020nf3f$hQjhi*egiC5YiEeW8YfihDi6e#7gjFjD8Zc+b.i@2Bh?0%jRjibyh{jN0`imiohYg2jyg43Gg6j,iJ7E9miMjG9sieb-hP0ThRi|j j}dm0`jPiUk4eVdIjz7FiIh35*kxiajDa5khgh0$gkgmiqc eJjrafj_0Yh@j|j!i`f=jXkkjZi?faeSjwda0W7$7J7X7L7U1d0S7Ok.2O2J0Thb2I7M8R0#0%0)0i04.

Solution

La combinaison A-B-E est bien valide (poids total 39) et rapporte 1800

Mon info

La force brute a mis en évidence une combinaison meilleure que celle donnée par l'algorithme glouton.

En effet la combinaison A-B-E est bien valide (poids total 39) et rapporte 1800, donc 100 de mieux que la solution gloutonne.

Par contre, la force brute est inenvisageable pour si le nombre d'objets est grand, alors que la stratégie gloutonne reste très rapide.

4. Pour approfondir⚓︎

interstices

V. La chasse au trésor⚓︎

tresor

⌛ Elle arrive ...

VI. Conclusion⚓︎

Mon info

La stratégie gloutonne donne très rapidement des solutions satisfaisantes mais pas forcément optimales. Pour beaucoup de problèmes (dont le problème du sac à dos), la recherche d'une solution optimale sans passer par la force brute semble impossible (mais n'est pas démontrée).
Dans ce cas-là, la stratégie gloutonne peut être employée pour avoir vite et bien une solution convenable, même si peut-être non optimale. On dit que la stratégie gloutonne est une heuristique de résolution. On sait que ce n'est pas forcément optimal, mais faute de mieux, on s'en contente...

VII. Crédits⚓︎

Le III. La résolution gloutonne du problème du sac à dos est une mise en forme du travail de Gilles Lassus.