Niveau d'optimisation: 2020#4

J'ai une solution pour le challenge qui quand on lui passe une entrée aléatoire de 30 planètes et 30 étapes dépasse largment les limites de mémoire et de temps de calcul. C'est que mon algorithme est trop peu performant ou qu'en pratique les test sont prévus pour rester assez petits en temps de calcul?

Pour info, je code en Go, et mon algorithme est le suivant:

=ETAPE 1=

-partir d'un planète du bon type

-toujours aller vers la planète du bon type la plus proche possible

-récupérer ce nombre de déplacements effectués

=ETAPE 2=

-explorer par un graph toutes les branches tant que leur longueur (en déplacements) est inférieure à celle trouvée avant

-récupérer la plus petite

Sachant que l'étape 2 est parralélisée.

Mon algorithme est mal implémenté, ou il est juste pas adapté?

===EXEMPLE DE D'ENTREE===

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

30
30
598099 701688 17
640942 916060 25
676311 571110 12
961407 542666 4
837799 892209 13
753206 766721 20
808894 384894 20
952682 726287 10
788685 231021 4
837664 482859 15
647999 559763 12
883561 376292 28
982116 639838 25
448672 717778 13
885950 867610 27
844653 313187 14
944049 485624 4
757390 369739 6
69799 13312 27
256238 68401 28
609641 128437 27
444687 635313 27
490476 362028 22
921474 228101 29
989389 108287 10
219973 354669 16
389600 971352 28
240162 974168 19
158450 872118 29
475182 98035 20
30
17 12 17 27 27 13 27 4 19 4 6 15 12 13 28 14 25 4 17 6 10 29 27 19 15 25 12 13 10 12

Salut,

À vue de nez et sans me prononcer sur le fait que tu ne partes dans la bonne direction ou non j'ai l'impression que la façon dont tu explores ton graphe est potentiellement très coûteuse. Je ne sait pas quelles sont tes connaissances sur la question (du point de vue algorithmique) mais sans donner trop d'indices je peut te dire que la notion dont on a besoin pour résoudre ce problème est trouvable dans les ressources linkées dans le forum 😉 (https://prologin.org/forum/entrainement-3/ressources-i-debutants-1114/ et https://prologin.org/forum/entrainement-3/ressources-ii-avancees-1115/ )

Aussi, à noter que l'environnement de test limitera l’exécution de ton programme à un seul cœur et donc que tu n'arriveras pas à gagner en performances en parallélisant ton code. En règles générales Prologin incite plus à réfléchir à une solution "adaptée" plutôt que "bien implémentée" pour reprendre tes mots.

Bon courage !

PS: prends garde à ne pas envoyer une idée trop détaillée de tes idées sur le forum, je pense que là ça va :)

J'avais déjà regardé ces ressources, et j'avais bien vu des trucs pour parcourir les graphs, mais là on a un parcours avec des étapes et du coup j'avais pas l'impressions qu'il y en ait un adapté, je vais m'y replonger.

Et puis effectivement, l'informatique c'est mon dada, l'algorithmique beaucoup moins xD

Et niveau coût, en mémoire c'est assez faible, mais c'est surtout en temps de calcul, l'exemple que j'ai donnée a mis 15 minutes sur 8 coeurs, qui sont pas des plus lents ^^ donc quelques heures chez prologin à priori :(

Et du coup merci!