Inscription / Connexion Nouveau Sujet
Stationnement bis
Bonsoir,
un problème inspiré par 
On a une rue infinie dont les places sont numérotées à partir de 1.
Chaque place à une probabilité p inconnue d'être occupée.
Quand on est au niveau de la place k on peut voir toutes les places libres consécutives à partir de cette place. Par exemple si les places 1, 2 et 6 sont occupées et que les places 3, 4 et 5 sont libres on voit en arrivant au niveau de la place 3 que les places 4 et 5 sont libres et que la place 6 est occupée mais on ne sait rien sur les places numéros 7 et plus.
Quelle est la meilleure stratégie pour se garer le plus près possible de la place 20 ?
Bonjour Verdurin ...il y a quelques ambiguités ....
Quand on est au niveau de la place k on peut voir toutes les places libres consécutives à partir de cette place
donc de k à n ?
Par exemple si les places 1, 2 et 6 sont occupées et que les places 3, 4 et 5 sont libres on voit en arrivant au niveau de la place 3 que les places 4 et 5 sont libres et que la place 6 est occupée mais on ne sait rien sur les places numéros 7 et plus.
pour l'exemple que tu donnes , on se trouve initialement ou ? tu dis ensuite que depuis 3 , on vois 3,4,5 libres et pas 6 , mais on ne sait rien sur la place 7 ...ca m'a l'air contradictoire avec la premiere partie de l'enoncé sauf erreur de ma part
ou alors ...est ce qu'il faut comprendre qu'on peut voir toutes les places libres que seulement entre deux places occupées ?
Moi ça me semble clair.
Chaque place a une probabilité p (la même) inconnue d'être occupée.
De chaque place, on voit jusqu'à la première place occupée (on voit les places libres consécutives à partir de la place courante).
L'idée est d'estimer p pour savoir s'il vaut mieux s'arrêter à la dernière place libre visible ou continuer au delà de celle-ci.
J'ai pas encore eu le temps de me pencher dessus mais ça à l'air intéressant.
Bonsoir,
ou alors ...est ce qu'il faut comprendre qu'on peut voir toutes les places libres que seulement entre deux places occupées ?
@LittleFox C'est le problème et je viens de m'apercevoir que ma solution est fausse. En fait il manque des hypothèses.
Si quelqu'un a une idée . . .
Bonsoir,
Je suppose qu'on ne peut pas revenir en arrière car sinon la stratégie à appliquer est assez évidente 
.
@verdurin : je dirais que la donnée manquante est une pénalité qui indique un "coût" en fonction de la place où on se gare : 0 si place=20, positif sinon, croissante avec l'éloignement par rapport à 20 ... enfin un truc du genre.
Salut thetapinch27.
Le coût est la valeur absolue de la différence entre le numéro de la place de stationnement et 20.
Bien entendu on ne peut pas reculer.
Bonjour à tous
Je peux me tromper mais il me semble que la stratégie est assez simple . A un rang donné , on peut estimer le taux moyen d'occupation des places . S'il y a plus d'une chance sur deux qu'il reste une place libre avant la 21ème on continue .
A vérifier tout de même 
Imod
Soit k la place courante, k' la prochaine place occupée, n la place objectif, p' une estimation de p.
On a p' = (#place occupées <= k')/k'.
On a k<k'.
Si k' >= n, on s'arrête à la place libre visible la plus proche de n.
Sinon, il faut estimer la distance à n si on continue. Si celle-ci est inférieure à n-(k'-1) alors on continue. Sinon on s'arrête.
Je ne suis pas si sûr que ce soit équivalent à avoir plus d'une chance sur deux de trouver une place libre dans [k'+1, 2n-k'].
Je pense que ça dépend de comment on définit meilleure stratégie.
Mon ordinateur ne supporte plus la canicule : je vais être très bref
Mon critère n'est certainement pas bon mais après je ne vois qu'une stratégie sans ajouter d'autres paramètres . Si après la dernière place visible sur un intervalle centré sur 20 on a plus d'une chance sur deux de trouver une place libre avec les statistiques disponibles , il faut continuer . ensuite le choix est évident .
Imod
Annuler
connectez vous