Discussion :

[zenux]

Bonjour,

J'aimerais savoir si il existe des algorithmes de poursuite.

Ce que j'entend par poursuite: par exemple un policer essaye d'attrapper un voleur qui s'achappe dans la rue.

Je ne cherche pas un bête algorthime où le policer cours après le voleur et si le policier ne voit plus le voleur à cause d'un mur ou d'un coin de rue, il stop bêtement sa poursuite.
Un fois le voleur perdu de vue, le policier saurai que le voleur n'a pas pu aller à la prochaine rue à gauche qui est à 1km car il n'aurai pas eu le temps de courrir jusque là. Par contre il aurait très bien pu aller dans la prochaine rue à droite qui est à 100m.

Où encore plus complexe: le policer prendrais des raccourcis pour attrapper le voleur.

Et encore plus complexe: plusieurs policiers qui se parlent entre eux par communication radio pour encercler le voleur.

Merci d'avance...

[PRomu@ld]

Où encore plus complexe: le policer prendrais des raccourcis pour attrapper le voleur.

Assez compliqué à mettre en oeuvre, puisqu'il faut que tu supposes la destination de ton voleur. Ou bien tu sais qu'il n'y a qu'une seule issue et tu as deux chemins pour y arriver, mais dans ce cas tu ne peux éviter que le voleur fasse demi-tour et t'échappes.

Et encore plus complexe: plusieurs policiers qui se parlent entre eux par communication radio pour encercler le voleur.

Ca n'est pas forcément plus complexe. L'idée c'est d'isoler le voleur, quand tu as un policier sur une route, elle est bloquée. Si tu arrives à ce que l'ensemble des issues possible soit nul alors tu as cerné le voleur et il n'y a plus qu'à "refermer le filet". Ca se programme sans doute facilement avec un graphe comme support.

Un fois le voleur perdu de vue, le policier saurai que le voleur n'a pas pu aller à la prochaine rue à gauche qui est à 1km car il n'aurai pas eu le temps de courrir jusque là. Par contre il aurait très bien pu aller dans la prochaine rue à droite qui est à 100m.

Comme v = d/t tu peux supposer la vitesse du voleur et par conséquent la distance qu'il peut parcourir en une durée t. L'idée, c'est de pouvoir faire évoluer un graphe (ou sa pondération) au fil du temps en fonction de cette distance possible (ça doit faire comme un cercle qui grandit). Si tu arrives à bloquer avec l'ensemble des policiers l'ensemble des chemins accessibles à un instant t + dt tu as donc isolé ton voleur (même si tu ne sais pas où il est), à ce moment là, comme précédemment, tu n'as plus qu'à "refermer le filet" .

Ca ne reste que des idées en l'air (sans doute pas applicables en l'état), mais je suis persuadé qu'il s'agit d'un problème de graphe.

Après une première recherche rapide, c'est bien un problème de graphe, regarde du coté de cop ans robber game.