Les échelles de mots de Lewis Carroll, une application de GraphSearch et du problème de l'arbre de Steiner
Source: chapitre 33 de « Selected Papers on Fun and Games » de Donald E. Knuth.
Une échelle de mots est un jeu qui consiste à trouver, connaissant un mot de départ et un mot d’arrivée une succession de mots tel que le mot \(i+1\) est semblable au mot \(i\) (au sens où une transformation simple suffit à passer du mot \(i\) au mot \(i+1\)).
Nous allons considerer une version simplifiée du jeu qui n’autorise que l’opération de changement d’une lettre sur les mots (on ignore les opérations « ajout / retrait de lettre » et « changement de l’ordre des lettre »).
L’objectif est de trouver la séquence de mots de longueur minimale pour passer du mot initial au mot final.
On se donne comme liste de mots anglais le fichier /usr/share/dict/words présent sur certaines distributions GNU/Linux.
Algorithme de recherche de graphe en largeur d’abord
On filtre déjà le fichier pour ne garder que les mots avec 5 lettres:
mkdir -p tmp
awk 'length($0) == 5' /usr/share/dict/words > tmp/words5.txt
wc -l tmp/words5.txt
7044 tmp/words5.txt
initial = "glass"
goal = "spoon"
from typing import Iterable
def load_words(filename: str) -> set[str]:
with open(filename, "r") as f:
words: set[str] = set(
[
word.lower()
for word in f.read().splitlines()
]
)
return words
ALPHABET: str = "abcdefghijklmnopqrstuvwxyz"
def successor_words(word: str, candidates: set[str]) -> Iterable[str]:
for i in range(len(word)):
for other_letter in ALPHABET:
if other_letter != word[i]:
successor = list(word)
successor[i] = other_letter
successor = ''.join(successor)
if successor in candidates:
yield successor
words: set[str] = load_words("tmp/words5.txt")
list(successor_words(initial, words))
| class | grass | gloss | glads |
Maintenant que l’on sait comment obtenir un mot dérivé d’un autre mot par l’échange d’une unique lettre, on explore le graphe des doublets jusqu’à tomber sur le mot cible, en profondeur d’abord pour garantir un nombre d’étapes minimal.
import queue
from dataclasses import dataclass
from typing import Any, Self, Callable
@dataclass
class Node:
value: Any
parent: Self
def graph_search(initial_node: Node, expand_function: Callable[Node, Iterable[Node]], goal_test_function: Callable[Node, bool]) -> Node:
""""
Effectuer une recherche en largeur en largeur avec Graph-Search
initial_node -- noeud de l'état initial à étendre
expand_function -- fonction générant les noeuds successeurs
goal_test_function -- fonction vérifiant si un noeud est un état du but
"""
frontier: queue.Queue = queue.Queue()
frontier.put(initial_node)
explored: set[Node] = []
while not frontier.empty():
node = frontier.get()
if goal_test_function(node):
return node
successors = expand_function(node)
explored.append(node.value)
for successor in successors:
if successor.value not in explored:
frontier.put(successor)
return None
def reverse_path_to_root(leaf_node) -> list:
"""
Calculer le chemin de la racine au noeud de l'arbre donné
"""
path: list = [leaf_node.value]
current_node = leaf_node
while current_node.parent != None:
current_node = current_node.parent
path.append(current_node.value)
return path[::-1]
Maintenant qu’on a définit la structure générique du GraphSearch, on l’applique à notre problème:
def goal_test_function(state: Node) -> bool:
return state.value == goal
def expand_node(state: Node) -> Iterable[Node]:
for word in successor_words(state.value, words):
yield Node(word, state)
initial_node: Node = Node(initial, None)
final_node: Node = graph_search(initial_node, expand_node, goal_test_function)
path: list[str] = reverse_path_to_root(final_node)
" → ".join(path)
glass → gloss → glows → slows → shows → shoos → shoon → spoon
Les triplets
On sait trouver le chemin le plus court entre deux mots, par changement d’une seule lettre à la fois. Essayons maintenant de faire la même chose avec un triplet de mots.
On ne peut plus se contenter de l’algorithme GraphSearch. Ce que l’on cherche à faire correspond plutôt au problème de l’arbre de Steiner.
Problème de l’arbre de Steiner
Soit un graph non-orienté \(G(V, E)\), et un ensemble \(C \subseteq V\) de noeuds terminaux. L’objectif est de trouver un arbre de poids minimum contenant tous les nœuds de \(C\).
Dans notre cas, les nœuds sont les mots, une arête lie les mots \(u\) et \(v\) s’il existe une transformation simple de \(u\) vers \(v\). Les noeuds terminaux sont les mots que l’on veut relier.
Création du graphe (avec networkx)
import networkx as nx
import itertools
G = nx.Graph()
for word in words:
G.add_node(word)
for word1 in words:
for word2 in successor_words(word1, words):
G.add_edge(word1, word2)
Des solutions approximées
Le problème de l’arbre de Steiner est NP-complet, ce qui rend son application à de gros graphe inaccessible dans un temps raisonnable.
Il existe plusieurs algorithmes approximés pour résoudre ce problème.
Je vais me contenter, dans un premier temps d’appliquer ceux déjà implémentés dans networkx (Kou, Markowsky, and Berman 1981; Mehlhorn 1988).
Les algorithmes implémentés dans networkx attendent un graph connecté en entrée, je vais donc commencer par extraire les composantes connexes du graphe de mots:
S = [G.subgraph(c).copy() for c in nx.connected_components(G)]
Puis, j’identifie la composante connexe qui contient les mots terminaux
terminals = ["blood", "sweat", "tears"]
def identify_component(terminals, subgraphs):
for component in subgraphs:
if all([word in G.nodes
for word in terminals]):
return component
return None
component = identify_component(terminals, S)
assert component is not None
from networkx.algorithms.approximation import steiner_tree
# kou_solution = steiner_tree(component, terminals, method="kou")
mehlhorn_solution = steiner_tree(component, terminals, method="mehlhorn")
On retrouve bien les trois mots tears, sweat et blood dans l’arbre de la solution.
Comme on est en présence d’un algorithme \(\alpha\)-approximé (avec ici \(\alpha = 2(1-1/l)\), \(l\) étant le nombre total de feuilles dans un arbre de Steiner minimal), il peut exister une solution plus courte.