π
<-
Chat plein-écran
[^]

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

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

Unread postby 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
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 41.8%
 
Posts: 41470
Images: 14480
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
MyCalcs profile
YouTube: critor3000
Twitter: critor2000
GitHub: critor

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

Unread postby 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 ...
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
User avatar
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Level up: 45.9%
 
Posts: 1009
Images: 64
Joined: 17 May 2012, 09:49
Location: Avignon
Gender: Male
Calculator(s):
MyCalcs profile
Twitter: nsi_xyz

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

Unread postby 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 !
User avatar
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 69.5%
 
Posts: 5665
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender: Male
Calculator(s):
MyCalcs profile

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

Unread postby 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
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 41.8%
 
Posts: 41470
Images: 14480
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
MyCalcs profile
YouTube: critor3000
Twitter: critor2000
GitHub: critor

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

Unread postby 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 ! :bj:


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

Je suis bien d'accord ! :D
User avatar
AfyuVIP++
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 90.1%
 
Posts: 339
Images: 18
Joined: 30 Oct 2019, 19:17
Gender: Male
Calculator(s):
MyCalcs profile
Class: plutôt, oui :)

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

Unread postby 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
Image
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 41.8%
 
Posts: 41470
Images: 14480
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
MyCalcs profile
YouTube: critor3000
Twitter: critor2000
GitHub: critor

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

Unread postby 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
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 41.8%
 
Posts: 41470
Images: 14480
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
MyCalcs profile
YouTube: critor3000
Twitter: critor2000
GitHub: critor

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

Unread postby 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
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 41.8%
 
Posts: 41470
Images: 14480
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
MyCalcs profile
YouTube: critor3000
Twitter: critor2000
GitHub: critor

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

Unread postby critor » 27 Sep 2021, 21:30

Anonymat levé également à la demande de ptitjoz :
https://tiplanet.org/concours_alrys2021.php
Image
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 41.8%
 
Posts: 41470
Images: 14480
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
MyCalcs profile
YouTube: critor3000
Twitter: critor2000
GitHub: critor

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

Unread postby 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
User avatar
DubsVIP++
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Level up: 37.9%
 
Posts: 125
Joined: 06 Jan 2016, 13:44
Gender: Male
Calculator(s):
MyCalcs profile

PreviousNext

Return to News Divers

Who is online

Users browsing this forum: No registered users and 49 guests

-
Search
-
Social TI-Planet
-
Featured topics
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
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
2563 utilisateurs:
>2551 invités
>7 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)