Trouver la sortie.

Bonjour à vous. Voici un petit problème dont l'énoncé ne paie pas de mine mais dont la solution n'est pas évidente :

Vous vous trouvez en face d'un mur et vous voulez passer de l'autre coté. Le mur est trop haut et trop lisse pour qu'il soit possible de l'escalader et il s'étend à l'infini à gauche comme à droite.
Dans ce mur il y a une porte qui est percée mais vous ne savez pas si elle se trouve à droite ou à gauche de vous. Cette porte se trouve à une distance "d" de vous que vous ignorez.
Il vous faut pourtant trouver cette porte sachant que vous ne pouvez la voir que si vous êtes directement en face d'elle. De plus il vous faut parcourir une distance qui soit un O(d), c'est à dire au maximum un multiple constant de "d".
De toutes façons, même si vous ne savez pas ce qu'est un O(d), vous pouvez chercher la solution la plus courte possible, je vous dirais s'il y a plus court ou non.

Salut.

Quelle est la question ? Plus courte dans le temps ou l'espace ? Parce que si c'est l'espace je prends une pioche et creuse à travers le mur ou en dessous vu que l'on n'a pas d'informations sur le sol. Donc dans ce cas le plus court dans l'espace c'est l'épaisseur du mur à un ou deux mètres près.

En plus la porte est "percée", ça veut dire que l'on peut la franchir ? Sinon je ne vais pas bouger pour rien. Bref vu que ce genre de problème joue sur les mots en général, je préfère que l'on dispose de petites précisions, la question exacte étant la plus importante dans le tas.

Tout ça pour dire que vu qu'au vu du problème le max doit être embêtant à trouver, il faut donc être précis. Si le minimum est moins que d, ben je reviens sur ma première solution. :razz:

Ah ! Autre chose. Le sol est plat ? Bon j'arrête avec mes questions à la noix. Si c'était important de le savoir tu l'aurais écrit.

Je me suis dit au départ que (si on est obligé de passer par la porte, que notre vitesse de déplacement est constante et que l'on ne dispose que de nous même pour trouver la porte) il suffirait de faire des aller-retours gauche-droite de distance de plus en plus grande. Le problème c'est de jouer sur la probabilité de trouver la porte en la distance la plus courte, parce que cet algorithme de recherche risque d'avoir des résultats très différents selon que d est grand ou non (le paramètre variable étant la distance gauche droite qui augmente).

On pourrait augmenter la distance au centre (notre point de départ) en logarithme ou en exponentielle par exemple :

$\displaystyle \text \sum_{j=1}^{n} \left(\sum_{i=1}^{j}\ln(i)\right)$
$\displaystyle \text \sum_{j=1}^{n} \left(\sum_{i=1}^{j}\e(j)\right)$

Connaissant la vitesse de déplacement on peut voir quelle fonction utiliser pour tester le plus de valeurs de d en le moins de temps possible. Après faut choisir la bonne fonction en fonction de la distance au centre et de où l'on en est... bref ce ne doit pas être une bonne façon de faire. Il faut aussi tenir compte de l'hypothèse O(d) qui doit mener sur la piste de la bonne complexité à rechercher.

Pour trouver l'algorithme de plus court chemin (à moins qu'il y ait une véritable astuce) il faudrait peut-être passer par des calculs de probabilités et de complexité donc. Bizarrement ce problème me dit quelque chose, j'ai déjà dû le rencontrer sous une autre forme.

Bon je m'arrête là : j'ai de la fièvre et ma Freebox n'arrête pas de désynchroniser, c'est embêtant.

@+

Ce n'était peut-être pas parfaitement clair mais c'est bien la distance que l'on doit parcourir qui doit être la plus courte possible.
Le sol est aussi froid, lisse et immuable que le mur et on ne peut le creuser à main nue. On ne dispose pas d'outils (à part des instruments de géométrie élémentaire si on veut prendre son temps pour réfléchir avant d'aller chercher la porte).

L'énoncé originel ne mentionne pas l'interdiction de s'éloigner du mur mais, comme il faut être juste devant la porte pour la voir, cela semble inutile.

"il suffirait de faire des aller-retours gauche-droite de distance de plus en plus grande."

Le problème c'est qu'en faisant ça tu arrives vite a une complexité en d².
Je vais noter O le point de départ et distinguer une direction/O (par rapport à O) d'une direction (par rapport au personnage).

Si tu commences par aller à droite/O de 1, puis que tu veux aller à gauche/O de 2 il faut que tu déplaces de 3 vers la gauche. Puis si tu veux aller à droite/O de 3 il faut que tu te déplaces de 5 vers la droite (tu t'es alors déplacé en tout de 9).
En continuant ainsi, lorsque tu arrives à une distance d (par exemple à droite/O) tu t'es alors déplacé en tout de :
$1+3+5+...+(2n+1)⏟d\underbrace{ 1+3+5+...+(2n+1) }_{d}$

(bon normalement il faudrait discuter selon la parité de "d" ou s'il est à gauche ou à droite de O mais ici, des résultats exacte sur la distance parcourue ne nous intéresse pas, le problème est qu'elle dépend du carré de "d" ce qui ne va pas).

Peut-être qu'une autre fonction que la simple incrémentation pourrais fonctionner. Qui sait ?

le plus court est de partir d un coté et de ne jamais faire demi tour

tkt tu peu pa test

Si si tu peux test, mais il vaut mieux éviter.

Si tu pars dans une direction au hasard, tu as une chance sur deux de parcourir une distance infinie et une chance sur deux de parcourir d.
Ce qui te donne pour la distance parcourue une espérance de $d+∞2=+∞\frac{d+\infty}{2}=+\infty$ .
Tu n'es donc pas en O(d).

P.S : Tu vois, j'ai testé, ça ne m'inquiète pas outre mesure.

je croyai que la solution la plus courte était la réponse attendu

se que je propose me semble etre le chemin le plus court pour trouver la porte...

a moins que "d" appartient a un interval definit mais comme j'ai compris l'énoncé d peut etre n importe quoi entre 0 et l infinit ?

sinon on peu doubler la distance a chaque fois

bonjour !

je pense qu'il faudrait se donné un point de départ et je partir vers la gauche du mur jusqu'a une certaine distance , revenir au point de départ et faire le double de la distance parcourue vers la droite .c'est ce que j'ai compris en tout cas.