Algorithme le plus efficace pour ce problème
George369
Messages postés
10
Date d'inscription
Statut
Membre
Dernière intervention
-
dr hisoka Messages postés 71 Date d'inscription Statut Membre Dernière intervention -
dr hisoka Messages postés 71 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
voici le problème à résoudre au moyen d'un programme.
On a un carré de côté 10, et dans le coin supérieur gauche on place le nombre 1.
Ensuite on a le droit de se déplacer à partir de cette case au moyen des déplacements suivants :
-> 3 cases en horizontal ou vertical
OU
-> 2 cases en diagonale.
Ainsi, à partir du 1 je peux aller 3 cases vers la droite, 3 cases vers le bas ou alors 2 cases vers le coin inférieur droit. On place alors le 2, et ainsi de suite...
Le but est de trouver une solution pour cette énigme au moyen d'un ordinateur (elle existe, il y en a au moins 2).
J'ai essayé un algorithme de force brute. Cependant selon mes estimations, celui-ci mettrait plus d'un siècle à s'exécuter.
Auriez-vous une idée, ou auriez-vous déjà entendu parler de ce genre de problème ?
voici le problème à résoudre au moyen d'un programme.
On a un carré de côté 10, et dans le coin supérieur gauche on place le nombre 1.
Ensuite on a le droit de se déplacer à partir de cette case au moyen des déplacements suivants :
-> 3 cases en horizontal ou vertical
OU
-> 2 cases en diagonale.
Ainsi, à partir du 1 je peux aller 3 cases vers la droite, 3 cases vers le bas ou alors 2 cases vers le coin inférieur droit. On place alors le 2, et ainsi de suite...
Le but est de trouver une solution pour cette énigme au moyen d'un ordinateur (elle existe, il y en a au moins 2).
J'ai essayé un algorithme de force brute. Cependant selon mes estimations, celui-ci mettrait plus d'un siècle à s'exécuter.
Auriez-vous une idée, ou auriez-vous déjà entendu parler de ce genre de problème ?
A voir également:
- Algorithme le plus efficace pour ce problème
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Annuaire inversé efficace - Guide
- Algorithme ajout rapide snapchat - Forum Snapchat
6 réponses
Si tu trouves la réponse à ta question, tu résous le problème P=NP, qui est un des 7 problèmes du millénaires et tu gagnes 1 million de dollars !
Voir page wikipédia:
https://fr.wikipedia.org/wiki/Probl%C3%A8mes_du_prix_du_mill%C3%A9naire
Il existe toute une famille de problèmes comme le tien dont le temps de calcul explose avec la complexité. Actuellement on les résous en faisant des hypothèses simplificatrices comme ne pas étudier toutes les solutions pour arriver plus vite au résultat sans être sur toutefois d'avoir le meilleur résultat.
Voir page wikipédia:
https://fr.wikipedia.org/wiki/Probl%C3%A8mes_du_prix_du_mill%C3%A9naire
Il existe toute une famille de problèmes comme le tien dont le temps de calcul explose avec la complexité. Actuellement on les résous en faisant des hypothèses simplificatrices comme ne pas étudier toutes les solutions pour arriver plus vite au résultat sans être sur toutefois d'avoir le meilleur résultat.
Ok je vois ^^"
Merci pour ta réponse.
Tu n'aurais pas idée du nom de mon problème ?
Ou alors de la façon de trouver au moins une solution rapidement ?
Merci pour ta réponse.
Tu n'aurais pas idée du nom de mon problème ?
Ou alors de la façon de trouver au moins une solution rapidement ?
personnellement, j'ai bien compris ce que tu expliques, mais je ne vois pas où est la question, tu pourrais préciser quel est le but ?
Le but est d'arriver au nombre 100 en se déplaçant à chaque tour, avec des déplacements bien précis.
Cependant, on ne peut remplacer en nombre par un autre.
Exemple :
j'ai un nombre (e.g. 56) avec de certaines coordonnées (x = 1, y=2) dans la grille.
Avec les déplacements autorisés (horizontal, vertical = +- 3 cases, diagonale = +- 2 cases) il m'est possible d'identifier les cases potentielles pour le nombre suivant (ici 57).
Par exemple, si je veux me déplacer de 3 cases vers la droite, si la case en question est vide, je peux placer le 57. Si elle est remplie c'est impossible. De même me déplacer vers la gauche est impossible, puisque je sortirais du tableau dans cet exemple.
Il est donc possible d'être bloqué à un certain moment : lorsque on arrive sur un nombre qui n'a plus de cases potentielles, c'est fini.
Je connais 2 solutions de ce tableau. Cependant je croyais qu'il serait aisé de les trouver toutes ^^'
Cependant, on ne peut remplacer en nombre par un autre.
Exemple :
j'ai un nombre (e.g. 56) avec de certaines coordonnées (x = 1, y=2) dans la grille.
Avec les déplacements autorisés (horizontal, vertical = +- 3 cases, diagonale = +- 2 cases) il m'est possible d'identifier les cases potentielles pour le nombre suivant (ici 57).
Par exemple, si je veux me déplacer de 3 cases vers la droite, si la case en question est vide, je peux placer le 57. Si elle est remplie c'est impossible. De même me déplacer vers la gauche est impossible, puisque je sortirais du tableau dans cet exemple.
Il est donc possible d'être bloqué à un certain moment : lorsque on arrive sur un nombre qui n'a plus de cases potentielles, c'est fini.
Je connais 2 solutions de ce tableau. Cependant je croyais qu'il serait aisé de les trouver toutes ^^'
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
je ne sais pas... va faire un tour sur https://www.developpez.net/forums/f520/general-developpement/algorithme-mathematiques/mathematiques/ au cas où.
Le problème général est comme l'a dit le précédent posteur NP-Complet (c-à-d TRES difficile, on ne sais même pas s'il est possible)
Sinon, selon ton niveau en maths, et comme ton problème à toi est très précis (carré de 100 cases...), tu peux essayer qqchose comme ceci :
tes cases tu les numérotes de 0 à 99 (tu évolues dans les nombres modulo 100). aller 3 cases à droite = faire + 3, aller 3 cases vers le bas = faire +30, 2 cases en diag en bas à droite = faire +22.
Ensuite, je-ne-sais comment tu traduis ça en système linéaire et tu résous le système. Mais je ne sais pas être plus précis.
Le problème général est comme l'a dit le précédent posteur NP-Complet (c-à-d TRES difficile, on ne sais même pas s'il est possible)
Sinon, selon ton niveau en maths, et comme ton problème à toi est très précis (carré de 100 cases...), tu peux essayer qqchose comme ceci :
tes cases tu les numérotes de 0 à 99 (tu évolues dans les nombres modulo 100). aller 3 cases à droite = faire + 3, aller 3 cases vers le bas = faire +30, 2 cases en diag en bas à droite = faire +22.
Ensuite, je-ne-sais comment tu traduis ça en système linéaire et tu résous le système. Mais je ne sais pas être plus précis.
