Le problème du voyageur de commerce⚓︎

Exemple utilisé pour cette partie

Pour ce problème, nous allons utiliser un tableau de taille $n\times n$ pour représenter les distances entre les villes.

matrice_exemple = [[0, 55, 303, 188, 183],
                   [55, 0, 306, 176, 203],
                   [303, 306, 0, 142, 153],
                   [188, 176, 142, 0, 123],
                   [183, 203, 153, 123, 0]]

Cet exemple correspond à celui du cours.

Exercice 10

Compléter la fonction voyageur_commerce_glouton qui prend en paramètre un tableau de tableau matrice et qui cherche le plus court chemin en utilisant l'algorithme glouton.

On part de la ville 0 et ensuite, à chaque fois, on cherche la ville non visitée la plus proche de la ville courante et on passe à cette ville. À la fin, on rajoute la distance entre la dernière et la première ville pour le chemin du retour.

La fonction renvoie la distance trouvée et le chemin passant par toutes les villes. On ne rajoute pas la ville 0 à la fin de la liste, mais c'est sous entendu qu'on revient à la ville de départ à partir de la dernière ville visitée.

Pour initialiser le minimum

Afin d'initialiser le minimum, on prend la valeur float('inf') qui correspond à +∞.

Exemple d'utilisation

>> voyageur_commerce_glouton(matrice_exemple)
(810, [0, 1, 3, 4, 2])

Évaluations restantes : 5/5

.128013.8734;)3=9x+lwjn8gv,S."5/:rf7uemkèdas p h10itP(_y2[46cb]-o030z0v0J0A0I0d0B0C0S0d0A0B0B090n0J0I0D0n020E030B0u0w0w0A0r0N020l0W0d0u0:0W0g030p0`0|0~100^0D02031g191j0p1g0^0z0I0j0(0*0,0.0F0I0i0F0d1x0F0J0?030!0T0d0v1s0+0-0n1w1y1A1y0J1G1I1E0J0r1h0J0F0(130B0D0A0g0.0O0n1K1u0n0s0$0v0g0A0w0v1E1%1(1-1M1:1I1?1^0?040C0K0r0W0D0W0B0I160g0C0Y1#0r0r0v0S2d191{0g1h0p1Z2q1W1Y1X1F0z1}0.1A0g1=2a1E1p1r0)1L2A0I2C0g0W2G1E0D2j1h2o2q2U0_1'2e2I1.2N0r0}0d0?0C0G2n2Y0@2X1|2!1M2$2'2)0O2,1(2.2o2z0n2?0A2(020C082`2p0^2}2;0.30320C0Q362|2Y2~3c2)0o3g383i3a2 0W2%312)0R3n2/2Z1t2=3s2@330t3x393A3b3C3u330h3G3p3I3r3t3d0a3O2:3Q3k020G0H3V3z2J3R3D0G2+1a2-3o3W3'3Y0G2_3,2{3.3%2#3K320G353@373y3j3|0?0G3f403h3/3{3S453m483_434c3Z3w4f423q3;3F4l3H3:443Z3N4q3P4s4i0G3U4w4a3B4i0O3#4C3`4E3D0O3+2U4g4n4t0O3?4O4m3X4R3 4U4r4b4L472W1m2S192G2t0z1Y2y3q0S2O1_1h4+1i4)4'2W4;0Y2T4x2#0?0}1W0I0S0v0M0v0b0v0w0D1I3g0C4V3'0W0?095f5h1.0=020P0P3g5n1M0w0I0?4H2W4!1M5p0k5m5B0.5w0?0o4e5A505C0?5E485g5G0n5I02080H4Y2-5u0.5D5F5N5H5x4u4v5M4D5$5P5'5.5U5*0G0h5Z2{5#0n5p0U5Q4O0C62636465645|5p5s485|5V5K5t5T5%5R6c5*5z5!6g5:6i5T5V5X4k5-4J5/02602-5S5(5?450t6t6m6B6h2U6A5=5V4G5`2p680?5 3n666U666Q5q6f6B6r5Y6Z5=6I6z6j0?6s6%6v5}6o6J6*026l5{6n6x5;6.5V464T6G6'6:6)6q5@0o6O4 71026S4f6V7d626X6a6u2~6}0h5,706.6(2{6K6|5@6E6-2~7p2p7r7j5@0Q6 6^6H727q6=6@6P6_6y7H74450O776X7b617e6V7g7v3q7k7R7L6{7A0?6N7Y3Q7x336=0G767*3'7,7z7Z5@7Q7;5o7G7y7I7{5O7a0U3n4P3Q0x0?0Y0s7%4n0s0?0j0W0N0A0i0v0u0r0M4;0|0v0r560M0i0d0W1517806w0L8z2 520A54568C5p070q6T635|0g0?1'8r8w0r0B8b3Q5j025l6p7F6Y6b7O6?8I6R8M7f5T8P020j0$1I8n8T1(0J0v8W5i5k8|1.5V7J0@678.880I0B0!0g8s0J0W0!5e8#5=8Y8!6;8(920E946B87020s3s8 2=0?0I9u0.0W0e9w189g6.0g0T0?0r1(8j8*028B8'6B9G0?209M9O7i4n8E8G8{9P79078C8Y0V8C6}9M8K8,658O8e8=570*0M5d0u0B9^270S0F9!9k6B9i9y6C8)7c6U9:020z0M5w9Da19h8~9E3j9H9r8v8F9U8C0B0G0?0001080a062L0satav069,5f7@3Q0Sar02010C0c059.9o5=8/1p981(568Vai3qa3aX3X9Y0r55a07n7w0?7ha)9X8:9=8@8l8_a(7E7983a76W5T9q9s0ra48/0fa49A9Cb1ak9J0g9L9#7o0?9Va-3Xak9Tbca*9N8CaR9799aV9,9-a{7d5|9q0I8aa!3:0?b3bA1.b5022N0Jb49B022Lb18Q0~4;8laWaf6.bG1(0zbOaabpaU0vbTbg7=a+bnbC9Ma`bU2~8Y000d0JaCbE9vaaacbNbk3q5p8Lbu7VaFbBb{adb4ahb/a.aSbqb%9Ma,a^9Fb,b~7+8+c27Va98;0d8?9@9_9{2R0W9~a@7~5TaZcaa#02bD7Ua|9Q96aT9a579c9ecz7-cBc973cJb!cL9b9d31cQc4bF0?0cbZabc7cn8-cV8RbR8U9'0?0mb+020A0D0D1=bYckb)bmc 51a/cr9?0A9^14cv9}9 aDc,c$b`cq8?c:a?c88ZbZdhd6d89`9|cxdcbu5|aH0?aK170C9J0f8w8`0C0*2fb#cM0C1=1W1JdH2R5b0I0y2j0Cdo0Cc/8T0u1J0ZdG0A2f8q0gdS2j9.a9ccb$0McOc!dl0c9jcUaQa$a'cfc^do0Mctd9dscyb-cg7K6!6kb-d-a}9I0Z8laed`cicWcdd;cZ9f9Wcl6`b_3bbP8SbS3x0p4}0v2qdQ2q4^2r4-192ueH0A1HeA4*1q2.0p0Y0!0$0B02.

Tester toutes les permutations

Afin de chercher la solution optimale, nous allons tester tous les chemins possibles. Cette fois-ci, cela se traduira par l'utilisation de la fonction permutation du module itertools.

Exemples d'utilisation

>>> import itertools
>>> list(itertools.permutations(range(3), 3))
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

Cette expression permet de générer toutes les combinaisons possibles avec les nombres de 0 à 2. Comme nous l'avons vu, ce n'est pas la peine de tester tous les circuits. On peut fixer le point de départ. On prendra donc les valeurs à partir de 1 et on rajoutera ensuite 0 au début.

Exemple d'utilisation

>>> list(itertools.permutations(range(1, 3), 2))
[(1, 2), (2, 1)]

Cela permet de réduire grandement le nombre de chemins à tester. Mais si lorsque le nombre de villes augmente, ce nombre deviendra quand même rapidement gigantesque. Il n'est pas conseillé de tester l'algorithme par force brute avec plus d'une dizaine de villes.

Exercice 11

Compléter la fonction voyageur_commerce_brute(matrice) qui cherche le plus court chemin en faisant une recherche exhaustive.

Puisque les permutations sont données sous forme de t-uplets, on doit utiliser (0,) pour rajouter 0 au début du chemin considéré.

Exemple d'utilisation

>>> voyageur_commerce_brute(matrice_exemple)
(709, (0, 1, 3, 2, 4))

Évaluations restantes : 5/5

.128013;)3=9+lwjnR8Vgv.S,à"5/:rf7uOemkèédas p h10itP(_y2[46cb]-o030C0x0M0D0L0b0E0F0V0b0D0E0E080o0M0L0G0o020H030E0v0y0y0D0s0Q020l0Z0b0v0?0Z0e030q0}0 11130{0G02031j1c1m0q1j0{0C0L0j0+0-0/0;0I0L0i0I0b1A0I0M0_030%0W0b0x1v0.0:0o1z1B1D1B0M1J1L1H0M0s1k0M0I0+160E0G0D0e0;0R0o1N1x0o0t0(0x0e0D0y0x1H1)1+1:1P1?1L1_1{0_040F0N0s0Z0G0Z0E0L190e0F0#1'0s0s0x0V2g1c1~0e1k0q1$2t1Z1#1!1I0C200;1D0e1^2d1H1s1u0,1O2D0L2F0e0Z2J1H0G2m1k2r2t2X0|1*2h2L1;2Q0s100b0_0F0J2q2#0`2!1 2%1P2(2*2,0R2/1+2;2r2C0o2_0D2+020F072}2s0{302@0;33350F0T392 2#313f2,0p3j3b3l3d320Z2)342,0U3q2=2$1w2^3v2`360u3A3c3D3e3F3x360g3J3s3L3u3w3g093R2?3T3n020J0K3Y3C2M3U3G0J2.1d2:3r3Z3*3#0J2|3/2~3;3)2'3N350J383`3a3B3m3 0_0J3i433k3=3~3V483p4b3|464f3$3z4i453t3@3I4o3K3?473$3Q4t3S4v4l0J3X4z4d3E4l0R3'4F3}4H3G0R3.2Z1p2V1c2J2w0C1#2B3t0V2R1|1k4V1l4T4R2Z4#0#2W4A1;0z0e0_0L0y2c0s0M3j0F4p3!4?022f0x4{0Z1(3q4j3t0z0_0#0t4}4 3?0t0_0j0Z0Q0D0i0x0v0s0P4#0 540V0x0P0W0s180x3j5g1;0^020O5D4u2'0_101Z0L5w5J4:1P5G060r3q0F5Y4~5K2^0_1b4b5!5S0;0Z0_085f5#3e0W0_235R4G0;5G5I4b5E5$025N0s5P5C5}5:0o5U5X5Z5~3e0_5t0W2O0'0E1a0E5/5*0o5,025.5(6b324@0M540M560)5^4M5+0_0k6A3m0_0G540y180D2g6k656m5{6F4q5=020s1+5o6S3T6R6P5_0o0y0L486Z3*5G0m6l6%515'2Z665U6.6r666;6+1;6o0Y6}1P6(6*6$6B670_06695Y6s511{0(1L5q6/766o6q2X5)6%5G0S0X7a7n76510G0L2m7i317k7z3t7p7r4i5Z7t6G020b1a0i0v5p5r6(6=2:7I3t7B6`6m0e6U0t7L6M715`0_5|6?6m0E0J0_00010709052O0t7:7=057'7702797G6a665b020t3v7C3!6H114#5q6O7m6s0Z0c4@7S2~7U89026e6g0L6i0e8e2:6s5G5W817H7b660V7.02010F0h7f1M2j0C0B1*4{0F0n0F0-0F2U0x6(0A2m0F0j8r2f0B642X0H8A827Y5?7M7O7h7X6%7W8f6{5M6M625Q75317p7}73024K7+7o0_0X0S7}7v8b0Z8d7}908~3t92948v6@977F8)8+8B6m8D0_8G0w2h6W0d9d6v0F6x0v0*1L0*8M0G0-5w1{0e0M9H0v8U9c9e8z8A6s84860s883?4@9!6~8i528k2s8m3?6U6W0e6Y9h6!7)9a6U5@9=6,9@9{5L028O8c0s8u2~8w787}6 916)3$9f788y9p9q7H7c8.9:8:9Z8=7j5-9%5 7Lal7Par6C020aaw6t608{63ad02999~5 a19da3aFaH957u9$aI7(020X989a8a0sa2a42sa6aGaX52a80_azaS6'ab4Q9l6Q9n7sai8C8E8G0f0$aL8Q8S0D8!8J2i8K8N114|9Ua^8-7K8/avao7Aaqbf4qak7Nbe8^6m6oa,bn6:8`5O8}aP8 0_aOa;bsa09SaMa-9gbw7V0_70a-92a:a59maUaWbLab9kbOa=aUa@8,6%9t8F0F9w0F2m0i112j2e0F1ab21^0Mb49C2a0v0j540F0v2F0F7e0b7g8Z6i172pb9bZ76840L5ebi8natbl8;brap02000b0M7|cd9#bcau5q0P7RaFaf3:ahbabBc0c2aA8@7Ta%7*bA769jaF0m80cibgayaA9baZaLa#0`czc87Jcfamcu2OcEbhcPbjcrcganag9r6%842m0M5q9*36ajc,c$cvbF0_6_c*8ncCbm3:1c4-0x2t8V2t4(2u4X1c2xdg0D1Kd94U1t2;0q0#0%0(0E02.

Comparer les algorithmes

Afin de tester ces algorithmes sur d'autres exemples, nous allons générer des points dans un repère et calculer les distances les séparant.

Exercice 12

Écrire une fonction genere_points qui prend en paramètre un entier nb_points et qui génère une liste de couples (x, y), où les deux valeurs sont tirées au hasard dans l'intervalle $[0;100]$.

Pour générer les valeurs aléatoirement

Vous pouvez utiliser la commande random.uniform(0, 100) qui renvoie un réel choisi au hasard entre 0 et 100.

Exemple d'utilisation

>>> random.uniform(0,100)
10.506382593738529

Exemple d'utilisation

>>> genere_points(3)
[(98.35288913986197, 45.75239295229048),
 (69.75253012777488, 99.14961943360957),
 (11.91408689187744, 17.876060649733528)]

Évaluations restantes : 5/5

.128013;)3=9xlwqnR8gv.S,"A5/:rf7uOemkédas p h10itP(_y2[46cb]o030A0w0K0B0J0b0C0D0T0b0B0C0C080m0K0J0E0m020F030C0u0x0x0B0r0O020k0W0b0u0:0W0e0D000B0x0E050D0f0w0}0r0d0u0w0C030p0`0|0~100^0E02031v1o1y0p1v0^0A0J0i0(0*0,0.0G0J0h0G0b1M0G0K0?030!0U0b0w1H0+0-0m1L1N1P1N0K1V1X1T0K0r1w0K0G0(130C0E0B0e0.0P0m1Z1J0m0s0$0w0e1b0w1T1^1`1 1#221X250x2702040D0L0r0W0E0W0C0J16180Y1?0r0r0w0T2s1o290e1w0p1;2E1.1:1/1U0A2b0.1P0e242p1T1E1G0)1!2O0J2Q0e0W2U1T0E2x1w2C2E2+0_1_182W202#0r0}0b0?0H2B2/0@2.2a2;1#2?2^0?0P2|1`2~2C2N0m330B2_0207372D0^3a310.3d3f0R3i392/3b3o0?0o3r3k3t3m3c0W2@3e0?0S3y2 2:1I323D34020t3I3l3L3n3N3F020g3R3A3T3C3E3f093r1z2)1o2U2H0A1:2M3B0T2$2h0X1F1w2(0w2*2}3)3?0Y3~303#0y0e0?0J1c3D0K3r0D3J3u47020r1`0A0W0x3y3z442X0m0y0?0Y0s4d4f3B0e0s0?0h240w2x0N2o2Z0K1n1p3 3S4r0=020M3)4O2=0?0e0U4H0W4J4L2-4U1#4Q060q3y0D4-4e4'3n0?2x0`0b0!4c4M384/3!4r0W0?084x4:0m4Q0Q0V4,4.4y450?0s3D534~4V020J5g4q200W0c480e5l3K4r4X4=1`4D4T5h4(0?4S4{2D5b5u4W4Y4I0e4K5z5m5B024*594.5a544h0a5s3b5002525E024}5O4;4i4k4m5N5t5n0?0j5.3u0?0u0e0J5e2@5?3B4Q5D4%5A0.0x0J0?0I5~3#4Q0l5Y3B652`0I685%5G204)5S5T5(5/320?0O6d3#5!5$2+6p5@5+0e4l4n6j545!5=6F633c5^5`5|6E625)555C694r6f026i6Q6q0.6b6u6V66020H6h6U6l0?066n5T6k6r4i1m0u4^0B4`6Z5Z5;6,6?0B0E0E240A706#5C614N6K5W776S026c5%6z4z6s7e4)6/5%0F6;544t6@0K0u0r5r7i6=5*4?6_4_3I0p413}3*7I0p3-1o0K3/7N2K2F0B1W7K3-1u436!0m2x0x0N0s0B0y0w0N0G070?1g1i1k1m0D4+6j1B2~1v0v1874150D0B0u0,0J0D150$0J0C4F852Q0D1P0C0K1Y0A0z225`1Y241?1c0r0z0G242q177?1z2~2U3b1%1O1Q1S7Y3b2d24260?0n152x0D0C1386173)3|7Y2,3 7H8F3B7t4v6%2=4B024D2Q4G5K5M6J6R607e4h4X4Z4#7m6.7@2+7q5U6K7t2x7v7x8%5P0Q7a387A6L6B6D7e6H8=6M5{3N8`4R7e6W6Y7b8:0?7h6y9a6W6*9o99544)9s2}7j3#4h4j6C5-8/7Z9f9J6A5_9i5}9M5 6T9R3#9n9k9B4|9u6(9w9k067o9t7s5d5f7z5V48950.5o5q9:3c0U5w0e5y9U4P9T6}7k028@8-4$9p7Z4)587p1o8Y7J2E7W3,0Z0#0%02.

Pour calculer la distance entre 2 points

La fonction distance prend en paramètres deux couples de réels pt1 et pt2, et renvoie la distance euclidienne entre les deux points.

import math

def distance(pt1, pt2):
    x1, y1 = pt1
    x2, y2 = pt2
    return math.sqrt((x2-x1)**2 + (y2-y1)**2)

Cette fonction est utilisable dans les exercices suivants.

Exercice 13

Compléter la fonction calcul_matrice_distances qui prend en paramètre une liste de couples de réels liste_points et qui renvoie la matrice des distances entre les points donnés.

Exemple d'utilisation

>>> calcul_matrice_distances(genere_points(3))
[[0, 82.42860061936726, 36.90459181116363],
 [82.42860061936726, 0, 85.34081684848618],
 [36.90459181116363, 85.34081684848618, 0]]

Version videVersion à trous

Évaluations restantes : 5/5

.128013)3=9+lwjn8gv,S"5/:rf7uemkdas p h10itP(_y2[46cb]o030u0r0E0v0D0a0w0x0N0a0v0w0w070j0E0D0y0j020z030w0q0s0s0v0n0I020i0Q0a0q0*0Q0d030l0;0?0^0`0/0y02031a131d0l1a0/0u0D0g0Z0#0%0(0A0D0f0A0a1r0A0E0-030U0O0a0r1m0$0'0j1q1s1u1s0E1A1C1y0E0n1b0E0A0Z0}0w0y0v0d0(0J0j1E1o0j0o0W0r0d0v0s0r1y1X1Z1'1G1*1C1-1/0-040x0F0n0Q0y0Q0w0D100d0x0S1V0n0n0r0N27131=0d1b0l1T2k1Q1S1R1z0u1@0(1u0d1,241y1j1l0!1F2u0D2w0d0Q2A1y0y2d1b2i2k2O0:1Y282C1(2H0n0@0a0-0B2h2S0.2R1?2U1G2W2Y0-0J2$1Z2'2i2t0j2,0v2Z02062:2j0/2?2*0(2_2{0L2~2=2S2@340-0k373039322^0Q2X2`0-0M3e2(2T1n2+3j2-020p3o313r333t3l020e3x3g3z3i3k2{08371e2M132A2n0u1S2s3h0N2I1:1b3Q1c3O2Q142%033W0S2N3G2D0j0t0-0S0o370x3p3a0o0-0N2`0N0q0a0H0@1Q0D0N0r0H1j0w0U0d460w3M3y3.0,020G4f3-2V0-1u4a47232F0E4e3'2;3_3h4i050m3e0x4E3^4g4n02124w2j4G4m1G0Q0-073@4y3H0d0O4o1,4l2)3H4i4k4L3,4#3.0d4o0D4q0H4s0d4u4!3q4h0-054D4F4U4+0-430n450r4T4H4P4R554O0(4i0K0K4@2@0s0D0-0C594*1(3:020o3j5l4^4I0D5s2@0Q0b0-2F5w3h4W0-0n1Z0f544(4~1(4%5f5D0-4K2Q565b4`0P5C3H5o5q0n5X4 020c5$1(5y5A5R2%4N5m2+4X025G0d5I5O4$0-4'5S5a2^5Q5`4_02055W4(0z4F5/5t1G5Z5r4(6a3a5A5)4P5z025B6f5L5;5F5H5J5~5:5U4j624I5-4x5T0j4A4C6769696p0(6d5#6o6C4,5'6j0(5+6m6A4M6J2^5=5@5_5K6C5N6$5 6P5v6(6v0j4Q02096y1G5h2!6=6w0h6R604J6_6D4`6F2O686H756X6P0u6|6/4S6N6)3;4.4b466 6'6u6b334-4/4;4?6,7m70025e7s6h6m7j0-0P6{7d6-6P4p0E4r0Q4t4v7l2@5c6 6P5(7x4z7B4{6G756H77500v447i7T5{7v7Q6i7(630P7w7N5P6Q7-5M7B7a587E7t784|7Y4}6O7#7%6t3(6%0-7:867e7?7;7)7/7+7z7@1G4i662O6g3h7b6|7~7X4E6X5o2d0E0q0n6V028n4V83527'73133*0r2k2L8K3P1k3R2n2q2l0v1B8N0l3Q0/8X0T0V0X02.

Évaluations restantes : 5/5

.128013)3=9+lwjn8gv,S"5/:rf7uemkdas p h10itP(_y2[46cb]o030u0r0E0v0D0a0w0x0N0a0v0w0w070j0E0D0y0j020z030w0q0s0s0v0n0I020i0Q0a0q0*0Q0d030l0;0?0^0`0/0y02031a131d0l1a0/0u0D0g0Z0#0%0(0A0D0f0A0a1r0A0E0-030U0O0a0r1m0$0'0j1q1s1u1s0E1A1C1y0E0n1b0E0A0Z0}0w0y0v0d0(0J0j1E1o0j0o0W0r0d0v0s0r1y1X1Z1'1G1*1C1-1/0-040x0F0n0Q0y0Q0w0D100d0x0S1V0n0n0r0N27131=0d1b0l1T2k1Q1S1R1z0u1@0(1u0d1,241y1j1l0!1F2u0D2w0d0Q2A1y0y2d1b2i2k2O0:1Y282C1(2H0n0@0a0-0B2h2S0.2R1?2U1G2W2Y0-0J2$1Z2'2i2t0j2,0v2Z02062:2j0/2?2*0(2_2{0L2~2=2S2@340-0k373039322^0Q2X2`0-0M3e2(2T1n2+3j2-020p3o313r333t3l020e3x3g3z3i3k2{08371e2M132A2n0u1S2s3h0N2I1:1b3Q1c3O2Q142%033W0S2N3G2D0j0t0-0S0o370x3p3a0o0-0N2`0N0q0a0H0@1Q0D0N0r0H1j0w0U0d460w3M3y3.0,020G4f3-2V0-1u4a47232F0E4e3'2;3_3h4i050m3e0x4E3^4g4n02124w2j4G4m1G0Q0-073@4y3H0d0O4o1,4l2)3H4i4k4L3,4#3.0d4o0D4q0H4s0d4u4!3q4h0-054D4F4U4+0-430n450r4T4H4P4R554O0(4i0K0K4@2@0s0D0-0C594*1(3:020o3j5l4^4I0D5s2@0Q0b0-2F5w3h4W0-0n1Z0f544(4~1(4%5f5D0-4K2Q565b4`0P5C3H5o5q0n5X4 020c5$1(5y5A5R2%4N5m2+4X025G0d5I5O4$0-4'5S5a2^5Q5`4_02055W4(0z4F5/5t1G5Z5r4(6a3a5A5)4P5z025B6f5L5;5F5H5J5~5:5U4j624I5-4x5T0j4A4C6769696p0(6d5#6o6C4,5'6j0(5+6m6A4M6J2^5=5@5_5K6C5N6$5 6P5v6(6v0j4Q02096y1G5h2!6=6w0h6R604J6_6D4`6F2O686H756X6P0u6|6/4S6N6)3;4.4b466 6'6u6b334-4/4;4?6,7m70025e7s6h6m7j0-0P6{7d6-6P4p0E4r0Q4t4v7l2@5c6 6P5(7x4z7B4{6G756H77500v447i7T5{7v7Q6i7(630P7w7N5P6Q7-5M7B7a587E7t784|7Y4}6O7#7%6t3(6%0-7:867e7?7;7)7/7+7z7@1G4i662O6g3h7b6|7~7X4E6X5o2d0E0q0n6V028n4V83527'73133*0r2k2L8K3P1k3R2n2q2l0v1B8N0l3Q0/8X0T0V0X02.

Exercice 14

Comparer les résultats trouvés avec les deux algorithmes avec des listes de longueur 10 au maximum.

Vous pouvez aussi copier puis modifier la version par force brute pour qu'elle renvoie également la longueur du pire parcours.

Évaluations restantes : ∞/∞

Exercice 15

À l'aide du script suivant, observez le chemin trouvé par l'algorithme glouton.

Évaluations restantes : ∞/∞

Le tracé sera affiché ici