Python - Dividir e conquistar

Na abordagem dividir para conquistar, o problema em questão é dividido em subproblemas menores e cada problema é resolvido independentemente. Quando continuamos dividindo os subproblemas em subproblemas ainda menores, podemos eventualmente atingir um estágio em que nenhuma divisão mais é possível. Esses menores subproblemas "atômicos" possíveis (frações) são resolvidos. A solução de todos os subproblemas é finalmente combinada para obter a solução de um problema original.

Em termos gerais, podemos entender divide-and-conquer abordagem em um processo de três etapas.

Divide / Break

Esta etapa envolve dividir o problema em subproblemas menores. Os subproblemas devem representar uma parte do problema original. Essa etapa geralmente usa uma abordagem recursiva para dividir o problema até que nenhum subproblema seja mais divisível. Nesse estágio, os subproblemas tornam-se atômicos por natureza, mas ainda representam uma parte do problema real.

Conquistar / Resolver

Esta etapa recebe muitos subproblemas menores a serem resolvidos. Geralmente, neste nível, os problemas são considerados 'resolvidos' por conta própria.

Unir / Combinar

Quando os subproblemas menores são resolvidos, esse estágio os combina recursivamente até que formem uma solução para o problema original. Esta abordagem algorítmica funciona recursivamente e as etapas de conquista e mesclagem funcionam tão próximas que aparecem como uma só.

Exemplos

O programa a seguir é um exemplo de divide-and-conquer abordagem de programação onde a busca binária é implementada usando python.

Implementação de pesquisa binária

Na pesquisa binária, pegamos uma lista ordenada de elementos e começamos a procurar um elemento no meio da lista. Se o valor da pesquisa corresponder ao valor do meio na lista, concluímos a pesquisa. Caso contrário, eliminamos metade da lista de elementos escolhendo se procede com a metade direita ou esquerda da lista, dependendo do valor do item pesquisado. Isso é possível porque a lista é classificada e é muito mais rápida do que a pesquisa linear. Aqui, dividimos a lista fornecida e conquistamos escolhendo a metade adequada da lista. Repetimos essa abordagem até encontrar o elemento ou concluir sobre sua ausência na lista.

def bsearch(list, val):

    list_size = len(list) - 1

    idx0 = 0
    idxn = list_size
# Find the middle most value

    while idx0 <= idxn:
        midval = (idx0 + idxn)// 2

        if list[midval] == val:
            return midval
# Compare the value the middle most value
        if val > list[midval]:
            idx0 = midval + 1
        else:
            idxn = midval - 1

    if idx0 > idxn:
        return None
# Initialize the sorted list
list = [2,7,19,34,53,72]

# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))

Quando o código acima é executado, ele produz o seguinte resultado:

5
None