Obtenha a combinação mais eficiente de uma grande lista de objetos com base em um campo

9

Estou procurando maximizar o número de estrelas com um determinado orçamento e limite máximo na combinação.

Pergunta de exemplo:

Com um orçamento de 500 euros, visitando apenas o máximo permitido de restaurantes ou menos, jante e colete o máximo de estrelas possível.

Estou procurando escrever um algoritmo eficiente, que possa potencialmente processar 1 milhão de instâncias de restaurantes para até 10 restaurantes no máximo.

Observe que esta é uma postagem cruzada de uma pergunta que fiz ontem: Java: obtenha a combinação mais eficiente de uma grande lista de objetos com base em um campo

A solução abaixo atribuirá 15 $ por estrela ao r8Restaurante, o que significa que, ao gerar a lista, ela é colocada em primeiro lugar e, com os restantes 70 $, só pode obter mais 2 estrelas, totalizando 4 estrelas. No entanto, se fosse inteligente o suficiente para pular o r8restaurante (mesmo que seja a melhor relação dólar por estrela), o r1restaurante seria realmente uma escolha melhor para o orçamento, pois custa 100 dólares e 5 estrelas.

Alguém pode ajudar a tentar o problema e vencer a solução atual?

import itertools

class Restaurant():
  def __init__(self, cost, stars):
    self.cost = cost
    self.stars = stars
    self.ratio = cost / stars

  def display(self):
    print("Cost: $" + str(self.cost))
    print("Stars: " + str(self.stars))
    print()

r1 = Restaurant(100, 5)
r2 = Restaurant(140, 3)
r3 = Restaurant(90, 4)
r4 = Restaurant(140, 3)
r5 = Restaurant(120, 4)
r6 = Restaurant(60, 1)
r7 = Restaurant(40, 1)
r8 = Restaurant(30, 2)
r9 = Restaurant(70, 2)
r10 = Restaurant(250, 5)

print()
print("***************")
print("** Unsorted: **")
print("***************")
print()

restaurants = [r1, r2, r3, r4, r5, r6, r7, r8, r9, r10]

for restaurant in restaurants:
  print(restaurant.ratio, restaurant.stars)

print()
print("***************")
print("**  Sorted:  **")
print("***************")
print()

sorted_restaurants = sorted(restaurants, key = lambda x: x.ratio, reverse = True)

for restaurant in sorted_restaurants:
  print(restaurant.ratio, restaurant.stars)

print()
print("*********************")
print("** Begin Rucksack: **")
print("*********************")
print()

max = 5
budget = 100

spent = 0
quantity = 0

rucksack = []

for i in itertools.count():

  if len(rucksack) >= max or i == len(sorted_restaurants):
    break

  sorted_restaurants[i].display()

  if sorted_restaurants[i].cost + spent <= budget:
    spent = spent + sorted_restaurants[i].cost
    rucksack.append(sorted_restaurants[i])

print("Total Cost: $" + str(sum([x.cost for x in rucksack])))
print("Total Stars: " + str(sum([x.stars for x in rucksack])))

print()
print("*****************")
print("** Final List: **")
print("*****************")
print()

for restaurant in rucksack:
  restaurant.display()
AK47
fonte
2
Isso é mochila? Perdoe-me, eu olhei.
precisa
11
É o mesmo conceito de mochila - budget= peso mochila máximo em kg, max= número de itens da mochila pode conter, stars= algum valor no item e costpeso = item em kg
AK47
3
E qual é o problema com o código postado?
cricket_007
11
@ cricket_007, com base no pedido, atribui 15 $ por estrela ao r8restaurante, o que significa que, ao gerar a lista, coloca-o na lista primeiro e, com os 70 dólares restantes, ele pode obter apenas mais 2 estrelas. No entanto, se fosse inteligente o suficiente para ignorar isso (mesmo que seja a melhor relação dólar por estrela, o r1restaurante seria realmente uma escolha melhor para o orçamento, pois custa 100 dólares e 5 estrelas
AK47

Respostas:

5

Parece que seu problema é praticamente o mesmo que o problema da mochila: Maximize o valor, considerando certas restrições de peso e volume. Basicamente, valor = total de estrelas, peso = preço, limite da mochila = orçamento total. Agora, há uma restrição adicional ao total de "itens" (visitas a restaurantes), mas isso não muda a essência.

Como você pode ou não saber, o problema da mochila é difícil de NP, o que significa que nenhum algoritmo com escala de tempo polinomial é conhecido.

No entanto, pode haver algoritmos pseudopolinomiais eficientes usando programação dinâmica e, é claro, existem heurísticas eficientes, como a heurística "gananciosa" que você parece ter descoberto. Essa heurística envolve começar a preencher os itens de "densidade" mais altos (a maioria das estrelas por dólar) primeiro. Como você viu, essa heurística falha em encontrar o verdadeiro ideal em alguns casos.

A abordagem de programação dinâmica deve ser muito boa aqui. É baseado em uma recursão: dado um orçamento B e várias visitas restantes V, qual é o melhor conjunto de restaurantes para visitar de um conjunto total de restaurantes R?

Veja aqui: https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem

Basicamente, definimos uma matriz mpara "máximas estrelas", onde m[i, b, v]é a quantidade máxima de estrelas que podemos obter quando nos é permitido visitar restaurantes com até (incluindo) número de restaurante i, gastar no máximo be visitar na maioria dos vrestaurantes (o limite) .

Agora, de baixo para cima preenchemos esta matriz. Por exemplo, m[0, b, v] = 0para todos os valores de be vporque, se não podemos ir a nenhum restaurante, não podemos obter estrelas.

Além disso, m[i, b, 0] = 0para todos os valores de ie bporque se esgotássemos todas as nossas visitas, não conseguiríamos mais estrelas.

A próxima linha também não é muito difícil:

m[i, b, v] = m[i - 1, b, v] if p[i] > b Onde p[i]está o preço das refeições no restaurante i? O que esta linha diz? Bem, se o restaurante ié mais caro do que o que resta ( b), não podemos ir até lá. O que significa que a quantidade máxima de estrelas que podemos obter é a mesma, independentemente de incluirmos restaurantes com até iou apenas até i - 1.

A próxima linha é um pouco complicada:

m[i, b, v] = max(m[i-1, b, v]), m[i-1, b - p[i], v-1] + s[i]) if p[i] <= b

Ufa. s[i]é a quantidade de estrelas que você recebe do restaurante ibtw.

O que esta linha diz? É o coração da abordagem de programação dinâmica. Ao considerar a quantidade máxima de estrelas que podemos obter ao procurar em restaurantes i, inclusive , na solução resultante, vamos para lá ou não, e "apenas" precisamos ver qual desses dois caminhos leva a mais estrelas:

Se não formos a um restaurante i, mantemos a mesma quantidade de dinheiro e as visitas restantes. A quantidade máxima de estrelas que podemos obter nesse caminho é a mesma que se nem olhávamos no restaurante i. Essa é a primeira parte do max.

Mas se formos a um restaurante i, ficaremos com p[i]menos dinheiro, menos uma visita e s[i]mais estrelas. Essa é a segunda parte do max.

Agora a questão é simples: qual dos dois é maior.

Você pode criar essa matriz e preenchê-la com um loop for relativamente simples (inspire-se no wiki). Isso apenas fornece a quantidade de estrelas, mas não a lista real de restaurantes para visitar. Para isso, adicione alguma contabilidade extra ao cálculo de w.


Espero que a informação seja suficiente para levá-lo na direção certa.

Como alternativa, você pode escrever seu problema em termos de variáveis ​​binárias e uma função objetiva quadrática e resolvê-lo no analisador quântico D-Wave :-p Envie-me uma mensagem se quiser saber mais sobre isso.

Lagerbaer
fonte
Em relação ao tempo polinomial, o máximo de 10 restaurantes significa que o problema pode ser resolvido por força bruta, repetindo todas as combinações de até 10 restaurantes e mantendo o melhor, em O (n ^ 10). Agora, também não quero executar um algoritmo O (n ^ 10) com n = 10 ^ 6, mas é tempo polinomial.
kaya3
Os "10 restaurantes" são um número realmente fixo ou apenas foram fixados no exemplo acima e podem ser maiores para um exemplo diferente?
Lagerbaer 02/12/19
Essa é uma boa pergunta e não está claro quais parâmetros do problema devem ser generalizados ao analisar o tempo de execução. Obviamente, não há solução conhecida que seja polinomial em k, apenas quero dizer que é uma conclusão bastante fraca se estivermos interessados ​​apenas no problema para k pequeno.
precisa saber é o seguinte
O número "máximo" de restaurantes pode mudar. Essa iteração pode ser 10 e a seguir pode ser 5. #
AK47
@ AK47 Independentemente disso, o algoritmo que eu esbocei acima deve ser bem organizado. O tamanho da matriz multidimensional é fornecido pelo seu orçamento, número de restaurantes e número de visitas, e é necessário O (1) para preencher uma entrada da matriz, para que o algo seja executado no tempo O (R B V).
Lagerbaer
2

Usando a mesma idéia da minha resposta aqui :

Em uma coleção de n números positivos que somam S, pelo menos um deles será menor que S dividido por n (S / n)

você pode criar a lista a partir dos possíveis restaurantes "mais baratos" .

As etapas do algoritmo:

  • Encontre os 5 restaurantes com custo <500/10, cada um com estrelas diferentes e com o menor custo para cada estrela . por exemplo, r1, r2, r3, r4, r5
  • Para cada um dos valores acima, encontre outros 5 restaurantes com custo <(500 - custo (x)) / 9 e estrelas diferentes . Selecione novamente o menor custo para cada estrela
  • faça isso até chegar a 10 restaurantes e não exceder seu orçamento.
  • Execute novamente as 3 etapas acima para o limite de 1 a 9 restaurantes.
  • Mantenha a solução que produz mais estrelas

Obviamente, você não pode selecionar novamente um restaurante.

Eu acho que no pior caso, você terá que calcular 5x5x5 ... = 5 ^ 10 + 5 ^ 9 + ... + 5 ^ 2 + 5 (= cerca de 12 milhões) soluções.

Em javascript

function Restaurant(name, cost, stars) {
    this.name = name;
    this.cost = cost;
    this.stars = stars;
}

function RestaurantCollection() {
    var restaurants = [];
    var cost = 0;
    this.stars = 0;

    this.addRestaurant = function(restaurant) {
        restaurants.push(restaurant);
        cost += restaurant.cost;
        this.stars += restaurant.stars;
    };

    this.setRestaurants = function(clonedRestaurants, nCost, nStars) {
        restaurants = clonedRestaurants;
        cost = nCost;
        this.stars += nStars;
    };
    this.getAll = function() {
        return restaurants;
    };

    this.getCost = function() {
        return cost;
    };
    this.setCost = function(clonedCost) {
        cost = clonedCost;
    };

    this.findNext5Restaurants = function(restaurants, budget, totalGoal) {
        var existingRestaurants = this.getAll();
        var maxCost = (budget - cost) / (totalGoal - existingRestaurants.length);
        var cheapestRestaurantPerStarRating = [];
        for(var stars = 5; stars > 0; stars--) {
            var found = findCheapestRestaurant(restaurants, stars, maxCost, existingRestaurants);
            if(found) {
                cheapestRestaurantPerStarRating.push(found);
            }
        }
        return cheapestRestaurantPerStarRating;
    };

    this.clone = function() {
        var restaurantCollection = new RestaurantCollection();
        restaurantCollection.setRestaurants([...restaurants], this.getCost(), this.stars);
        return restaurantCollection;
    };
}

function findCheapestRestaurant(restaurants, stars, maxCost, excludeRestaurants) {
     var excludeRestaurantNames = excludeRestaurants.map(restaurant => restaurant.name);
     var found = restaurants.find(restaurant => restaurant.stars == stars && restaurant.cost <= maxCost && !excludeRestaurantNames.includes(restaurant.name));
     return found;
}

function calculateNextCollections(restaurants, collections, budget, totalGoal) {
    var newCollections = [];
    collections.forEach(collection => {
        var nextRestaurants = collection.findNext5Restaurants(restaurants, budget, totalGoal);
        nextRestaurants.forEach(restaurant => {
            var newCollection = collection.clone();
            newCollection.addRestaurant(restaurant);
            if(newCollection.getCost() <= budget) {
                 newCollections.push(newCollection);
            }
        });
    });
    return newCollections;
};

var restaurants = [];
restaurants.push(new Restaurant('r1', 100, 5));
restaurants.push(new Restaurant('r2',140, 3));
restaurants.push(new Restaurant('r3',90, 4));
restaurants.push(new Restaurant('r4',140, 3));
restaurants.push(new Restaurant('r5',120, 4));
restaurants.push(new Restaurant('r6',60, 1));
restaurants.push(new Restaurant('r7',40, 1));
restaurants.push(new Restaurant('r8',30, 2));
restaurants.push(new Restaurant('r9',70, 2));
restaurants.push(new Restaurant('r10',250, 5));

restaurants.sort((a, b) => a.cost - b.cost);
var max = 5;
var budget = 100;

var total = max;
var totalCollections = [];

for(var totalGoal = total; totalGoal > 0; totalGoal--) {
    var collections = [new RestaurantCollection()];

    for(var i = totalGoal; i > 0; i--) {
        collections = calculateNextCollections(restaurants, collections, budget, totalGoal);
    }
    totalCollections = totalCollections.concat(collections);
}

var totalCollections = totalCollections.map(collection => { 
      return {
          name: collection.getAll().map(restaurant => restaurant.name),
          stars: collection.stars,
          cost: collection.getCost()
      }
});

console.log("Solutions found:\n");
console.log(totalCollections);

totalCollections.sort((a, b) => b.stars - a.stars);
console.log("Best solution:\n");
console.log(totalCollections[0]);

Jannes Botis
fonte
Hey @Jannes Botis, está demorando 27 segundos para 100000 restaurantes: repl.it/repls/StripedMoralOptimization Você acha que é possível otimizá-lo para trabalhar com 1 milhão de registros?
AK47
O gargalo é a função .filter () dentro de findCheapestRestaurant (), você pode classificar () os restaurantes no custo após a criação e usar .find () em vez de filter (), pois apenas o primeiro encontrado será o mais barato. Eu fiz a alteração no link. Mas acho que a melhor solução seria usar um banco de dados (por exemplo, mysql) para restaurantes com um índice de custo, para que você possa substituir .filter () por uma seleção condicional.
Janes Botis