Compor solução linha maior de soma de dois algoritmo optimalization variedade dimensional

votos
2

Suponhamos que temos uma matriz bidimensional (linhas n, m colunas), em que cada coluna tenha, pelo menos, uma célula não vazia com valor inteiro:

Dados

Podemos facilmente compor uma nova linha único, em que cada célula contém o maior valor tomado de acordo coluna na matriz de dados.

A solução (comprimento M) não pode ter valores de vazios.

Neste caso, a solução seria:

Solução

Não há um único fator: maior valor para cada coluna.

Queremos adicionar um outro fator: menor quantidade de linhas a partir do qual a solução está sendo compostas a partir de ( mais importante do que o valor da soma).

O algoritmo mais simples para isso seria da seguinte forma:

i = 1

while (i <= M)
{
    candidates = generateCorrectSolutionsFromAllNLengthRowCombinations(i)

    if ( ! empty(candidates))
    {
        return biggestSumElement(candidates)
    }

    i++
}

Este algoritmo retorna solução correta, mas tem muito alta complexidade computacionalmente que é problemático para matrizes maiores.

Existe uma maneira de fazê-lo mais rápido? Foi este problema (ou um semelhante) analisaram em qualquer lugar?

Saudações,

Patryk

Publicado 03/03/2016 em 12:06
fonte usuário
Em outras línguas...                            


1 respostas

votos
0

Se você está encontrando valores em série não ordenada, você nunca sabe, se o valor que você está procurando é no último campo visitou desse array, pois a complexidade de matriz de comprimento N é O (N) e não pode ser menor.

A única maneira de como tornar a busca mais rápida é ter conjunto ordenado de alguma forma, ou para conhecer alguns padrões e com base em que pular alguma parte da matriz, porque temos a certeza, a solução não está lá.

Respondeu 03/03/2016 em 12:46
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more