Problème 4 - idée d'optimisation

Bonjour :) Je participe juste histoire d'apprendre de nouveau algo et voir quel niveau j'ai (je fais de la programmation depuis pas si longtemps) Du coup j'ai essayé de réaliser le problème 4 en essayant de plusieurs manières et j’avouerai que là je sais plus trop quel algo utiliser...

En cherchant dans : https://prologin.org/forum/entrainement-3/les-algorithmes-et-structures-de-donnees-a-connaitre-950/ Le dernier que j'ai utilisé est l'algorithme de Dijkstra avec quelques modification, mais je ne réussit pas le 5eme car je dépasse la limite des 75 secondes de pythons avec 503,9Ko de mémoire.

Actuellement je sais absolument pas quel algorithme chercher... :/ Possible de m’orienter Sinon je me contenterai d'attendre la fin des qualifications pour regarder la solutions des autres participants ^^

P.S : Sur mes tests perso, mon programme réussit en quelques secondes sur des données assez larger, quelqu'un saurait comment je pourrai trouver d'autres données que je pourrai utiliser pour faire ressortir mon problème, car ceux que je génère moi même ne semble pas créer de problèmes :/

Fais toi un programme qui génère des entrées au hasard, et met les entrées les plus larges possible. Profile ton code et cherche un endroit particulièrement mal codé. Algorithme Djikstra peut marcher pour ce problème. C'est l'implémentation qui doit être hasardeuse.

Bah le truc, c'est que j'ai essayé, j'ai généré un truc avec 1500 planètes, 500 types de planètes et une mission de 400 jours. Mon code la résolu en 3,10 seconde :/ Je comprends pas pourquoi quand je le soumet il met autant de temps

Essaie de réfléchir à quelle entrée peut être faite volontairement pour augmenter le temps de calcul, et cherches comment la combattre.

J'ai finis par jeter ma solution actuelle et en prendre une autre, Au final c'est 50 lignes de moins et 100x plus rapide :) Bref j'étais assez fière de l'ancienne mais il y avait d'autres algo plus pratique ^^

Moi je m'en suis sorti avec un Djikstra.

Une fois les qualification finis, je serais intéressé de voir ce que tu as fait ^^

Moi aussi je m'en suis sorti avec l'algorithme de Dijkstra, après c'est sûr qu'il faut savoir l'adapter au problème.

Oui j'ai évidemment essayé de l'adapter j'ai pas fait du simple copier coller xD Mon problème venait de l'optimisation de la liste que je rentrayai constamment :/

Mais bon ça m'intéresse quand même de voir ce que vous avez fait après ^^

Ok, j'imagine qu'on a le droit d'envoyer nos solutions sur le forum une fois que les qualifications sont terminées ?

Pas sur mais tu peux au moins en parler ! J'avoue que le dijkstra n'était pas passé chez moi à cause de la mémoire, j'avais un tas trop grand. mais on peut le gérer différement pour que ça passe. Après, on peut optimiser et faire sans dijkstra, c'est plus beau comme code.