π
<-
Chat plein-écran
[^]

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

Online

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: 19.9%
 
Posts: 38495
Images: 11152
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
GitHub: critor

Online

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 de spécialité NSI ( projets, tutos ...)
:favorite: NumWork, Python : démineur, snake, tétris
User avatar
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Level up: 6.4%
 
Posts: 742
Images: 61
Joined: 17 May 2012, 09:49
Location: Avignon
Gender: Male
Calculator(s):
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: 54.3%
 
Posts: 5597
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender: Male
Calculator(s):

Online

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: 19.9%
 
Posts: 38495
Images: 11152
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
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: 20.6%
 
Posts: 266
Images: 17
Joined: 30 Oct 2019, 19:17
Gender: Male
Calculator(s):
Class: plutôt, oui :)

Online

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: 19.9%
 
Posts: 38495
Images: 11152
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
GitHub: critor

Online

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: 19.9%
 
Posts: 38495
Images: 11152
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
GitHub: critor

Online

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' 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: 19.9%
 
Posts: 38495
Images: 11152
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
GitHub: critor

Online

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

Unread postby critor » 27 Sep 2021, 21:30

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

Online

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 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 67.2%
 
Posts: 78
Joined: 06 Jan 2016, 13:44
Gender: Male
Calculator(s):

PreviousNext

Return to News Divers

Who is online

Users browsing this forum: No registered users and 8 guests

-
Search
-
Social
-
Featured topics
Concours de rentrée 2021 - La Geste d'Alrys
Concours de rentrée 2021 - Synchro-donjon !
Comparaisons des meilleurs prix pour acheter sa calculatrice !
25€ remboursés par Casio sur l'achat de ta calculatrice fx-CP400 d'ici le 31 Octobre 2021
Journées APMEP 2021 à l'IUT de Bourges les 24-25 Octobre. Viens rencontrer Casio, NumWorks, TI et Vittascience.
Coque NumWorks édition limitée Octobre 2021 à gagner.
123456
-
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.
630 utilisateurs:
>604 invités
>20 membres
>6 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)