Ist der von git bisect implementierte Algorithmus optimal?

Sei eine DAG. Wir wissen, dass einige Knoten in G "schlecht" sind, während die anderen "gut" sind; Ein Nachkomme eines schlechten Knotens ist schlecht, während die Vorfahren eines guten Knotens gut sind. Wir wissen auch, dass fehlerhafte Knoten ein eindeutiges minimales Element enthalten$G$$G$ das wir mit Abfragen vom Typ "Sind Sie gut oder schlecht?" So wenige Knoten wie möglich abfragen möchten.$G$

Dieses Problem wird in Git, dem beliebten Versionskontrollsystem, durch den Befehl gelöst git-bisect, der einem Programmierer hilft, das erste Commit zu finden, bei dem ein Fehler aufgetreten ist.

Zu Beginn geht der von Git implementierte Algorithmus davon aus, dass ein einzelnes schlechtes Commit und ein oder mehrere gute Commits bekannt sind. Bei jedem Schritt seiner Ausführung findet der Algorithmus ein Commit unter Verwendung der folgenden Schritte (entnommen aus hier aus ):

1. Behalten Sie nur die Commits bei, die:

   ein) ein Vorfahr des schlechten Commits sind (einschließlich des schlechten Commits selbst), und

   b) keine Vorfahren eines guten Commits sind (mit Ausnahme der guten Commits).

2. Ordnen Sie jedem Commit ausgehend von den guten Enden des resultierenden Diagramms die Anzahl der Vorfahren plus eins zu.

3. Ordnen Sie jedem Commit , wobei X der Wert ist, der dem Commit in Schritt 2 zugeordnet ist, und $\min(X, N-X)$$X$$N$ die Gesamtzahl der Commits im Diagramm ist (nachdem es in Schritt 1 reduziert wurde).

4. Der beste Halbierungspunkt ist das Commit mit der höchsten zugeordneten Zahl.

Dieser Algorithmus findet im Wesentlichen das Commit, das den "schlechtesten besten Fall" erzielt: Tatsächlich ist die Anzahl der Knoten in der DAG bei der nächsten Iteration im besten Fall, also max min ( X , N - X ) ist der schlechteste beste Fall.$\min(X,N-X)$$\max\min(X,N-X)$

Ich frage mich:

• Macht es einen Unterschied, ob wir den "besten schlechtesten Fall" auswählen, dh den Knoten, der ?$\min\max(X,N-X)$
• Ist dieser Algorithmus im schlimmsten Fall optimal?

EDIT: Ich habe festgestellt, dass dieses Problem eine -Bindung hat. Betrachten Sie die DAG, die von einem einzelnen Knoten b mit N - 1 Eltern gebildet wird, die als g 1 , … , g N - 1 bezeichnet werden . Wenn wir das wissen $\Omega(N)$$b$$N-1$$g_1,\dots,g_{N-1}$$b$ schlecht ist, müssen wir alle Eltern überprüfen, um festzustellen, ob sie der minimale schlechte Knoten sind.

EDIT 2: Das vorherige ist tatsächlich eine -Bindung , wobei w die Breite des Posets ist. Ein alternativer Algorithmus für dieses Problem ist in dieser Antwort auf cstheory.stackexchange angegeben, der O- Abfragen ( w log n ) verwendet .$\Omega(w)$$w$$O(w\log{n})$

$X$$N$$c$$c$$X$$c$$N-X$$c$

$\min(X,N-X)$ist eine Untergrenze für die Anzahl der Commits, die wir im nächsten Schritt entfernen können, unabhängig davon, wie der Test ausgeht. Die Idee des Git-Algorithmus ist es, diese Metrik zu maximieren. Mit anderen Worten, Git wählt einen Schwellenwert$t$ das ist so groß wie möglich und ein Commit $c$ als nächstes zu testen, so dass Git sicher sein kann, dass es zumindest wegschneiden kann $t$ legt im nächsten Schritt fest.

Wenn wir keine Informationen darüber haben, ob jedes Commit wahrscheinlich gut oder schlecht ausfällt, und es ebenso wahrscheinlich ist, dass es gut oder schlecht ist, dann scheint dies eine lokal optimale Wahl zu sein. Somit ist der Git-Algorithmus ein gieriger Algorithmus.

Ist der Git-Algorithmus global optimal? Dies hängt von der Definition von "optimal" und (wahrscheinlich) von der Verteilung der DAGs ab, auf die man in der Praxis stößt. Wahrscheinlich gibt es keine einfache Charakterisierung der Wahrscheinlichkeitsverteilung auf DAGs, auf die man in der Praxis stößt, daher würde ich erwarten, dass es wahrscheinlich schwierig sein wird, ein Optimalitätsergebnis für dieses Problem zu finden.