L'algorithme implémenté par git bisect est-il optimal?

Soit un DAG. Nous savons que certains nœuds de sont "mauvais", tandis que les autres sont "bons"; un descendant d'un mauvais nœud est mauvais tandis que les ancêtres d'un bon nœud sont bons. Nous savons également que les mauvais nœuds ont un élément minimal unique en que nous aimerions trouver interroger le moins de nœuds possible avec des requêtes du type "Êtes-vous bon ou mauvais?".$G$$G$$G$

Ce problème est résolu dans Git, le système de contrôle de version populaire, par la commande git-bisect, qui aide un programmeur à trouver le premier commit dans lequel un bogue a été introduit.

Au début, l'algorithme implémenté par Git suppose de connaître un seul mauvais commit et un ou plusieurs bons commits. À chaque étape de son exécution, l'algorithme trouve une validation en utilisant les étapes suivantes (prises à partir d' ici ):

1. Ne conservez que les engagements qui:

   a) sont l'ancêtre du mauvais commit (y compris le mauvais commit lui-même), et

   b) ne sont pas l'ancêtre d'un bon commit (à l'exclusion des bons commits).

2. En partant des bonnes extrémités du graphique résultant, associez à chaque commit le nombre d'ancêtres qu'il a plus un.

3. Associer à chaque validation , où X est la valeur associée à la validation à l'étape 2 et N est le nombre total de validations dans le graphique (après avoir été réduit à l'étape 1).$\min(X, N-X)$$X$$N$

4. Le meilleur point de bissection est la validation avec le plus grand nombre associé.

Cet algorithme trouve essentiellement le commit qui atteint le "pire des cas": en fait, est le nombre de nœuds dans le DAG à la prochaine itération dans le meilleur des cas, donc est le pire des cas.$\min(X,N-X)$$\max\min(X,N-X)$

Je me demande:

• Cela fait-il une différence si nous sélectionnons le "meilleur pire cas", c'est-à-dire le nœud qui atteint ?$\min\max(X,N-X)$
• Cet algorithme dans le pire des cas est-il optimal?

EDIT: J'ai remarqué que ce problème a un lié. Considérons le DAG formé par un seul nœud avec parents appelé . Si nous savons que est mauvais, nous devons vérifier chacun des parents pour voir s'ils sont le mauvais nœud minimal.$\Omega(N)$$b$$N-1$$g_1,\dots,g_{N-1}$$b$

EDIT 2: Le précédent est en fait une borne , où est la largeur du poset. Un algorithme alternatif pour ce problème est donné dans cette réponse sur cstheory.stackexchange qui utilise des requêtes .$\Omega(w)$$w$$O(w\log{n})$

Voici quelques intuition pour ce que et font. Se concentrer sur un engagement particulier . Supposons que nous testons et le classions comme «bon» ou «mauvais». Jusqu'à ce que nous le testions, nous ne savons pas s'il est bon ou mauvais, mais nous pouvons prédire à l'avance à quel point le graphique deviendra plus petit dans chacun de ces deux cas. En particulier, est le nombre de validations qui seraient supprimées si la validation se révélait bonne, et était le nombre de validations qui seraient supprimées si la validation se révélait mauvaise.$X$$N$$c$$c$$X$$c$$N-X$$c$

Par conséquent, la valeur est une limite inférieure du nombre de validations que nous pourrons supprimer à l'étape suivante, quelle que soit l'issue du test. L'idée de l'algorithme Git est de maximiser cette métrique. En d'autres termes, Git choisit un seuil qui est aussi grand que possible et un commit pour tester ensuite, de sorte que Git peut être sûr qu'il sera en mesure de supprimer au moins commits à l'étape suivante.$\min(X,N-X)$$t$$c$$t$

Si nous ne savons pas si chaque validation est susceptible de se révéler bonne ou mauvaise, il est donc tout aussi probable qu'elle soit bonne ou mauvaise, cela ressemble à un choix localement optimal. Ainsi, l'algorithme Git est un algorithme gourmand.

L'algorithme Git est-il globalement optimal? Cela dépendra de la définition de "optimal" et (probablement) de la distribution des DAG que l'on rencontre dans la pratique. Il n'y a probablement pas de caractérisation simple de la distribution de probabilité sur les DAG que l'on rencontre dans la pratique, donc je m'attends à ce qu'il soit probablement difficile de trouver un résultat d'optimalité pour ce problème.