¿El algoritmo implementado por git bisect es óptimo?

Dejar $G$ser un DAG Sabemos que algunos nodos en son "malos", mientras que otros son "buenos"; un descendiente de un nodo malo es malo mientras que los antepasados ​​de un nodo bueno son buenos. También sabemos que los nodos defectuosos tienen un elemento mínimo único en que nos gustaría encontrar consultando la menor cantidad posible de nodos con consultas del tipo "¿Eres bueno o malo?".$G$$G$

Este problema se resuelve en Git, el popular sistema de control de versiones, mediante el comando git-bisect, que ayuda al programador a encontrar la primera confirmación en la que se introdujo un error.

Al principio, el algoritmo implementado por Git supone conocer una única confirmación errónea y una o más confirmaciones válidas. En cada paso de su ejecución, el algoritmo encuentra una confirmación utilizando los siguientes pasos (tomados de aquí ):

1. Mantenga solo las confirmaciones que:

   a) son un antepasado del mal compromiso (incluido el mal compromiso en sí), y

   b) no son ancestros de un buen compromiso (excluyendo los buenos compromisos).

2. A partir de los buenos extremos del gráfico resultante, asocie a cada compromiso el número de antepasados ​​que tiene más uno.

3. Asociado a cada compromiso $\min(X, N-X)$, donde es el valor asociado a la confirmación en el paso 2, y es el número total de confirmaciones en el gráfico (después de que se redujo en el paso 1).$X$$N$

4. El mejor punto de bisección es el commit con el número más alto asociado.

Este algoritmo es esencialmente encontrar el compromiso que logra el "peor de los casos": de hecho, es el número de nodos en el DAG en la próxima iteración en el mejor de los casos, por lo tanto, es el peor de los casos.$\min(X,N-X)$$\max\min(X,N-X)$

Me pregunto:

• ¿Hay alguna diferencia si seleccionamos el "mejor peor de los casos", es decir, el nodo que logra ?$\min\max(X,N-X)$
• ¿Es este algoritmo el peor de los casos óptimo?

EDITAR: He notado que este problema tiene un límite de . Considere el DAG formado por un solo nodo con padres llamados . Si sabemos que es malo, entonces tenemos que verificar a cada uno de los padres para ver si son el nodo malo mínimo.$\Omega(N)$$b$$N-1$$g_1,\dots,g_{N-1}$$b$

EDIT 2: El anterior es en realidad un límite de , donde es el ancho del poset. En esta respuesta se proporciona un algoritmo alternativo para este problema en cstheory.stackexchange que usa consultas .$\Omega(w)$$w$$O(w\log{n})$

Aquí hay una intuición de lo que y están haciendo. Centrarse en un compromiso particular . Supongamos que probamos y lo clasificamos como "bueno" o "malo". Hasta que lo probamos, no sabemos si es bueno o malo, pero podemos predecir de antemano cuánto más pequeño será el gráfico en cada uno de esos dos casos. En particular, es el número de confirmaciones que se recortarían si la confirmación resulta ser buena, y es la cantidad de confirmaciones que se recortarían si la confirmación resulta ser mala.$X$$N$$c$$c$$X$$c$$N-X$$c$

Por lo tanto, el valor es un límite inferior en el número de confirmaciones que podremos recortar en el siguiente paso, sin importar cómo resulte la prueba. La idea del algoritmo Git es maximizar esta métrica. En otras palabras, Git elige un umbral que es lo más grande posible, y un commit para probar a continuación, de modo que Git pueda estar seguro de que podrá recortar al menos commits en el siguiente paso.$\min(X,N-X)$$t$$c$$t$

Si no tenemos información sobre si es probable que cada commit resulte bueno o malo, por lo que es igualmente probable que sea bueno o malo, entonces esto parece una opción óptima a nivel local. Por lo tanto, el algoritmo Git es un algoritmo codicioso.

¿Es el algoritmo Git globalmente óptimo? Eso dependerá de la definición de "óptimo" y (probablemente) de la distribución de DAG que uno encuentre en la práctica. Probablemente no hay una caracterización simple de la distribución de probabilidad en los DAG que uno encuentra en la práctica, por lo que esperaría que sea difícil encontrar un resultado óptimo para este problema.