Problema do Ordenamento Linear

[Duffy]

Boas pessoal trabalhador  👍

Bem tenho um trabalhito para fazer para uma cadeira com este enunciado:

Dada uma matriz quadrada N×N pretende-se encontrar um reordenamento das linhas

e colunas de tal forma que a soma dos valores do triângulo superior da matriz seja a

mais elevada possível. Este reordenamento é especificado através de uma permutação

π dos índices das linhas e das colunas {1, ..., N}, indicando a ordem pela qual estas

devem ser consideradas.

Obvio que não venho pedir para me fazerem o trabalho  😛 mas estou um bocado na dúvida de qual a heuristica a utilizar para este tipo de problemas e queria umas opiniões, e se alguém tiver conhecimentos de alguns sites ou pdf's relevantes também agradecia.

Obrigado 🙂

[Warrior]

Eu criaria outra matriz, NxN, onde guardaria: (vou começar a matriz na posição 1 para simplificação)

m[1][1] = Elemento central da primeira linha

m[1][2] = Soma dos dois elementos centrais da primeira linha

m[2][1] = Elemento central da segunda linha

m[2][5] = Soma dos cinco elementos centrais da segunda linha, etc.

O que faria a seguir dependeria dos limites do enunciado, e se a matriz pode ou não conter elementos negativos.

Se a matriz tiver um máximo de... 10x10 utilizaria permutações (se não me engano permutações de 10 elementos demoram ligeiramente menos de um segundo a calcular)

Caso contrário, julgo que exista uma solução que envolva Programação Dinâmica para esse problema, mas não tenho a certeza. Foi isso que o meu instinto me disse mas não estou a ver qual é.

[Duffy]

Ora não é nada mal pensado não, vou experimentar isso, o limite é de 80 linhas por 80 colunas  😛 obrigado pela dica  👍

[Warrior]

80 linhas por 80 colunas não podes fazer permutações, fica demasiado lento.

Estou-me a lembrar de várias alternativas, mas todas elas me parecem falíveis:

Greedy: Procurar a que tem maior valor para o maximo, depois a que tem maior valor para n-1, etc.

Value/Size: Ordenar todas as alternativas num vector com a relação Valor/Tamanho. Ou seja, 2 valores do meio: 5 7, 12/2 = 6; 1 Valor: 9 -> 9/1 = 9. Simplesmente aproveitar os maiores de cada género.

Ordenação: Aplicar um quick/bubble sort, com um parametro de comparação mais rabuscado, terias que ordenar apontadores etc..