Probabilités à l'intérieur d'un cube

Réponses à toutes vos questions de la 2nde à la Terminale toutes séries
Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Probabilités à l'intérieur d'un cube

par Steph3112 » 22 Jan 2021, 13:51

Bonjour à toutes et tous,

Voici les ingrédients :
J'ai un GROS cube (admettons 1m3) constitué de PETITs cubes (admettons 1cm3)
Chacun des petits cubes comporte une valeur de résistance propre comprise entre 0.000 et 1.000
Ces résistances sont calculées de façon aléatoire et distribuées de façon homogène à l'échelle du gros cube.
Je définis aléatoirement un petit cube comme étant un cube de départ et un autre petit cube comme cube d'arrivée.
Maintenant j'ai un algorithme de recherche du plus court-chemin qui cherchera par quels petits cubes passer pour rallier le point de départ à celui d'arrivée en rencontrant une résistance minimale.

Voici mon problème :
Calculer la probabilité de chacun des petits cubes de mon gros cube de se trouver dans le chemin en fonction de la position des points de départ et d'arrivée.

Les différentes nuances de probabilité devraient dessiner des sortes de ballons de Rugby entre le point de départ et le point d'arrivée je pense.

Note: les algorithmes de recherche du plus court-chemin sont des algorithmes gloutons d'où la grande importance de limiter le nombre de cellules à calculer.
Avis aux amateurs ! Merci beaucoup



Rhaegar
Membre Naturel
Messages: 91
Enregistré le: 25 Mar 2017, 23:27

Re: Probabilités à l'intérieur d'un cube

par Rhaegar » 22 Jan 2021, 18:29

Bonjour,

J'imagine que plus la résistance d'un cube est élevée, plus la probabilité d'être dans le bon chemin est faible. De la même façon, plus le petit cube est loin du segment reliant cube de départ et d'arrivée, plus la probabilité est faible.
Je ne suis pas sûr d'avoir saisi tous les détails du problème mais de ce que j'ai compris, je pense que c'est un problème assez compliqué à résoudre.

Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Re: Probabilités à l'intérieur d'un cube

par Steph3112 » 22 Jan 2021, 19:55

Merci une nouvelle fois Rhaegar,
Effectivement si la résistance d'un cube est élevée il y'a peu de chance que le chemin le rencontre mais cela n'empêche pas qu'il puisse se situer dans une ZONE où la probabilité est importante.
En fait je dispose d'un algo qui trouve le chemin entre 2 cubes diagonalement opposés mais qui prends le temps de calculer tous les cubes alors qu'il est à coup sûr inutile d'aller jusqu'à explorer les autres coins du cube et cela coûte très cher en temps d'accumuler des cubes probablement inutiles dans la partie gloutonne de mon algorithme. Ta réponse au sujet du point hors ou dans un cylindre était parfaite mais mon approche du problème non. Le but de ma question ici est de limiter encore un peu plus le nombre de cellules que celles en intersection du cylindre et du cube.
Et comme je veux bien te croire que ça soit pas forcément facile à calculer !
Pourvu au moins que ce soit marrant sinon je ne risque pas de trouver d'amateur !

Rhaegar
Membre Naturel
Messages: 91
Enregistré le: 25 Mar 2017, 23:27

Re: Probabilités à l'intérieur d'un cube

par Rhaegar » 22 Jan 2021, 20:24

Je reformule mon problème, dite moi si je me trompe. Vous avez un domaine cubique que vous partitionnez en plein de petits cubes. Vous associez à chaque cube un nombre aléatoire tiré uniformément entre 0 et 1. Vous avez un cube de départ et d'arrivé. Vous cherchez un chemin de cubes reliant le cube de départ au cube d'arrivé telle que la somme des nombres de chaque cube par lesquels votre chemin est passé soit la plus petite possible. Vous avez un algorithme pour faire ça et vous cherchez à l'optimiser en éliminant les cubes ayant peu de chance de se trouver sur le chemin optimal.

Pouvez-vous détailler le fonctionnement de votre algorithme s'il vous plaît ?

Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Re: Probabilités à l'intérieur d'un cube

par Steph3112 » 22 Jan 2021, 21:39

Merci Rhaegar,
J'ai mis en ligne récemment un PDF montrant de façon très simplifiée la résolution d'un petit problème 2D (une matrice 5x5 en mode périphérique). En suivant le lien de ce Post https://forum.excel-pratique.com/astuces/le-pathfinding-ou-la-recherche-de-chemin-par-vba-95554#p937054tu pourras arriver jusqu'à la dernière version béta de mon application et un document rentrant plus dans le détail de la programmation: Le Propagation Book.
Voilà toute la littérature disponible sur cet algorithme actuellement.

Slts
Stéphane

Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Re: Probabilités à l'intérieur d'un cube

par Steph3112 » 22 Jan 2021, 21:55

Et je te confirme que tu as parfaitement compris mon problème

Rhaegar
Membre Naturel
Messages: 91
Enregistré le: 25 Mar 2017, 23:27

Re: Probabilités à l'intérieur d'un cube

par Rhaegar » 22 Jan 2021, 23:53

Je suis curieux de savoir ce que vous voulez faire avec votre algorithme.

J'ai encore du mal à comprendre votre problème. Si les résistances sont déjà assignées, et si le cube de départ et d'arrivée sont déjà déterminés, un petit cube est, ou n'est pas sur le bon chemin. La probabilité est 1 ou 0.

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Probabilités à l'intérieur d'un cube

par lyceen95 » 23 Jan 2021, 00:33

La question n'est effectivement pas réellement une question de probabilité, mais une question de recherche de plus court chemin.
Les algorithmes connus pour ce tye de problème, c'est A* et Dijkstra.

La solution que j'aime bien, si je dois le programmer moi-même et que je ne peux pas utiliser une librairie toute faite, c'est de chercher des chemins qui partent de A, et qui nous rapprochent un peu de B. Idem, chercher des chemins qui partent de B pour se rapprocher des extrémités des arbres qu'on vient de préparer ... et continuer, jusqu'à ce que les 2 moitiés d'arbre se rejoignent.

Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Re: Probabilités à l'intérieur d'un cube

par Steph3112 » 23 Jan 2021, 02:05

Bonsoir,
A Rhaegar
"Je suis curieux de savoir ce que vous voulez faire avec votre algorithme."
Initialement j'ai voulu reproduire par jeu l'IA d'un jeu vidéo et codé un premier algorithme 2D à l'intention d'un éventuel développeur de jeux. Je me suis rendu compte qu'il était facile d'étendre l'algorithme à la 3D. Est-ce que ça peut avoir une utilité en 3D je ne sais pas ? Et en plus je ne sais gérer en 3 dimensions dans un délai raisonnable que de toutes petites matrices (une 30^3 en adjacent, mode le plus rapide réclame 38 secondes, la 90^3 3 heures et 6 minutes !). Je me suis rendu compte que sur une matrice randomisée de façon homogène (ce qui ne restera qu'un cas particulier de mon app) le chemin serpente toujours plus ou moins près du segment qui relie le départ à l'arrivée et qu'il devenait inutile de calculer les cubes s'en éloignant trop. C'est juste un jeu et un défi que je me lance: calculer la plus grosse matrice possible avec mon vieux Dell ! En hésitant pas à tenter d'user de compétences externes quand cela est nécessaire comme je le fais avec ce sujet.

A Lycéen95
Je n'ai qu'une vague connaissance des algorithmes A* et de Dijkstra je bute vite sur… les mathématiques !
J'ai suivi le raisonnement des graphes de la Wikipédia sur Dijkstra et compris que l'algorithme A* était plus rapide par l'utilisation de probabilités. Alors j'ai lancé ce sujet pour faire pareil: tenter de gagner du temps en introduisant des probabilités.
"... et continuer, jusqu'à ce que les 2 moitiés d'arbre se rejoignent."
C'est une solution que tu as imaginé ou éprouvé ? J'avais commencé en cherchant une solution de ce type et n'étais arrivé à rien. As-tu téléchargé le ZIP qui contient un PDF expliquant le fonctionnement de l'algo (lien que j'ai Posté plus haut) ? Si tu as un système autre je serais très intéressé que tu me l'explique dans le détail.

Merci à vous deux

Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Re: Probabilités à l'intérieur d'un cube

par Steph3112 » 23 Jan 2021, 03:30

Je reviens à toi Rhaegar, je pensais après avoir lu ton Post de 20H24 que tu avais entièrement compris mon problème et ce n'est peut-être pas tout-à-fait le cas.
Pour mieux le visualiser voici une explication qui sera peut-être plus parlante :
Je randomise et calcule un très grand nombre de fois des matrices (des gros cubes) de même dimensions avec pour seules constantes la position des points de départ et d'arrivée. On s'apercevra que certains petits cubes seront rentrés dans le chemin plus de fois que d'autres et qu'une grande partie d'entre eux (les plus éloignés du segment liant le départ à l'arrivée) ne sera jamais calculée.
Admettons qu'après chaque random et calcul les petits cubes rencontrés par le chemin soient marqués de façon indélébile, il se dessinera rapidement une forme (ballon de rugby ?)
Donc si j'arrive à déterminer dès le départ qu'il est très improbable qu'un certain petit cube à tel endroit soit une étape d'un chemin possible je peux le raturer d'office de mes calculs (rapide à faire) et ne calculer et incorporer dans ma boucle gloutonne que les cubes à l'intérieur du ballon de rugby.
En espérant que cela puisse aider.
Cordialement

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Probabilités à l'intérieur d'un cube

par GaBuZoMeu » 23 Jan 2021, 11:26

Bonjour,

Première remarque : je me demande ce que fait ce fil dans la rubrique "Lycée".

Deuxième remarque : simplifions la question à l'extrême en supposant que tous les pas sur la grille ont le même coût. Si on va de (0,0,0) à (a,b,c) (avec a,b,c tous positifs ou nuls), les chemins les plus courts sont tous de longueur a+b+c et chaque pas consiste à augmenter de 1 une des coordonnées.
Le nombre total de ces chemins est le coefficient multinomial . Le nombre de chemins passant par le noeud (i,j,k) (avec , , ) est .

Si on admet que tous les chemins sont équiprobables, la probabilité de passer par (i,j,k) est donc .

Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Re: Probabilités à l'intérieur d'un cube

par Steph3112 » 23 Jan 2021, 14:25

Bonjour GaBuZoMeu,
Grand merci pour ta réponse, à l'instant t je ne suis pas encore capable de traduire tes équations en VBA mais si d'autres questions me viennent je pourrai les affiner (par exemple je ne comprends pas la signification des C majuscules de ta dernière équation - calcul intégral ?). Mais ça va dans le bon sens indéniablement !
Au sujet de ta première remarque je ne connais pas encore bien maths-forum et ai du mal à situer le niveau de difficulté de mon problème. J'ai été impressionné par tout ce que savait déjà en maths mon neveu qui n'est qu'en première (il est bien plus balèze que moi) du coup j'ai choisi la rubrique : "Lycée". Où l'aurais tu placé toi ?
Stéphane

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Probabilités à l'intérieur d'un cube

par GaBuZoMeu » 23 Jan 2021, 18:54

Les C sont les nombres de combinaisons (ou coefficients binomiaux).
À mon avis, le fil irait mieux dans "Salon mathématique".

Un petit dessin pour illustrer la probabilité de passage par un noeud de la grille 30x20 quand on va du coin en bas à gauche au coin en haut à droite.

Image

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Probabilités à l'intérieur d'un cube

par lyceen95 » 24 Jan 2021, 00:25

GBZM,
le problème n'est pas celui-ci.

Le problème auquel GBZM répond est celui-ci :
- En dimension 2, pour aller d'un point A à un point B, avec uniquement des pas vers la droite ou des pas vers le haut, on a plein de possibilités ( 30 pas vers la droite, puis 30 vers le haut, ou 17 vers la droite , 30 vers le haut puis 13 vers la droite ) etc etc
On peut donc calculer pour chaque sommet, la probabilité de passer par ce sommet. Par exemple, si on veut aller du point A(0,0) au point B(30,30), la moitié des chemins passent par (0,1) , et l'autre moitié par (1,0)

Et la taille des ronds rouges représentent ces pourcentages.

Le problème de Steph3112 est différent.
1. on est en dimension 3 et pas en dimension 2. Mais ça, disons que c'est un détail.
2. Chaque sommet rencontré a un 'coût' ; tous les sommets n'ont pas le même coût. Pour un chemin donné, le coût est la somme des coûts de tous les sommets utilisés. Il y a donc un chemin, et un seul qui a un coût minimum. L'objectif est de trouver ce chemin.
3. Imaginons qu'on est dans un cube 30x30x30, et que le point de départ soit le point A(2,2,2) et le point d'arrivée soit B(28,2_,28).
Et, pas de chance, les 3 points A1(3,2,2), A2(2,3,2) et A3(2,2,3) ont tous les 3 des coûts très élevés. Dans ce cas, le chemin avec le coût le moins élevé passera peut-être par le point (2,2,1) ; c'est à dire que le chemin va avoir plus de pas que le minimum basique.
On cherche le chemin qui a le coût minimum, quitte à ce que le nombre de pas soit supérieur au minimum 'normal'.
Ce n'est pas une question de maths, mais une question d'algorithme.
On peut recenser tous les chemins possibles, et garder le chemin qui a le coût le plus faible.
Mais, problème, recenser tous les chemins, c'est long en temps de calcul.
La question est donc de trouver le chemin le moins coûteux, en éliminant astucieusement les chemins qui vont forcément coûter trop cher.
Et la petite cerise sur le gateau, c'est qu'apparemment, Chris veut implémenter ça en VBA.
C'est vraiment un exe

Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Re: Probabilités à l'intérieur d'un cube

par Steph3112 » 24 Jan 2021, 02:24

Rebonjour Lycéen95,
Merci beaucoup ces réflexions que j'arrive à comprendre alors que si tu les avais posées sous forme d'équations j'aurai eu plus de difficultés. Ton raisonnement est tout à fait juste, je ne comprends cependant pas quand il devient utile de "recenser" tous les chemins ? Qui est ce Chris ? Son travail pourrait m'intéresser ! As-tu lu le principe de mon algo ?

Rebonjour GaBuZoMeu,
Merci pour ces précisions je me rappelle avoir vu les combinaisons dans le passé faut juste maintenant que je me rafraichisse la mémoire.
Ton graphique est tout à fait conforme à ce à quoi je m'attendais. (entendu que la proportion des cercles est totalement erronée)
Je n'ai pas consacré encore beaucoup de temps à essayer de transposer tes équations sur Excel mais ai déjà pu constater que le plus gros nombre factoriel qu'il assume est 170! (7,25E+306) je ne sais pas encore si ce peut être bloquant.

@ bientôt et merci à tous les deux

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Probabilités à l'intérieur d'un cube

par GaBuZoMeu » 24 Jan 2021, 09:30

Bonjour lyceen95,

Si tu avais lu mes messages avec attention, tu aurais vu que j'écris :
simplifions la question à l'extrême en supposant que tous les pas sur la grille ont le même coût

et que je suppose que tous les chemins de longueur de grille minimale sont équiprobables.

Je sais très bien que ce n'est pas le problème de Steph3112, mais une version extrêmement simplifiée où le coût de chaque pas n'intervient pas.

Steph3112
entendu que la proportion des cercles est totalement erronée

Non, la surface des disques reflète exactement la probabilité de passer par le noeud en question, sous les hypothèses que j'ai indiquées.

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Probabilités à l'intérieur d'un cube

par lyceen95 » 24 Jan 2021, 13:04

Chris ou Steph... c'est la même personne, c'est toi.

Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Re: Probabilités à l'intérieur d'un cube

par Steph3112 » 26 Jan 2021, 01:25

Re-bonjour GaBuZoMeu,
J'ai pu tester tes 2 premières équations et vérifier avec des toutes petites valeurs de a,b,c et i,j,k que cela marchait bien. Je n'ai pas encore réussi à bien lire la troisième. Equivaut-elle à diviser le nombre de chemins passant pat i,j,k par le nombre total de chemins ? Concernant ton graphique effectivement la surface des cercles est bien représentative de la probabilité en 2D (je pensais que ces surfaces étaient erronées car j'avais envisagé le problème comme un problème 3D aplani.)
Fin de ce Post. Je m'apprête à en diffuser un nouveau avec problème élargi.

Steph3112
Membre Naturel
Messages: 24
Enregistré le: 10 Oct 2020, 22:12

Re: Probabilités à l'intérieur d'un cube

par Steph3112 » 26 Jan 2021, 01:34

Bonjour,
Dédoublement de mon problème : Mon algo gère deux modes de diffusion: "Adjacent", celui que GaBuZoMeu a envisagé dans son Post (la diffusion ne se fait que par les 6 faces d'un cube central) mais aussi "Périphérique" (la diffusion peut passer par les 26 cubes entourant un cube central, soit par les faces, par les arêtes ou par les coins).
Ainsi en périphérique on obtient toujours une somme résistive et un nombre d'étapes inférieur qu'en adjacent.

Dans ces deux cas voici ce que l'on peut connaitre :
- La dimension de la matrice (le gros cube ou prisme)
- Les positions des points de départ et d'arrivée (donc les distances en X,Y et Z qui les séparent)
Voici ce qu'il faut ignorer :
- La résistance de chacun des petits cubes (car elle changera d'un calcul à l'autre)

Voici quelques réflexions sur ces deux modes:
En adjacent un cube ne change que dans une dimension par rapport au cube précédent et ne dispose que de deux alternatives : s'approcher (le plus fréquent) ou s'éloigner (rare) du cube d'arrivée.
En périphérique on agit dans les trois dimensions d'un coup et pour chacune de ces dimensions on peut soit :
- S'approcher
- S'éloigner
- Stagner
Le cube s'éloignant dans les 3 dimensions est le moins probable tandis que le cube s'approchant dans les 3 dimensions est le plus probable.
Mon idée serait de, en commençant par le point de départ, calculer la probabilité de chacun de ses 6 ou 26 cubes alentours, répéter ce calcul sur ces derniers, faire le produit des probabilités, s'écarter comme ça concentriquement du point de départ et exclure ceux sous un certain seuil de probabilité.

Cette logique vous parait-elle tenir la route ? Si oui je ne sais pas encore calculer les 6 ou 26 probabilités de mes cubes alentours et je suppose que les décalages respectifs en X, en Y et en Z du cube en cours d'étude par rapport au cube d'arrivée doivent jouer sur cette probabilité.
Là s'arrête ma science, je suis preneur de toute idée sur la logique et si la logique que je viens d'exposer vous semble OK comment calculer ces probabilités ?
Un grand merci par avance.

 

Retourner vers ✎✎ Lycée

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 40 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite