Discussion :

[Barnabech]

Bonjour
J'essaye de modéliser un touriste qui se promène dans un parc. Dans ce parc il y a des chemins qui lui plaise et d'autre pas. Je veux que le touriste se promène dans le parc en empruntant les chemins qu'il préfère. Seulement son but n'est pas de trouver le plus court chemin mais bien de se balader et donc il peut prendre plusieurs fois le même chemin tant qu'il lui reste du temps pour sa promenade.
Est ce que vous avez des idées d'algorithme que je pourrais utiliser ?

Merci

[millie]

Le touriste a t'il connaissance du graphe du parc? Dans le cas où il a un plan, on peut imaginer qu'il a une connaissance totale du parc mais pas des chemins qui lui plaisent et qui lui plaisent pas (qui seront visibles que lorsqu'il sera à cet endroit)

[Barnabech]

Le touriste a une connaissance total du parc. De plus il connait les chemins qui vont lui plaire.

[ToTo13]

Bonjour,

tu peux faire des parcours aléatoires :
- A un carrefour, le touriste prend aléatoirement un chemin parmi ceux qui lui plaisent.
- Si pas de chemin favoris, alors demi tour.

Sinon tu peux appliquer cet algo à l'avance sur la carte afin d'éviter les demis tours.

Sinon, tu peux encore faire la même chose, mais avec tous les chemins ! Tu mets une probabilité de prendre le chemin qui sera proportionnelle au fait que le touriste aime ce chemin. Ce parcours sera déjà plus sympa dans le sens que dans la grande majorité des cas il prendra les chemins qu'il préfère, mais rarement il testera un autre chemin.

[Alp]

On ne peut pas aussi imiter un algo de fourmis en faisant comme s'il y avait des féromones ou je ne sais quoi sur les chemins qui plaisent au touriste ?
Cela doit de toute manière rejoindre ce qu'a dit ToTo13.

[millie]

Sauf qu'il faut mettre des poids sur les chemins car sinon il y a une probabilité non nul pour que la personne ne sorte jamais.

[Alp]

Sauf qu'il faut mettre des poids sur les chemins car sinon il y a une probabilité non nul pour que la personne ne sorte jamais.

Qui a dit qu'elle voulait sortir ?

[millie]

Qui a dit qu'elle voulait sortir ?

tant qu'il lui reste du temps pour sa promenade.

A moins qu'à la fin de la promenade, il se pose là où il est pour camper... Mais c'est possible aussi

[Alp]

Donc l'idée serait de pondérer plus fortement les chemins qu'il aime mais qui en plus l'amènent à la sortie, c'est ça ?

Mais là quand il rentre il aura envie de sortir de suite, non ?

Edit : pour ça, suffit d'orienter les chemins.

[Barnabech]

Merci pour toutes vos réponses, je vais essayer de faire qqch et de vous le montrer !

[millie]

Donc l'idée serait de pondérer plus fortement les chemins qu'il aime mais qui en plus l'amènent à la sortie, c'est ça ?

Je pensais que la pondération était lié au temps.

Je pensais créer un sous graphe à partir du graphe initial qui contiendrait uniquement les chemins qui plaisent. Mais si le graphe n'est pas connexe, il est possible qu'il faille ajouter des chemins qu'ils aiment pas pour rendre le graphe connexe afin d'aller à certains endroits qu'ils souhaitent. (problématique plus simple dans un graphe non orienté que dans un graphe orienté)

Mais bon, les sujet n'était pas très clair, ça dépend

[Alp]

On est obligé de l'orienter car sinon ça risque de poser problème pour sortir.

Et puis il faut aussi créer les chemins les plus courts possibles entre 2 chemins qu'il aime afin qu'il n'y ait pas de "trou" et qu'il soit mécontent le moins longtemps possible :p
C'est à faire aussi entre l'entrée et le chemin qui lui plaît le plus proche de l'entrée, si nécessaire, et de même pour la sortie.

[millie]

On est obligé de l'orienter car sinon ça risque de poser problème pour sortir.

Pourquoi ? Un chemin peut être pris dans les deux sens (à moins que l'on considère certains passages à sens unique comme saut d'un mur )

[Barnabech]

En faite je souhaitais modéliser une petite station de ski donc il s'agit d'un graphe orienté. J'ai pris l'exemple d'un parc pour faire plus "problème général". :p
Le but est de modéliser les skieurs, ceux qui ont un comportement sportif et qui vont donc préférer les pistes rouges et noires et les skieurs débutants qui vont prendre que les pistes vertes et bleus. J'ai déjà modélisé une partie de la station et j'utilise l'algo de Djikstra pour aller d'un point à un autre mais je trouve que ce n'est pas très intéressant. Je suis en train de tenter de faire qqch avec tout ce que vous avez dit précédemment mais mon niveau en programmation et algo est très très limité donc ca risque de prendre du temps :p

[JeromeBcx]

Dans le cas du skieur,

Il faudrait différencier les remontées et les pistes, sachant qu'il est possible d'avoir plusieurs pistes de niveaux différents pour une remontée. Pour l'histoire du temps et du retour à la station, il faut paramétrer les temps nécessaires pour la remontée et les différentes pistes. Ainsi, en fonction du temps qu'il lui reste, il va pouvoir calculer le parcourt le plus intéressant mais qui lui permet de rentrer avant la fermeture de la station.

Evolution possible : ajouter le temps d'attente aux remontées... et construire un scénario en fonction du niveau du skieur (ex du très bon skieur): si piste noire, beaucoup de temps d'attente, mais piste géniale, alors attendre. Si piste verte et personne, passer son chemin...

[3DArchi]

Un graphe orienté donc avec des poids sur les arêtes pour la préférence et réactualisés à chaque franchissement d'une arête par un facteur lié au temps restant disponible pour retourner en bas des pistes (pondération de plus en plus forte pour le chemin le plus court au fur et à mesure que le temps baisse). Il faut peut-être aussi masquer des arêtes -via des poids nuls: pas de piste noire pour un débutant, pas de piste bleu(? je ne connais pas les couleurs) pour un chevronné. Un skieur va-t-il avoir un trajet aléatoire sur une base préférentielle ou va-t-il renforcé des parcours au fur à mesure qu'il les emprunte? Sa préférence est-elle constante dans le temps :au début des pistes simples, et en fin de journée s'éclater sur des choses plus frontière avec son niveau, ou au contraire à fond à fond dès le début et à la fin plus calme car plein les pattes? Ma foi, un projet qui à l'air fort intéressant.

[Barnabech]

Bonjour,
J'ai essayé d'avancer l'algo mais j'ai des difficultés.
Pour commencer j'ai choisit une méthode assez simple. Je vais expliquer ce que j'ai fait.

Tout d'abord j'ai mis des poids sur les arcs qui représentent la probabilité d'un chemin d'être emprunté. Au départ, il y a équiprobabilité.
Puis on part d'un noeud que j'appelle nœud père.
Ensuite on liste et on compte touts les chemins qui partent de ce noeud.
Apres il y a une phase qui compte les chemins intéressants et diminue le poids d'un chemin pas intéressant. On répartie équitablement les points enlevés entre les chemins intéressants. La somme des poids des chemins partant d'un noeud reste égale a 100. Cette phase est répétée deux fois de suite.
La première, j'utilise le nombre de fois qu'a été parcouru le chemin pour savoir si il est intéressant ou pas. Si il a été parcouru plus de 3 fois, il n’est pas intéressant. Son poids est divisé par deux.
La deuxième, chaque chemin possède la propriété « intéressant ou pas » stocké dans une table. J’utilise cette propriété pour savoir si le chemin est bien ou pas. Si le chemin n’est pas super, sa probabilité d’être emprunté est divisée par 4.

J'ai mis en ligne ce que j'ai fait : au bout de 3-4 pistes il ne fait que la piste 1 et la remonté 3.
http://tassounet.free.fr/algo/algo_touriste.php5
De plus avec cet méthode il est difficile d'ajouter le temps d'attente en bas des remontées.

Est ce que vous pensez que le principe est bon ?

Merci de votre aide

[3DArchi]

Bonjour,
La première, j'utilise le nombre de fois qu'a été parcouru le chemin pour savoir si il est intéressant ou pas. Si il a été parcouru plus de 3 fois, il n’est pas intéressant. Son poids est divisé par deux.

Un chemin parcouru + de 3 fois devient non-intéressant: tu arrive à une situation où tout tes chemins intéressant parcourus 3 fois sont non-intéressant, donc cette 'mémoire' devient inutile. En d'autre terme, cette règle devient neutre puisque elle a été appliquée sur tous les chemins intéressant. Je pense que tu devrais plutôt utiliser quelque chose comme les chemins qui ont été parcouru au cours des 3 dernier parcours voient leur poids diminué. Cela permet à un chemin parcourus de redevenir intéressant au quatrième coup. Une autre possibilité est d'atténuer le poids du chemin par la profondeur historique du parcours: en moins verbeux, le poids est divisé par un facteur d'autant plus grand qu'il a été parcouru récemment (exemple: par 4 pour le dernier, 3 pour l'avant dernier, 2 l'anté-pénultième).
Ensuite, tu utilises une division par 2 pour les chemins parcours et par 4 pour les chemins non intéressant: n'obtiens-tu pas une poids bien trop faible alors pour ces derniers? Les coefs sont peut-être à ajuster.