O algoritmo implementado pelo git bisect é ideal?

Seja um DAG. Sabemos que alguns nós em são "ruins", enquanto outros são "bons"; um descendente de um nó ruim é ruim enquanto os ancestrais de um nó bom são bons. Também sabemos que nós ruins têm um elemento mínimo exclusivo em que gostaríamos de encontrar consultando o menor número possível de nós com consultas do tipo "Você é bom ou ruim?".$G$$G$$G$

Esse problema foi resolvido no Git, o popular sistema de controle de versão, pelo comando git-bisect, que ajuda um programador a encontrar o primeiro commit no qual um bug foi introduzido.

No início, o algoritmo implementado pelo Git pressupõe conhecer um único commit incorreto e um ou mais commits válidos. Em cada etapa de sua execução, o algoritmo localiza uma confirmação usando as seguintes etapas (extraídas daqui ):

1. Mantenha apenas as confirmações que:

   a) são um ancestral do commit incorreto (incluindo o próprio commit incorreto) e

   b) não são ancestrais de um bom commit (excluindo o bom commit).

2. A partir das extremidades boas do gráfico resultante, associe a cada confirmação o número de ancestrais que possui mais um.

3. Associar a cada confirmação $\min(X, N-X)$, em que $X$ é o valor associado à confirmação na etapa 2 e $N$ é o número total de confirmações no gráfico (depois que foi reduzido na etapa 1).

4. O melhor ponto de bissecção é o commit com o maior número associado.

Esse algoritmo está essencialmente encontrando a confirmação que alcança o "pior melhor caso": na verdade, é o número de nós no DAG na próxima iteração no melhor caso, portanto é o pior caso.$\min(X,N-X)$$\max\min(X,N-X)$

Eu estou pensando:

• Faz alguma diferença se selecionarmos o "melhor pior caso", ou seja, o nó que atinge ?$\min\max(X,N-X)$
• Esse algoritmo é o pior caso ideal?

Edição: notei que este problema tem um ligado. Considere o DAG formado por um único nó com pais chamado . Se sabemos que é ruim, temos que verificar cada um dos pais para ver se eles são o nó ruim mínimo.$\Omega(N)$$b$$N-1$$g_1,\dots,g_{N-1}$$b$

EDIT 2: O anterior é realmente um ligado, onde é a largura do poset. Um algoritmo alternativo para esse problema é fornecido nesta resposta em cstheory.stackexchange que usa consultas .$\Omega(w)$$w$$O(w\log{n})$

Aqui está uma intuição para o que e estão fazendo. Concentre-se em um commit específico . Suponha que testemos e o classifiquemos como "bom" ou "ruim". Até testá-lo, não sabemos se é bom ou ruim, mas podemos prever com antecedência quanto menor o gráfico ficará em cada um desses dois casos. Em particular, é o número de confirmações que seriam eliminadas se a confirmação for boa e é o número de confirmações que seriam eliminadas se a confirmação for ruim.$X$$N$$c$$c$$X$$c$$N-X$$c$

Portanto, o valor é um limite inferior para o número de confirmações que poderemos cortar na próxima etapa, independentemente do resultado do teste. A idéia do algoritmo Git é maximizar essa métrica. Em outras palavras, o Git escolhe um limite o maior possível e um commit para testar a seguir, para que o Git possa ter certeza de que será capaz de cortar pelo menos commit no próximo passo.$\min(X,N-X)$$t$$c$$t$

Se não tivermos informações sobre se é provável que cada commit seja bom ou ruim, é igualmente provável que seja bom ou ruim, então isso parece uma escolha local ideal. Assim, o algoritmo Git é um algoritmo ganancioso.

O algoritmo Git é globalmente ideal? Isso dependerá da definição de "ideal" e (provavelmente) da distribuição dos DAGs encontrados na prática. Provavelmente, não existe uma caracterização simples da distribuição de probabilidade nos DAGs encontrados na prática, portanto, espero que seja difícil encontrar um resultado de otimização para esse problema.