High-Tech Santé Médecine Droit-Finances

Auto-Entrepreneur

Comment faire ?

Rechercher : dans
Par :

Algorithme le plus efficace pour ce problème

Dernière réponse le 9 nov 2009 à 00:24:27 George369, le 8 nov 2009 à 13:30:31 
 Signaler ce message aux modérateurs

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 ?

Configuration: Windows XP
Firefox 3.5.5

Meilleures réponses pour « Algorithme le plus efficace pour ce problème » dans :
Présentation et Configuration de l'antivirus AVG free. VoirVoici un tutoriel pour configurer l'antivirus AVG free dans le but qu'il soit le plus efficace possible, nous ferons aussi un petit commentaire pour chaque composant de l'antivirus : Pour info, l'antivirus AVG free est téléchargeable...
Axis 2 [Partie 1] Voir1.Concept 2.Fonctionnement : runtime 3.Axis2 : WSDL2Java 4.Axis2 : Databinding framework ADB 5.Distribution Axis Axis 2 1.Concept Le concept des Web Service tourne autour des trois acronymes suivants : SOAP (Simple Object Access...
Logiciels antispam gratuits Voir
Télécharger Emule Plus Voir
Télécharger Google Toolbar pour Internet Explorer VoirLa barre d'outils Google permet : d'afficher le pagerank des pages visitées d'ajouter à vos favoris les pages que vous visitez fréquemment pour y accéder directement. de rendre vos recherches plus efficaces grâce aux suggestions...
Télécharger Google Toolbar pour Firefox VoirLa barre d'outils Google permet : d'afficher le pagerank des pages visitées d'ajouter à vos favoris les pages que vous visitez fréquemment pour y accéder directement. de rendre vos recherches plus efficaces grâce aux suggestions...
Posez votre question Répondre

1

ensmings, le 8 nov 2009 à 13:59:50
  • +1

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:
http://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.

   
Répondre à ensmings

2

George369, le 8 nov 2009 à 21:02:04

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 ?

   
Répondre à George369

3

Pacorabanix, le 8 nov 2009 à 21:34:20

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 ?

   
Répondre à Pacorabanix

4

George369, le 8 nov 2009 à 22:19:24

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

   
Répondre à George369

5

Pacorabanix, le 8 nov 2009 à 22:34:08

Je ne sais pas... va faire un tour sur http://www.developpez.net/forums/f520/autres-langages/algori­thmes/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.

   
Répondre à Pacorabanix

6

 dr hisoka, le 9 nov 2009 à 00:24:27
   
Répondre à dr hisoka
Posez votre question Répondre
Ils ont besoin de votre aide