Encontrando a melhor combinação de conjuntos que fornece o número máximo de itens exclusivos

5

Um par de meses atrás eu fui a um show de Bruce Springsteen. Eu não tinha ouvido muitas de suas músicas antes disso, mas realmente gostei do show e comprei a gravação ao vivo dele depois (que ele vende via live.brucespringsteen. net ). Um pouco mais tarde até comprei outra gravação ao vivo de um concerto diferente e depois de ouvi-las repetidamente, estou gostando cada vez mais de sua música. Eu gosto tanto disso que eu quero comprar mais de suas gravações ao vivo ... e é aí que eu corri para o meu problema: ele tem muitas gravações!

Agora, como desenvolvedor, quero escrever um código que me dê o número mínimo / ótimo de gravações para comprar, o que me dará um número máximo de músicas diferentes com o mínimo de duplicatas (levando em conta as duas gravações Eu já tenho).

Eu poderia usar a força bruta, é claro, mas espero que haja algum algoritmo ou biblioteca que possa me ajudar a determinar o conjunto correto de gravações a serem compradas? Raspagem das listas de conjuntos do site é a parte fácil.

Já tentei pesquisar algoritmos e parece que pode ser algum tipo de Problema de conjunto de capas , que faria NP-completo, o que é um problema, mas eu não estou procurando uma combinação que me dê todas as músicas diferentes, apenas quais x gravações para comprar adicionalmente para obter a melhor quantidade de diferentes músicas no total (comprimento da música não importa).

Esclarecimento : como o Dr. Brown aponta, eu preciso ser ainda mais específico. Gostaria de saber quais gravações comprar que me dão mais, mas não todas, músicas, com um máximo fixo de duplicatas.

Possibilidade? Depois de pensar um pouco mais sobre isso, estou começando a me perguntar se talvez a Programação Genética possa ser aplicada a isso? Você poderia começar com uma população de indivíduos gerados aleatoriamente (combinações de gravações) e, em seguida, aplicar uma função de adequação que forneça uma pontuação com base na quantidade de músicas únicas, duplicatas & total de gravações necessárias. Depois de gerações suficientes, isso também poderia dar uma boa aproximação?

    
por fimez 02.08.2016 / 11:08
fonte

4 respostas

3

Você pode usar algoritmos genéticos com uma representação binária simples para os indivíduos:

individual = 01010100000111000011010111001110

Cada locus de um indivíduo está relacionado às gravações de um show específico. Se:

individual[k] == 1

você comprará o álbum k-th .

Você deve codificar duas / três funções:

unique_songs(individual) = number of unique songs

duplicates(individual) = number of duplicates

cost(individual) = total purchase cost

A função de fitness é algo como:

fitness(individual) =        unique_songs(individual)
                      - k1 *   duplicates(individual)
                      - k2 *         cost(individual)

k1 / k2 precisa ser ajustado. Isso tratará duplicates(individual) como restrição soft .

Se você quiser o máximo de músicas possível com um número máximo fixo de duplicatas ( limit ) você precisa de uma restrição difícil . A abordagem mais simples é mudar a adequação de um valor escalar para um vetor bidimensional:

fitness(individual) = [-penalty(individual),
                       unique_songs(individual) - k * cost(individual)]


                       / duplicates(individual) - limit   constraint not satisfied
penalty(individual) = {
                       \ 0                                otherwise

Para mais detalhes sobre essa abordagem, você pode ler Um método eficiente de manipulação de restrições para algoritmos genéticos - Kalyanmoy Deb.

Você pode usar a mesma biblioteca / estrutura, basta alterar o operador de comparação de adequação para uma função comparação lexicográfica .

    
por 02.08.2016 / 16:22
fonte
0

O recozimento simulado é uma técnica útil para gerar resultados aproximados para problemas computacionalmente difíceis, em que é fácil determinar se uma solução potencial é melhor que outra.

Na sua forma mais simples, você escolhe uma solução aleatória e gera uma pequena alteração (por exemplo, trocando uma gravação por outra) e vê se isso o aproximou de seu resultado. Se tiver, você mantém a nova solução e repete. Se não, você tem uma chance aleatória de aceitar a mudança de qualquer maneira. O processo é governado por uma variável "temperatura" que diminui à medida que você se aproxima do seu limite de iteração; a chance de aceitar uma mudança menos ideal reduz à medida que a temperatura diminui. Além de rastrear a solução atual, você também acompanha a melhor solução de sempre.

Para muitos tipos de problemas, essa abordagem geralmente converge para uma aproximação razoável da melhor solução.

    
por 02.08.2016 / 19:43
fonte
0

Se você tiver um limite para o número de álbuns que deseja comprar e esse número não for grande, acho que há uma abordagem bastante simples. Primeiro você quer criar uma função distância entre um conjunto e outro. No nível mais simples, é a contagem de músicas que não estão nos dois conjuntos. Você diz que quer limitar o número de duplicatas, mas eu questiono isso, uma vez que também pode limitar o número de músicas diferentes que você acaba. Por exemplo, se uma gravação tiver todas as novas músicas, exceto uma que você já tenha várias vezes, você a rejeitaria e possivelmente escolheria um álbum com poucas músicas novas. Dado o artista, imagino que algumas músicas (por exemplo, "Born in the USA", "Born to Run", "Born ...") vão aparecer com muita frequência, se não em todas as gravações.

Depois de ter esse cálculo. Você pega suas duas gravações e as combina em um conjunto. Calcule a distância desse conjunto e todas as outras gravações. Então pegue esses conjuntos e repita até chegar ao número máximo de gravações que você está disposto a comprar.

Isso pode ser muito caro se você estiver disposto a comprar muitas gravações e não tenho certeza de quantas são, mas parece um monte. Se isso levar muito tempo, você poderá selecionar os conjuntos iniciais com base na pontuação de cada iteração. Não é garantido que você obterá o melhor resultado dessa forma, mas é provável que seja bem próximo.

Veja um exemplo para demonstrar por que você pode não querer definir um limite rígido para duplicatas:

Digamos que seu conjunto inicial seja:

Apple
Banana
Carrot
Durian

E você tem os 4 conjuntos a seguir para escolher.

Apple       Apple        Banana  Carrot
Escarole    Horseradish  Durian  Escarole
Fig         Jalapeno        
Grapefruit  Kale        
            Lemon       

E você deseja selecionar os dois melhores conjuntos desses quatro para adicionar ao seu conjunto. Aqui estão as 6 opções:

 1 & 2          1 & 3     1 & 4
Apple       3  Apple  2  Apple    2
Banana      1  Banana 2  Banana   2
Carrot      1  Carrot 1  Carrot   2
Durian      1  Durian 2  Durian   1
Escarole    1            Escarole 1
Fig         1           
Grapefruit  1           
Horseradish 1           
Jalapeno    1           
Kale        1           
Lemon       1           

 2 & 3          2 & 4          3 & 4    
Apple       2  Apple       2  Apple    1
Banana      2  Banana      1  Banana   2
Carrot      1  Carrot      2  Carrot   2
Durian      2  Durian      1  Durian   2
Horseradish 1  Horseradish 1  Escarole 1
Jalapeno    1  Jalapeno    1        
Kale        1  Kale        1        
Lemon       1  Lemon       1        
               Escarole    1        

Agora, digamos que você começou com a regra de que nenhum item poderia ser repetido mais de duas vezes. Isso excluiria a opção de 1 & 2. Eu diria que exclui a melhor opção, pois fornece o maior número de itens exclusivos.

Obviamente, este é um exemplo artificial, mas à medida que você recebe muitos conjuntos em que os mesmos valores aparecem com frequência, essa situação se torna mais provável.

    
por 02.08.2016 / 20:09
fonte
0

Isso parece uma variação do problema da mochila para mim. Resolvi o problema com a biblioteca do GA Jenetics :

import static java.util.Objects.requireNonNull;

import java.util.function.Function;
import java.util.stream.Collectors;

import org.jenetics.BitGene;
import org.jenetics.engine.Codec;
import org.jenetics.engine.Engine;
import org.jenetics.engine.EvolutionResult;
import org.jenetics.engine.Problem;
import org.jenetics.engine.codecs;
import org.jenetics.util.ISeq;

public class Springsteen
    implements Problem<ISeq<Springsteen.Record>, BitGene, Double>
{

    public static final class Record {
        final String name;
        final double price;
        final ISeq<String> songs;

        public Record(
            final String name,
            final double price,
            final ISeq<String> songs
        ) {
            this.name = requireNonNull(name);
            this.price = price;
            this.songs = requireNonNull(songs);
        }
    }

    private final ISeq<Record> _records;
    private final double _maxPricePerUniqueSong;

    public Springsteen(final ISeq<Record> records, final double maxPricePerUniqueSong) {
        _records = requireNonNull(records);
        _maxPricePerUniqueSong = maxPricePerUniqueSong;
    }

    @Override
    public Function<ISeq<Record>, Double> fitness() {
        return records -> {
            final double cost = records.stream()
                .mapToDouble(r -> r.price)
                .sum();

            final int uniqueSongCount = records.stream()
                .flatMap(r -> r.songs.stream())
                .collect(Collectors.toSet())
                .size();

            final double pricePerUniqueSong = cost/uniqueSongCount;

            return pricePerUniqueSong <= _maxPricePerUniqueSong
                ? uniqueSongCount
                : 0.0;
        };
    }

    @Override
    public Codec<ISeq<Record>, BitGene> codec() {
        return codecs.ofSubSet(_records);
    }

    public static void main(final String[] args) {
        final double maxPricePerUniqueSong = 2.5;

        final Springsteen springsteen = new Springsteen(
            ISeq.of(
                new Record("Record1", 25, ISeq.of("Song1", "Song2", "Song3", "Song4", "Song5", "Song6")),
                new Record("Record2", 15, ISeq.of("Song2", "Song3", "Song4", "Song5", "Song6", "Song7")),
                new Record("Record3", 35, ISeq.of("Song5", "Song6", "Song7", "Song8", "Song9", "Song10")),
                new Record("Record4", 17, ISeq.of("Song9", "Song10", "Song12", "Song4", "Song13", "Song14")),
                new Record("Record5", 29, ISeq.of("Song1", "Song2", "Song13", "Song14", "Song15", "Song16")),
                new Record("Record6", 5, ISeq.of("Song18", "Song20", "Song30", "Song40"))
            ),
            maxPricePerUniqueSong
        );

        final Engine<BitGene, Double> engine = Engine.builder(springsteen)
            .build();

        final ISeq<Record> result = springsteen.codec().decoder().apply(
            engine.stream()
                .limit(10)
                .collect(EvolutionResult.toBestGenotype())
        );

        final double cost = result.stream()
            .mapToDouble(r -> r.price)
            .sum();

        final int uniqueSongCount = result.stream()
            .flatMap(r -> r.songs.stream())
            .collect(Collectors.toSet())
            .size();

        final double pricePerUniqueSong = cost/uniqueSongCount;

        System.out.println("Overall cost:  " + cost);
        System.out.println("Unique songs:  " + uniqueSongCount);
        System.out.println("Cost per song: " + (cost/uniqueSongCount));
        System.out.println("Records:       " + result.map(r -> r.name).toString(", "));

    }
}

A função fitness é simples, o número de músicas únicas, restritas pelo preço máximo por música, que você está disposto a pagar. A execução do código imprimirá a seguinte saída:

Overall cost:  37.0
Unique songs:  15
Cost per song: 2.466666666666667
Records:       Record2, Record4, Record6
    
por 09.08.2016 / 18:04
fonte