Concours de rentrée 2021 - La Geste d'Alrys

→ **MyCalcs** profile · by **critor** » 25 Sep 2021, 17:51

Nouveau participant n°11 qui s'insère directement à la 7ème place :

https://tiplanet.org/concours_alrys2021.php

→ **MyCalcs** profile · by **cent20** » 25 Sep 2021, 18:02

Bisam wrote:
critor wrote:Pour l'instant le sujet vous résiste bien cette année.

J'espère bien !! Si n'importe qui réussissait à résoudre une instance du problème du voyageur de commerce (à peu de choses près) à 21 points de passage, ça se saurait.
La meilleure implémentation connue de la recherche de la solution optimale (par l'algorithme de Held et Karp) demande au moins 1 milliard de calculs.
Bref, il y a très peu de chances que l'on te fournisse la solution optimale.

Il y a en effet 21 points de passage mais tous ne sont pas obligatoires, et l'ordre est un "peu contraint" par la carte assez particulière. Le problème ce n'est pas les 21 points, c'est qu'entre chaque point il existe un nombre presque illimité de chemins dont le coût n'est pas constant ...

→ **MyCalcs** profile · by **Bisam** » 26 Sep 2021, 11:02

Il suffit d'appliquer l'algorithme de Dijkstra (qui est quasi-linéaire en le nombre de sommets) entre chaque couple de points de passage, en prenant comme points intermédiaires tous les points de la carte.
C'est long, mais il suffit de le faire une seule fois !

→ **MyCalcs** profile · by **critor** » 26 Sep 2021, 17:14

Si ça peut vous aider, animation de ce que donne une implémentation de l'algorithme de recherche de chemin A* sur Alrys.
Ici, à partir de la position de départ, la cible est le donjon en bas à gauche.

Par @bebertii / Marcellus Wallace.

Source : https://twitter.com/bebertii/status/1442152467765006342

→ **MyCalcs** profile · by **Afyu** » 26 Sep 2021, 17:43

SlyVTT wrote:
critor wrote:C'est super sympa de ta part @Dubs d'aider ainsi tout-le-monde, bravo !

C'est clair, il faudrait décerner le prix spécial du Fair Play pour Dubs !!

Je suis bien d'accord !

→ **MyCalcs** profile · by **critor** » 27 Sep 2021, 11:21

critor wrote:Si ça peut vous aider, animation de ce que donne une implémentation de l'algorithme de recherche de chemin A* sur Alrys.
Ici, à partir de la position de départ, la cible est le donjon en bas à gauche.

Par @bebertii / Marcellus Wallace.

Source : https://twitter.com/bebertii/status/1442152467765006342

Et une fois que la destination a été atteinte par l'algorithme, génération du chemin optimal. Attention à coefficienter correctement les cases, ça peut tout changer :

Source : https://twitter.com/bebertii/status/1442420508943867905

→ **MyCalcs** profile · by **critor** » 27 Sep 2021, 20:37

Plusieurs participants me disent que c'est dommage que les participations soient anonymes :
https://tiplanet.org/concours_alrys2021.php

On vous écoute, on tient compte des retours.

Donc si certains participants ne souhaitent pas rester anonymes jusqu'à la fin du concours, il leur suffira de nous le préciser, soit ici, soit avec leur prochaine participation.

→ **MyCalcs** profile · by **critor** » 27 Sep 2021, 21:13

Suite à sa demande sur le chat, l'anonymat d'_Orlando_ est dès maintenant levé :
https://tiplanet.org/concours_alrys2021.php

Félicitations donc en passant !

→ **MyCalcs** profile · by **critor** » 27 Sep 2021, 21:30

Anonymat levé également à la demande de ptitjoz :
https://tiplanet.org/concours_alrys2021.php

→ **MyCalcs** profile · by **Dubs** » 28 Sep 2021, 07:48

J'ai mis à jour mon petit soft pour dessiner le trajet avec quelques améliorations (notamment un mode Zoom pour affiner les trajets. J'ai mis aussi une possibilité de choisir son point de départ et le prochain point de passage, par exemple pour calculer visuellement la distance entre un donjon et une ville)

ptitjoz wrote:
Dubs wrote:J'ai programmé une appli pour calculer le chemin optimal en "brute force", un poil optimisée.
j'espère qu'elle me trouvera une réponse avant la fin du concours.

trop fort pour moi.. je ne saurais même pas où commencer..

sinon pour ton outil https://tiplanet.org/forum/archives_voir.php?id=2793208 tout fonctionne à merveille ( sauf je n'arrive pas à loader un programme via wine sous Linux) j'ai ce message
0009:err:ole:CoCreateInstanceEx apartment not initialised

je crois que tu l'a fais avec Delphi. Est-ce que tes sources sont compatibles avec Lazarus à tout hasard ?

est-ce que ce serait possible de revenir sur des segments du parcours plutôt que de tout effacer et de recommencer ?

J'ai mis les sources dans l'archive, comme je ne connais pas Lazarus je te laisse voir si tu peux le convertir facilement. Je n'utilise que des composants natifs.
J'ai essayé d'implémenter "revenir sur des segments du parcours", mais je n'ai pas trouvé de solution propre. Comme les angles et les distances n'ont pas de décimales, le chemin se dégrade rapidement (ex : A->B->C, si je modifie le point B, le point C ne sera pas exactement le même à cause des arrondis)

Et merci à vous pour vos remerciements, ça fait plaisir !

et pour Critor : j'accepte de lever l'anonymat pour mon n°5