Jeux de policiers et voleurs, Mod��les et applications

Les jeux de policiers et voleurs sont ��tudi��s depuis une trentaine d���ann��es en informatique et en math��matiques. Comme dans les jeux de poursuite en g��n��ral, des poursuivants (les policiers) cherchent �� capturer des ��vad��s (les voleurs), cependant ici les joueurs agissent tour �� tour et sont contraints de se d��placer sur une structure discr��te. On suppose toujours que les joueurs connaissent les positions exactes de leurs opposants, autrement dit le jeu se d��roule �� information parfaite. La premi��re d��finition d���un jeu de policiers-voleurs remonte �� celle de Nowakowski et Winkler [39] et, ind��pendamment, Quilliot [46]. Cette premi��re d��finition pr��sente un jeu opposant un seul policier et un seul voleur avec des contraintes sur leurs vitesses de d��placement. Des extensions furent graduellement propos��es telles que l���ajout de policiers et l���augmentation des vitesses de mouvement. En 2014, Bonato et MacGillivray [6] propos��rent une g��n��ralisation des jeux de policiers-voleurs pour permettre l�����tude de ceux-ci dans leur globalit��. Cependant, leur mod��le ne couvre aucunement les jeux poss��dant des composantes stochastiques tels que ceux dans lesquels les voleurs peuvent bouger de mani��re al��atoire. Dans ce m��moire est donc pr��sent�� un nouveau mod��le incluant des aspects stochastiques. En second lieu, on pr��sente dans ce m��moire une application concr��te de l���utilisation de ces jeux sous la forme d���une m��thode de r��solution d���un probl��me provenant de la th��orie de la recherche. Alors que les jeux de policiers et voleurs utilisent l���hypoth��se de l���information parfaite, les probl��mes de recherches ne peuvent faire cette supposition. Il appert cependant que le jeu de policiers et voleurs peut ��tre analys�� comme une relaxation de contraintes d���un probl��me de recherche. Ce nouvel angle de vue est exploit�� pour la conception d���une borne sup��rieure sur la fonction objectif d���un probl��me de recherche pouvant ��tre mise �� contribution dans une m��thode dite de branch and bound.