Inscription / Connexion Nouveau Sujet
Algorithme de déplacement
Bonjour
je vous propose l'exercice suivant ; (ressemble à ce que j'ai deja posé mais avec une variante )
On se donne une grille de format 10 x 10 , chaque case de cette grille est reperée par ses coordonnées de type (i,j) i pour les lignes et j pour les colonnes , on noircit ensuites les cases dont les coordonnées sont les suivantes (8,2) (2,3) (5,3) (10,4) (3,6) (7,6) (10,6) (2,9) (4,10) (6,9) et (10,9) .
"un robot" se trouve sur la case de depart de coordonées (10,1) , le but du jeu et de rejoindre la case (1,10) par des deplacements aleatoires vers le bas, vers le haut , vers la gauche ou à droite d'une case à chaque fois et de facon équiprobable (1/4 de chance d'aller dans l'une des 4 directions ) , tout en restant dans les limites de la grille , si le deplacement dans la direction souhaitée le fait tomber sur une case noire alors le robot doit renoncer et choisir une autre direction , lorsque le robot atteint la case (1,10) le jeu s'arrete.
A combien estimez vous en moyenne le nombre de déplacements que celui ci devra effectuer pour arriver à son but ?
vous avez le choix du langage de programmation
Comme calculé de deux façons par ce programme: 
, le nombre de déplacement moyen est d'environ 607.147.
Notez que le nombre de déplacements doit être pair.
Distribution du nombre de déplacements entre le départ et l'arrivée:
Espérance du nombre de déplacements en fonction de la case de départ (les coordonnées sont décalées de 1 pour commencer à (0;0)):
Salut Littlefox , j'ai ecris un bout de code en vba
que voici
Sub avance_vers_cible()
Dim d, e, choix As Long
Dim blocage As Integer
Dim arret As Boolean
Randomize
e = 0
Do
e = e + 1
Cells(10, 1).Select
d = 0
blocage = 0
Do
recom:
blocage = blocage + 1
If blocage = 4 Then
arret = True
End If
choix = Int(Rnd * 4)
Select Case choix
Case Is = 0 'haut
'verifier si le deplacement vers le haut est possible
If ActiveCell.Row > 1 Then
If ActiveCell.Offset(-1, 0).Interior.ColorIndex <> 1 Then
ActiveCell.Offset(-1, 0).Select
blocage = 0
d = d + 1
Else
GoTo recom
End If
End If
Case Is = 1 'bas
'verifier si le deplacement vers le bas est possible
If ActiveCell.Row < 10 Then
If ActiveCell.Offset(1, 0).Interior.ColorIndex <> 1 Then
ActiveCell.Offset(1, 0).Select
blocage = 0
d = d + 1
Else
GoTo recom
End If
End If
Case Is = 2 'gauche
'verifier si le deplacement vers le haut est possible
If ActiveCell.Column > 1 Then
If ActiveCell.Offset(, -1).Interior.ColorIndex <> 1 Then
ActiveCell.Offset(, -1).Select
blocage = 0
d = d + 1
Else
GoTo recom
End If
End If
Case Is = 3 'droite
'verifier si le deplacement vers le haut est possible
If ActiveCell.Column < 10 Then
If ActiveCell.Offset(, 1).Interior.ColorIndex <> 1 Then
ActiveCell.Offset(, 1).Select
blocage = 0
d = d + 1
Else
GoTo recom
End If
End If
End Select
Loop Until ActiveCell.Row = 1 And ActiveCell.Column = 10 Or (arret = True)
q = q + d
Loop Until e = 10000
MsgBox q / e
End Sub
j'ai corrigé le code en prenant en compte le fait que le robot se trouve devant un mur de cellules noires , horizontale , verticale ou oblique et donc avec l'impssibilité d'atteindre la cellule cible avec message de sortie si c'est le cas .
ce qui donne :
Sub avance_vers_cible()
Dim d, e, choix As Long
Dim blocage As Integer
Dim arret As Boolean
Randomize
e = 0
Do
e = e + 1
Cells(10, 1).Select
d = 0
blocage = 0
Do
recom:
blocage = blocage + 1
If blocage = 4 Then
arret = True
End If
choix = Int(Rnd * 4)
Select Case choix
Case Is = 0 'haut
'verifier si le deplacement vers le haut est possible
If ActiveCell.Row > 1 Then
If ActiveCell.Offset(-1, 0).Interior.ColorIndex <> 1 Then
ActiveCell.Offset(-1, 0).Select
blocage = 0
d = d + 1
Else
GoTo recom
End If
End If
Case Is = 1 'bas
'verifier si le deplacement vers le bas est possible
If ActiveCell.Row < 10 Then
If ActiveCell.Offset(1, 0).Interior.ColorIndex <> 1 Then
ActiveCell.Offset(1, 0).Select
blocage = 0
d = d + 1
Else
GoTo recom
End If
End If
Case Is = 2 'gauche
'verifier si le deplacement vers le haut est possible
If ActiveCell.Column > 1 Then
If ActiveCell.Offset(, -1).Interior.ColorIndex <> 1 Then
ActiveCell.Offset(, -1).Select
blocage = 0
d = d + 1
Else
GoTo recom
End If
End If
Case Is = 3 'droite
'verifier si le deplacement vers le haut est possible
If ActiveCell.Column < 10 Then
If ActiveCell.Offset(, 1).Interior.ColorIndex <> 1 Then
ActiveCell.Offset(, 1).Select
blocage = 0
d = d + 1
Else
GoTo recom
End If
End If
End Select
Loop Until ActiveCell.Row = 1 And ActiveCell.Column = 10 Or (arret = True)
If arret = True Then
MsgBox "impossible de se rendre vers la cellule cible "
GoTo fin
End If
q = q + d
Loop Until e = 10000
MsgBox q / e
fin:
End Sub
Tu peux mettre ton code dans un bloc [code][/code], ce sera plus lisible.
Si je comprends bien, ton code est une simulation de 10000 tentatives. Ok mais ça doit être long et pas très précis 
Pour le cas où le robot est incapable d'atteindre la cible, tu testes juste que le robot s'est cogné quatre fois d'affilée contre un obstacle.
Si le robot est contre un obstacle, il y a une change sur 256 que ça arrive. C'est peu probable mais sur 10000 essais, ça doit arriver. Non?
Aussi, le robot ne peut pas se retrouver entouré d'obstacles. S'il était entouré alors il n'aurait pas pu arriver à cette position.
Tester s'il existe un chemin entre le départ et l'arrivée est un tout autre problème. Et n'est pas vraiment nécessaire puisqu'on peut le vérifier facilement à la main.
Ma première version est un robot "quantique": Le robot prend tous les chemins possibles à chaque mouvement et je calcule pour chaque cellule la probabilité qu'il se trouve là après ce mouvement.
En connaissant la probabilité d'être sur la case d'arrivée après chaque mouvement, je peux calculer la moyenne.
Ma seconde version calcule directement pour chaque cellule le nombre de mouvements moyen pour aller à l'arrivée.
J'ai utilisé une inversion de matrice mais ça peut très bien se faire par itération, le résultat étant stable.
:DBonjour,
Je m'en tiens à cette dernière réflexion ....notre robot doté de l'IA
mettra 18 déplacements 
Ou juste d'un développeur compétent
C'est quoi l'IA? Un grand mot qui recouvre bien des domaines.
Ici on a une IA de type essai-erreur sans mémoire. Un intelligence artificielle vraiment peu intelligente.
Annuler
connectez vous