Algorithme le plus efficace pour ce problème Fermé

Question

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 ?

ensmings · Answer

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.

George369 · Answer

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 ?

Pacorabanix · Answer

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 ?

George369 · Answer

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 ^^'

Pacorabanix · Answer

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.

dr hisoka · Answer

https://forums.commentcamarche.net/forum/affich-15109719-fonctions-parametre-char

https://forums.commentcamarche.net/forum/affich-15109719-fonctions-parametre-char

Algorithme le plus efficace pour ce problème

6 réponses

Discussions similaires