π
<-
Chat plein-écran
[^]

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

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

Message non lude critor » 25 Sep 2021, 17:51

Nouveau participant n°11 qui s'insère directement à la 7ème place : :bj:
https://tiplanet.org/concours_alrys2021.php
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

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

Message non lude cent20 » 25 Sep 2021, 18:02

Bisam a écrit:
critor a écrit: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 ...
Image
Enseignant de mathématiques et d'informatique. Spécialité NSI : Des projets, des tutos, mais aussi de l'art
Calculatrice NumWorks : Des applications et des jeux, scripts, 📙 Découvrir la NumWorks
Avatar de l’utilisateur
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 45.9%
 
Messages: 1007
Images: 64
Inscription: 17 Mai 2012, 09:49
Localisation: Avignon
Genre: Homme
Calculatrice(s):
MyCalcs profile
Twitter/X: nsi_xyz

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

Message non lude 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 !
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile

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

Message non lude 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
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

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

Message non lude Afyu » 26 Sep 2021, 17:43

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


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

Je suis bien d'accord ! :D
Avatar de l’utilisateur
AfyuVIP++
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 89.2%
 
Messages: 339
Images: 18
Inscription: 30 Oct 2019, 19:17
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: plutôt, oui :)

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

Message non lude critor » 27 Sep 2021, 11:21

critor a écrit: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
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

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

Message non lude 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. :)
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

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

Message non lude 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 ! :bj:
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

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

Message non lude critor » 27 Sep 2021, 21:30

Anonymat levé également à la demande de ptitjoz :
https://tiplanet.org/concours_alrys2021.php
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

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

Message non lude 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 a écrit:
Dubs a écrit: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
Avatar de l’utilisateur
DubsVIP++
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 37.9%
 
Messages: 125
Inscription: 06 Jan 2016, 13:44
Genre: Homme
Calculatrice(s):
MyCalcs profile

PrécédenteSuivante

Retourner vers News Divers

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 26 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
798 utilisateurs:
>773 invités
>20 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)