Barbara
RÉSOUDRE LE MYSTÈRE DE “QUI A TUÉ LE DUC DE DENSMORE” À L’AIDE DE LA THÉORIE DES GRAPHES, DE LA PROGRAMMATION PAR CONTRAINTES, ET DE LA PROGRAMMATION LINÉAIRE ENTIER MIXTE
La gestion des stocks, l’optimisation de portefeuille, la planification de machines, l’acheminement de véhicules, et de nombreux autres problèmes de la vie réelle sont d’excellents exemples de l’utilisation de techniques analytiques et de la science des données. Il n’est pas surprenant que ce soient certains des premiers problèmes que nous apprenons à l’université. Cependant, je suis fasciné par les innombrables autres problèmes qui peuvent être représentés comme une entité abstraite appelée modèle, qui peut être un graphe, un emploi du temps, ou un ensemble d’équations mathématiques et résolu en utilisant les techniques appropriées. Une fois que vous avez acquis les compétences de modélisation, il est facile d’appliquer ces techniques à la fois à un problème de chaîne d’approvisionnement et à un simple puzzle.
Dans cet article, je vais montrer comment le mystère de l’assassinat du duc de Densmore peut être résolu en utilisant la théorie des graphes, la programmation par contraintes et la programmation linéaire entier mixte.
LE MYSTÈRE DU DUC DE DENSMORE
Le livre “Who Killed the Duke of Densmore” de Claude Berge est une histoire de mystère qui se concentre sur l’identification de la personne qui a placé une bombe dans le château de Densmore sur l’île de White, entraînant la mort du duc. Malgré l’écoulement de dix ans, l’affaire est restée non résolue jusqu’à ce que Sherlock Holmes et Watson décident de s’y intéresser.
Lorsque le duc de Densmore a perdu la vie à la suite d’une explosion de bombe dans son château sur l’île de White, ses six ex-épouses – Ann, Betty, Charlotte, Edith, Felicia, Georgia et Helen – sont devenues les principaux suspects. Cette affaire était compliquée par la destruction du testament du duc dans l’explosion, qui aurait été sévère envers l’une des anciennes épouses. Cependant, il a été révélé que les six femmes avaient reçu des invitations au château avant que la tragédie ne se produise.
Toutes ses ex-épouses ont juré qu’elles n’étaient allées au château qu’une seule fois. Elles ne se souvenaient pas non plus de la durée de leur séjour, mais savaient qui elles avaient rencontré pendant leur visite.
Le détective Sherlock Holmes et son assistant, Watson, croient que le meurtrier est l’une des ex-épouses, car elles avaient toutes prétendu n’être allées au château qu’une seule fois. Cependant, les détectives soupçonnent que l’une des anciennes épouses ment sur le nombre de visites qu’elle a faites au château. Identifier laquelle des ex-épouses a menti sur la fréquence de ses visites est la clé pour résoudre le mystère.
THÉORIE DES GRAPHES
La théorie des graphes est la méthode que Berge a finalement utilisée pour résoudre le mystère, et elle semble être l’approche la plus simple. Chacune des ex-épouses avait une durée de séjour spécifique au château, avec une heure d’arrivée et de départ définie. Bien que la durée exacte de leur visite et l’ordre dans lequel elles sont arrivées et parties soient inconnus, nous savons grâce à l’interrogatoire que certaines de leurs visites se sont chevauchées.
Pour simplifier, concentrons-nous sur Helen et ses interactions avec Betty, Felicia et Georgia pendant leurs visites respectives au château. Pour illustrer leurs visites, nous pouvons utiliser des lignes horizontales, les extrémités représentant leurs heures d’arrivée et de départ, comme le montre l’exemple ci-dessous :
Exemple d’intervalles et de chevauchements
Si deux intervalles se chevauchent, cela signifie que les individus correspondants étaient au château simultanément et qu’ils ont donc dû se rencontrer. Nous pouvons représenter les intervalles sous forme de graphique, où chaque nœud correspond à une personne. Si deux intervalles se croisent, nous dessinons une arête entre les nœuds correspondants. Dans le cas d’Helen, Betty, Felicia et Georgia, le graphe résultant ressemble à celui ci-dessous :
Exemple de graphe d’intervalles
Ce type de graphe s’appelle un graphe d’intervalles, qui peut être utilisé pour modéliser n’importe quel ensemble d’intervalles. Cependant, tous les graphes ne peuvent pas être représentés sous forme d’intervalles. Par exemple, considérez le graphe ci-dessous :
Graphe cyclique C4
Il ne peut pas être décomposé en intervalles, car il est impossible de trouver quatre intervalles tels que A-B, B-C, C-D et D-A se croisent. Ce graphe est appelé C4. Si un graphe possède C4 comme sous-graphe, il n’est certainement pas un graphe d’intervalles.
Par conséquent, si le graphe n’est pas un graphe d’intervalles, nous savons qu’au moins une personne a menti sur sa visite au château. Nous pouvons utiliser ce fait pour identifier le vrai coupable en construisant le graphe à partir de l’interrogatoire et en vérifiant s’il s’agit d’un graphe d’intervalles ou non.
Basé sur les informations fournies, Holmes et Watson soupçonnent que le meurtrier a visité le château à plusieurs reprises, ce qui contredit les affirmations des ex-épouses selon lesquelles elles n’avaient visité le château qu’une seule fois.
PROGRAMMATION PAR CONTRAINTES
La programmation par contraintes (CP) est une approche de résolution de problèmes qui traite des problèmes combinatoires et logiques en se concentrant sur la recherche de solutions réalisables qui satisfont des contraintes données. Les algorithmes CP atteignent la convergence en réduisant progressivement l’ensemble de solutions réalisables par l’ajout de nouvelles contraintes. Étant donné sa capacité à gérer des déclarations et des contraintes logiques complexes, la CP est particulièrement efficace pour aborder des problèmes tels que celui-ci.
Pour résoudre notre problème, nous pouvons utiliser un modèle CP, qui implique de définir N comme l’ensemble de personnes, s_i comme l’heure d’arrivée de la personne i au château, d_i comme la durée de sa visite, et e_i comme la fin de sa visite. Nous pouvons également introduire une variable logique v_i, qui est VRAI si la personne i ne peut pas être incluse dans l’horaire de visite, et FAUX sinon. De plus, met_i est l’ensemble des personnes que la personne i a rencontrées pendant sa visite. Les variables entières s, d et e ont une grande borne supérieure (1000) et doivent être non négatives.
Nous utiliserons la bibliothèque ortools pour résoudre ce problème :
Détermination de toutes les cycles simples du graphe à l’aide de la fonction « simple_cycles » de networkx. Tous les cycles élémentaires de toutes les longueurs seront générés.
Pour tous les cycles de longueur égale à 4, générer le sous-graphe en utilisant la fonction « subgraph » et vérifier s’il n’est pas cordal. En d’autres termes, vérifier si le cycle est un C4 – un cycle de longueur 4 où tous les nœuds ont un degré égal à 2.
PROGRAMMATION LINÉAIRE ENTIER MIXTE
La programmation linéaire entière mixte (MILP) est une méthode utilisée pour
