O problema de partição de números consiste em: dado um conjunto de N números, o objetivo é subdividi-lo em dois subconjuntos (chamados de partições) de tal forma que, a diferença entre os valores das somas dos números dessas duas partições seja a menor possível. Por exemplo, considere o seguinte conjunto com quatro números (23, 20, 56, 48). As partições (20,56) e (23,48) consistem no particionamento ótimo para este conjunto e, seu valor é 5. Apesar da simplicidade do enunciado, este é um problema de otimização combinatória que pertence à classe NP-difícil. Observe que, para um conjunto com N números têm-se 2N possíveis maneiras de subdividi-lo em duas partições.
Nosso problema consiste em dado uma seqüência [10,20,30,11,25,23,32,9,7,19,17,31,48,27,5,21,35,13,38,16,14,33,5] devemos criar um vetor de sinais (- ou +) para cada numero disposto, de modo a alcançarmos o menor valor (tendendo a 0) considerando o módulo do resultado das operações realizadas.
EX: para o vetor [10,20,30,11] geramos um vetor [1,1,0,0] considerei para esse exemplo que um representa + e 0 representa -, sendo assim nosso vetor seria [+,+,-,-]. O que geraria +10+20-30-11, resultando no valor 11, considerando seu módulo.
Entendido esse conceito vamos ao código.
Criaremos uma classe chamada Individuo com dois atributos @code e @value que recebem respectivamente o código binário (que representa os sinais) e o valor da função objetivo (ou em nosso caso o resultado da sentença) daquele individuo em questão.
Read the rest of this entry »
1