Battle Dev RegionsJob Novembre 2018 - Problème 5

Il y a quelques semaines s’est tenue la 12ème Battle Dev. J’ai décroché la 100e place tout pile, et bien que déçu par mon classement je trouve que les problèmes étaient de très bonne qualité, en particulier les deux plus difficiles dont je vais présenter la solution ici.

L’énoncé du problème 5 est le suivant :

Il y a N élèves, et un professeur souhaite donner des cours particuliers à chacun d’entre eux. Chaque élève est disponible sur deux créneaux de 60 minutes.

On veut donner un cours à chaque étudiant sur l’une de ses deux disponibilités, de telle sorte qu’il n’y ait pas d’intersection entre les cours de deux élèves.

Notre programme sera soumis à une batterie de tests pour vérifier sa validité, N sera inférieur ou égal à 1000 pour chaque test. Si le temps d’exécution dépasse quelques secondes, l’algorithme sera considéré faux.

Résolution du problème

Il existe deux solutions à ce problème, que je vais me charger de présenter dans cet article.

La première est conceptuellement la plus simple mais aussi la moins optimale. Pour autant, la solution est valide et je suis prêt à parier que les organisateurs n’avaient comme moi pas prévu que sa performance serait suffisamment bonne pour valider tous les tests.

Première solution

Il s’agit d’une solution faisant appel au retour sur trace (backtracking), aussi appelé “bruteforce intelligent” – vous comprendrez vite pourquoi. Derrière ce nom barbare se cache un concept facile à comprendre : On essaie de construire une configuration valide petit à petit, et dès qu’on rencontre un cas impossible on revient en arrière.

Introduction au retour sur trace

Pour illustrer le retour sur trace, prenons par exemple une grille de sudoku très simple 3x3 :

img 00

Il y a 6 cases à remplir, et 3 possibilités pour chaque case. Par conséquent, nous avons 3⁶ = 729 possibilités si nous décidons de faire une exploration exhaustive (= bruteforce) des réponses possibles.

Pour cette grille particulière très simple on pourrait bien sûr envisager une résolution intelligente (par exemple en remarquant que la case vide à gauche est forcément un 2). Cependant dans certaines instances complexes du sudoku, les seules solutions viables font appel au retour sur trace.

On va explorer les solutions possibles en construisant au fur et à mesure et en essayant d’aller le plus loin possible, jusqu’à aboutir à une solution valide. Pour commencer, on cherche une valeur de la première case qui n’introduit pas de problème immédiat :

img 01

Impossible de mettre la valeur 1 dans cette case, car la première ligne contient deux fois la même valeur.

img 02

Cette configuration est valide car aucune règle du sudoku n’est rompue.

img 03

On verrouille donc cette première case et on entame l’exploration de la prochaine case vide.

img 04

Ici, la grille est invalide car la première ligne contient deux fois la valeur 1.

img 05

Ici encore, la première ligne pose problème.

img 06

On ne peut pas mettre un 3 dans cette case car il y en a un dans la même colonne.

Dans ce cas, nous avons épuisé toutes les possibilités de la deuxième case disponible, sans trouver de configuration valide. Il nous faudra donc revenir d’un pas en arrière et reprendre l’exploration de la première case, d’où le nom de “retour sur trace”. Nous revenons ici en arrière d’une seule case, mais il peut arriver d’avoir à remonter beaucoup plus faute d’avoir trouvé des configurations valides.

img 07

img 08

img 09

img 10

img 11

Et ainsi de suite…

Retour sur trace dans le cadre du problème 5

On peut voir notre problème de choix d’intervalles de la même manière que la grille de sudoku et appliquer un algorithme de backtracking. Une configuration valide sera une liste de N valeurs 1 ou 2. Chaque valeur correspond à un étudiant, et vaut 1 si l’on choisit de lui donner cours sur son premier intervalle et 2 si l’on choisit le second.

Il y aura parfois des incompatibilités entre le créneau de l’étudiant que l’on vient de choisir et un autre créneau horaire précédemment sélectionné. Dans ce cas, il suffira de revenir sur nos pas, aussi loin que nécessaire, pour retrouver une configuration valide et repartir de là.

Voici ma solution en backtracking pour cet exercice :

import sys

N = int(input())
intervals = []
for i in range(N):
    a, b = map(int, input().split())
    intervals.append((a,b))

#On détermine une fois pour toutes quels intervalles sont en collision
collision = [([],[]) for _ in range(N)]
for first in range(N):
    for second in range(first+1, N):
        for firstpos in (0,1):
            for secondpos in (0,1):
                if abs(intervals[first][firstpos]
                           - intervals[second][secondpos]) <= 60:
                    collision[second][secondpos].append((first, firstpos))
                    # Pas besoin ici d'ajouter la collision réciproque :
                    # on ne cherchera les conflits que vers l'arrière

state = [1] * N
ptr = 0

print(intervals, file=sys.stderr)
# Oui c'est sale de faire un while True, mais c'est de la
# programmation compétitive, pas du code qui va partir en prod ;)
while True:
    # On vérifie que l'état partiel est valide
    okstate = True
    for student, pos in collision[ptr][state[ptr]-1]:
        if state[student] == pos+1:
            # On vient de choisir un intervalle en conflit avec un autre
            # intervalle précédemment sélectionné, donc on revient sur nos pas
            okstate = False
            break
        
    if okstate:    #Si l'état partiel est valide, on avance
        if ptr == N-1:
            # On a trouvé un état entier valide sans conflit
            for s in state: print(s)
            sys.exit(0)
        ptr += 1
        state[ptr] = 1

    else:          #Sinon, on revient sur nos pas
        while state[ptr] == 2 and ptr > 0:
            ptr -= 1
        if ptr < 0:
            # On a tout exploré sans trouver de configuration valide
            print('KO')
            sys.exit(0)
        state[ptr] = 2

Deuxième solution

La “vraie” solution à l’exercice 5 n’est pas celle du retour sur trace : En effet, la complexité de l’algorithme précédent n’est pas garantie de passer tous les tests car elle est non-polynomiale. Dans le pire cas imaginable du retour sur trace, on inspecterait tous les états en rencontrant à chaque fois un conflit sur le tout dernier pas, juste avant d’atteindre une solution valide. Comme il y a 2 états pour chaque étudiant et N étudiants au total, le nombre de configurations possibles est de 2ᴺ. Avec une complexité algorithmique O(2ᴺ) on ne peut normalement pas dépasser N=30, mais le retour sur trace nous offre une optimisation très forte (dans la plupart des cas) qui nous permet de dépasser aisément cette limite.

Il existe cependant une solution polynomiale au problème 5 qui n’est pas beaucoup plus difficile à comprendre, mais moins fréquente en compétition que le retour sur trace (je me plains souvent que les Battle Dev ont toujours un exercice de bruteforce avec backtracking).

L’astuce pour cette résolution est plus fine à repérer, car il faut transposer notre problème en autre problème connu dont l’algorithme de résolution est polynomial. Je vais d’abord présenter ce problème qui est connu sous le nom de 2-SAT, et je montrerai ensuite comment on peut réduire notre problème d’intervalles à un problème 2-SAT. Si vous sentez que vous êtes en train de découvrir comment faire le pont entre les deux problèmes avant que j’explique comment faire, n’hésitez pas à mettre la lecture de côté pour quelques minutes et prenez le temps de le poser ! C’est un exercice très intéressant.

Introduction aux problèmes SAT

Les problèmes SAT regroupent tous les problèmes de contraintes sur des variables booléennes. Par exemple, on a quatre variables booléennes a, b, c et d. Il faut trouver un état de nos 4 variables tel que la formule suivante soit valide :

(a ∧ (¬b ∨ c)) ∧ ((¬c ∧ d) ∨ (¬a ∨ b))

  • ∧ indique la conjonction logique (ET)
  • ∨ indique la disjonction non-exclusive (OU)
  • ¬ indique la négation logique (NON)

Cela revient à dire qu’il faut trouver un état des entrées du circuit suivant de telle sorte que la sortie vaille 1 :

img logisim1

La configuration a=1, b=0, c=0, d=1 engendre une sortie à 1, on peut donc dire que la formule est satisfaite dans ce cas.

img logisim2

Le problème SAT se cache derrière un nombre énorme d’applications qui font appel de près ou de loin à la satisfaction de contraintes. Dans sa forme la plus générique, le temps de calcul pour déterminer la satisfaisabilité d’une instance SAT est non-polynomial. Cependant, notre cas précis permet de réduire le problème de choix des intervalles à un cas particulier de SAT : les problèmes 2-SAT. Ceux-ci sont résolvables en temps quadratique = O(n²) (qui est polynomial).

Problème 2-SAT

Pour faire simple, une instance de 2-SAT sera toujours de la forme suivante : (¬a ∨ b) ∧ (c ∨ d) ∧ (¬a ∨ d) ∧ (¬c ∨ ¬d) ∧ (¬b ∨ c)

Un peu de vocabulaire : La formule ci-dessus est présentée dans une forme universelle que l’on appelle Forme Normale Conjonctive. La FNC est un ensemble de sous-formules jointes ensemble par des “ET” logiques. Ces sous-formules sont appelées des clauses, elles sont au nombre de 5 ci-dessus. On trouve aussi des variables positives (a), ou négatives (¬a), qui sont appelées littéraux.

Le “2” des formules 2-SAT vient du fait que leurs clauses comportent au plus 2 littéraux, et c’est ce qui facilite grandement la résolution. À partir de 3 littéraux par clause (3-SAT) le problème redevient NP-Complet, et on peut même prouver que tout problème SAT dans le cas général est équivalent à un 3-SAT.

Pour résoudre une instance de 2-SAT à N variables booléennes, on va d’abord construire un graphe d’équivalences qui nous servira pour la seconde partie de la résolution. Après avoir éliminé les doublons dans les clauses, on a une liste comportant au maximum 4N² clauses qui devront être vérifiées simultanément. Ces clauses peuvent prendre les 4 formes suivantes :

  • (x ∨ y)
  • (¬x ∨ y)
  • (x ∨ ¬y)
  • (¬x ∨ ¬y)

Notre graphe d’implication est un graphe dirigé dont les nœuds sont des littéraux de forme x ou ¬x, et les arêtes correspondent à des implications logiques (“si x est vrai, alors y est vrai”).

On transforme chaque clause en deux arêtes dans le graphe. Prenons par exemple la clause (a ∨ ¬b). Si a est faux, alors il faut obligatoirement que b soit faux pour que la clause soit vraie. On ajoute donc une arête entre le nœud ¬a et le nœud ¬b pour signifier cette relation. Symétriquement, si b est vrai alors a doit être vrai pour vérifier la contrainte. On trace donc une arête entre b et a.

Voici un exemple de graphe d’implication que j’ai emprunté de l’article Wikipédia correspondant :

img implicationgraph

On peut voir sur ce graphe d’implication que ¬x6 implique x5, et à son tour x5 implique x0. En utilisant les propriétés de transitivité de l’implication logique, on peut dire que ¬x6 implique x0.

Vérifier la satisfaisabilité d’un problème 2-SAT revient à vérifier qu’il n’y a aucun littéral tel que x implique ¬x et en même temps ¬x implique x, ce qui donnerait une contradiction. Si aucun des littéraux ne pose de telle contradiction, alors il existera forcément une solution que l’on peut déterminer simplement.

Pour vérifier la satisfaisabilité en pratique, on peut chercher séparément pour chaque littéral x si celui-ci implique ¬x avec un simple parcours de graphe (BFS ou DFS). Ensuite, pour chacun des littéraux x impliquant leur opposé, on détermine avec un autre parcours de graphe si ¬x implique x.

Une fois que la satisfaisabilité des contraintes est vérifiée, on peut se mettre à la recherche d’une configuration des variables qui valide la formule. Pour cela, on choisit n’importe quel littéral - prenons les dans l’ordre, disons qu’on commence par a. On a alors 4 cas de figure :

  • Pas de relation entre a et ¬a : On donne n’importe quelle valeur au littéral a ;
  • a implique ¬a : a sera forcément fausse ;
  • ¬a implique a : a sera forcément vraie ;
  • a implique ¬a et ¬a implique a : Impossible, ce cas a été éliminé à l’étape précédente.

Une fois que l’on a déterminé la valeur que doit prendre la variable a, on va parcourir le graphe d’implication en partant de a ou ¬a (en fonction de la valeur choisie), ce qui va déterminer toutes les autres valeurs que l’on va forcer. En reprenant l’exemple de graphe d’implication ci-dessus, forcer ¬x0 revient à aussi forcer ¬x3, ¬x5 et x6.

Quand on a fini de parcourir le graphe d’implication et de forcer les valeurs de tous les littéraux sur notre passage, on recommence avec un autre littéral dont la valeur n’est pas forcée. On procède itérativement jusqu’à avoir déterminé les valeurs de tous les littéraux. Je ne m’attarderai pas à fournir une preuve - il y a beaucoup de littérature qui expliquerait ça mieux que moi - mais cette méthode marche nécessairement si la formule 2-SAT est satisfaisable.

Réduction du problème à un 2-SAT

On dispose maintenant de tous les éléments nécessaires pour proposer une solution efficace au problème 5 du Battle Dev. C’est maintenant votre dernière chance si vous souhaitez trouver la solution par vous-mêmes avant que je la présente, n’hésitez pas à mettre la lecture de côté !

Chaque étudiant sera représenté par une variable, prenons e0, e1, e2, etc. pour faire simple. Le créneau de gauche de l’étudiant 0 sera représenté par ¬e0, et le créneau de droite sera e0. Ensuite, on cherchera pour chaque créneau horaire les autres créneaux horaires d’autres étudiants qui sont incompatibles.

img creneaux

On aura par exemple ici une incompatibilité entre ¬e0 et ¬e1. On retrouve ici un problème SAT pour résumer toutes les collisions dans l’emploi du temps, dont les clauses seraient de la forme ¬ (¬e0 ∧ ¬e1) pour signifier que les variables e0 et e1 ne peuvent pas être fausses simultanément.

Notre problème s’apparente donc à un 2-SAT car les clauses comportent 2 littéraux, mais la Forme Normale Conjonctive interdit les clauses de forme ¬ (¬e0 ∧ ¬e1). Pour se mettre dans les règles de la FNC, il faut absolument des clauses (littéral1 ∨ littéral2).

Heureusement, les lois de De Morgan nous permettent de transformer nos clauses pour les rendre valides en regard de la FNC : ¬(x ∧ y) est strictement équivalent à (¬x ∨ ¬y), ce qui nous donne donc une formule 2-SAT valide.

La formule qui correspond à l’exemple est (e0 ∨ e1) ∧ (e0 ∨ e2) ∧ (e0 ∨ e3) ∧ (¬e0 ∨ ¬e1) ∧ (¬e0 ∨ ¬e2) ∧ (e1 ∨ e3) ∧ (e1 ∨ ¬e3) ∧ (¬e1 ∨ ¬e2)

À partir de ces 8 clauses, on peut donc former le graphe d’implication qui comportera 16 arêtes :

img implicationgraph2

Il ne reste qu’à résoudre le 2-SAT à partir de ce graphe d’implication :

import sys

#Renvoie l'ensemble des noeuds atteignables depuis un noeud donné
def dfs(graph, node):
    visited = set()
    queue = [node]
    while len(queue):
        curr = queue.pop()
        if curr in visited: continue
        visited.add(curr)
        for nxt in graph[curr]:
            if nxt not in visited:
                queue.append(nxt)
    return visited


N=int(input())

intervals = []
for i in range(N):
    a, b = map(int, input().split())
    intervals.append((a,b))

#On détermine le graphe d'implication
graph = [set() for i in range(2*N)]
for first in range(N):
    for second in range(first):
        for firstpos in (0,1):
            for secondpos in (0,1):
                if abs(intervals[first][firstpos] - intervals[second][secondpos]) <= 60:
                    graph[first + N*firstpos].add(second + N * (1-secondpos))
                    graph[second + N*secondpos].add(first + N * (1-firstpos))

# On cherche toutes les variables qui ont not(i)->i dans le graphe
risky = set()
for i in range(N):
    if i+N in dfs(graph, i):
        risky.add(i)

#Parmi les variables not(i)->i, on cherches celles qui ont aussi i->not(i)
for j in risky:
    if j in dfs(graph, j+N):
        # Ici on a not(i)->i->not(i), la formule 2-SAT est contradictoire.
        print('KO')
        sys.exit(0)

# Aucune contradiction trouvée, la formule est satisfaisable.
state = [0 for i in range(N)]

for i in range(N):
    if state[i] :  # L'état de cette variable est déjà déterminé, on passe à la suivante
        continue
    
    # Si not(i)->i on doit prendre i positif, sinon on peut le prendre négatif
    startnode = N+i if i in risky else i
    for res in dfs(graph, startnode):
        if res < N:
            state[res] = 1
        else:
            state[res - N] = 2

for x in state:
    print(x)

C’est la fin de cet article, n’hésitez pas à me suivre sur Twitter pour être informé de mes nouvelles publications !

Written on November 3, 2018
Follow us on Twitter to be informed about new posts !