Obtenez la combinaison la plus efficace d'une grande liste d'objets basée sur un champ

9

Je cherche à maximiser le nombre d'étoiles étant donné un certain budget et une limite maximale sur la combinaison.

Exemple de question:

Avec un budget de 500 euros, ne visitant que le maximum de restaurants autorisés, dîner et collecter le plus d'étoiles possible.

Je cherche à écrire un algorithme efficace, qui pourrait potentiellement traiter 1 million d'instances de restaurant pour un maximum de 10 restaurants.

Remarque, ceci est une publication croisée d'une question que j'ai posée hier: Java: Obtenez la combinaison la plus efficace d'une grande liste d'objets basée sur un champ

La solution ci-dessous attribuera 15 $ par étoile au r8restaurant, ce qui signifie que lors de la génération de la liste, il la place en premier dans la liste, et avec les 70 $ restants, elle ne peut obtenir que 2 étoiles supplémentaires, soit un total de 4 étoiles. Cependant, s'il était assez intelligent pour sauter le r8restaurant (même s'il s'agit du meilleur rapport dollar / étoile), ler1 qualité restaurant serait en fait un meilleur choix pour le budget, car il coûte 100 $ et 5 étoiles.

Quelqu'un peut-il aider à tenter de résoudre le problème et à battre la solution actuelle?

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
la source
2
Est-ce un sac à dos? Pardonnez-moi, j'ai survolé.
Kenny Ostrom
1
C'est le même concept de sac à dos - budget= poids maximum du sac à dos en kg, max= nombre d'articles que le sac à dos peut contenir, stars= une certaine valeur sur l'article et cost= poids de l'article en kg
AK47
3
Et quel est le problème avec le code affiché?
cricket_007
1
@ cricket_007 basé sur la commande, il attribue 15 $ par étoile au r8restaurant, ce qui signifie que lors de la génération de la liste, il le met en premier, et avec les 70 $ restants, il ne peut obtenir que 2 étoiles supplémentaires. Cependant, s'il était assez intelligent pour ignorer cela (même s'il s'agit du meilleur ratio dollar par étoile, le r1restaurant serait en fait un meilleur choix pour le budget, car il coûte 100 $ et 5 étoiles
AK47

Réponses:

5

On dirait que votre problème est à peu près le même que le problème du sac à dos: maximisez la valeur en fonction de certaines contraintes de poids et de volume. Fondamentalement, valeur = nombre total d'étoiles, poids = prix, limite de sac à dos = budget total. Maintenant, il y a une contrainte supplémentaire du total des «articles» (visites au restaurant), mais cela ne change pas l'essentiel.

Comme vous le savez peut-être ou non, le problème du sac à dos est NP difficile, ce qui signifie qu'aucun algorithme avec une échelle de temps polynomiale n'est connu.

Cependant, il peut y avoir des algorithmes pseudopolynomiaux efficaces utilisant la programmation dynamique, et bien sûr il existe des heuristiques efficaces, comme l'heuristique "gourmande" que vous semblez avoir découverte. Cette heuristique implique de commencer à se remplir avec les éléments de «densité» les plus élevés (la plupart des étoiles par mâle) en premier. Comme vous l'avez vu, cette heuristique ne parvient pas à trouver le véritable optimum dans certains cas.

L'approche de programmation dynamique devrait être assez bonne ici. Il est basé sur une récursivité: étant donné un budget B et un nombre de visites restantes V, quel est le meilleur ensemble de restaurants à visiter sur un ensemble total de restaurants R?

Voir ici: https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem

Fondamentalement, nous définissons un tableau mpour "max stars", où m[i, b, v]est le nombre maximum d'étoiles que nous pouvons obtenir lorsque nous sommes autorisés à visiter les restaurants jusqu'à (et y compris) le numéro du restaurant i, dépenser au maximum bet visiter au maximumv restaurants (la limite) .

Maintenant, nous remplissons de bas en haut ce tableau. Par exemple, m[0, b, v] = 0pour toutes les valeurs de betv parce que si nous ne pouvons aller dans aucun restaurant, nous ne pouvons pas obtenir d'étoiles.

Aussi, m[i, b, 0] = 0pour toutes les valeurs de ietb parce que si nous avons utilisé toutes nos visites, nous ne pouvons plus obtenir d'étoiles.

La ligne suivante n'est pas trop difficile non plus:

m[i, b, v] = m[i - 1, b, v] if p[i] > bp[i]est le prix d'un repas au restaurant i. Que dit cette ligne? Eh bien, si le restaurant iest plus cher que nous avons de l'argent ( b), nous ne pouvons pas y aller. Ce qui signifie que le nombre maximum d'étoiles que nous pouvons obtenir est le même, que nous incluions des restaurants jusqu'à iou juste jusqu'à i - 1.

La ligne suivante est un peu délicate:

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

Phew. s[i]est le nombre d'étoiles que vous obtenez du restauranti btw.

Que dit cette ligne? C'est le cœur de l'approche de programmation dynamique. Lorsque l'on considère le nombre maximum d'étoiles que nous pouvons obtenir en regardant les restaurants jusqu'à et y comprisi , alors dans la solution résultante, nous y allons ou non, et nous devons "juste" voir lequel de ces deux chemins mène à plus étoiles:

Si nous n'allons pas au restaurant i, nous gardons la même somme d'argent et les visites restantes. Le nombre maximum d'étoiles que nous pouvons obtenir sur ce chemin est le même que si nous ne regardions même pas le restaurant i. C'est la première partie du max.

Mais si nous allons au restaurant i, nous nous retrouvons avec p[i]moins d'argent, une visite de moins et s[i]plus d'étoiles. C'est la deuxième partie dumax .

Maintenant, la question est simple: lequel des deux est plus grand.

Vous pouvez créer ce tableau et le remplir avec une boucle for relativement simple (inspirez-vous du wiki). Cela vous donne juste le nombre d'étoiles, pas la liste réelle des restaurants à visiter. Pour cela, ajoutez une comptabilité supplémentaire au calcul de w.


J'espère que les informations sont suffisantes pour vous mettre dans la bonne direction.

Alternativement, vous pouvez écrire votre problème en termes de variables binaires et d'une fonction objectif quadratique et le résoudre sur l'annelaer quantique D-Wave :-p Envoyez-moi un message si vous voulez en savoir plus à ce sujet.

Lagerbaer
la source
En ce qui concerne le temps polynomial, le maximum de 10 restaurants signifie que le problème peut être résolu par la force brute, en itérant à travers toutes les combinaisons de jusqu'à 10 restaurants, et en gardant le meilleur, en temps O (n ^ 10). Maintenant, je ne veux pas non plus exécuter un algorithme O (n ^ 10) avec n = 10 ^ 6, mais c'est le temps polynomial.
kaya3
Est-ce que les "10 restaurants" sont vraiment un nombre fixe, ou simplement fixé dans l'exemple ci-dessus, et pourraient être plus grands pour un autre exemple?
Lagerbaer
C'est une bonne question, et il n'est pas clair sur quels paramètres du problème sortir pour être généralisé lors de l'analyse du temps d'exécution. Bien sûr, il n'y a pas de solution connue qui soit polynomiale en k, je veux juste dire que c'est une conclusion assez faible si nous ne sommes intéressés que par le problème des petits k.
kaya3
Le nombre "max" de restaurants pourrait changer. Cette itération il peut être 10, et ensuite il peut être 5.
AK47
@ AK47 Quoi qu'il en soit, l'algorithme que j'ai esquissé ci-dessus devrait être assez soigné. La taille du tableau multidimensionnel est donnée par votre budget, le nombre de restaurants et le nombre de visites, et il faut O (1) pour remplir une entrée du tableau, donc l'algo s'exécute dans le temps O (R B V).
Lagerbaer
2

En utilisant la même idée que ma réponse ici :

Dans une collection de n nombres positifs qui se résument à S, au moins l'un d'entre eux sera inférieur à S divisé par n (S / n)

vous pouvez construire la liste à partir des restaurants potentiels "les moins chers" .

Les étapes de l'algorithme:

  • Trouvez les 5 restaurants avec un coût <500/10, chacun avec des étoiles différentes et le prix le plus bas pour chaque étoile . par exemple r1, r2, r3, r4, r5
  • Pour chacune des valeurs ci-dessus, trouvez 5 autres restaurants avec un coût <(500 - coût (x)) / 9 et des étoiles différentes . Sélectionnez à nouveau le coût le plus bas pour chaque étoile
  • faites ceci jusqu'à ce que vous atteigniez 10 restaurants et que vous ne dépassiez pas votre budget.
  • Relancez les 3 étapes ci-dessus pour une limite de 1 à 9 restaurants.
  • Gardez la solution qui produit le plus d'étoiles

Bien sûr, vous ne pouvez pas resélectionner un restaurant.

Je pense que le pire des cas, vous devrez calculer 5x5x5 ... = 5 ^ 10 + 5 ^ 9 + ... + 5 ^ 2 + 5 (= environ 12 millions) de solutions.

En 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
la source
Hé @Jannes Botis, ça prend 27 secondes pour 100 000 restaurants: repl.it/repls/StripedMoralOptimization Pensez-vous qu'il est possible de l'optimiser pour travailler avec 1 million d'enregistrements?
AK47
Le goulot d'étranglement est la fonction .filter () dans findCheapestRestaurant (), vous pouvez trier () les restaurants en fonction du coût après leur création et utiliser .find () au lieu de filter () car seul le premier trouvé sera le moins cher. J'ai fait le changement dans le lien. Mais je pense que la meilleure solution serait d'utiliser une base de données (par exemple mysql) pour les restaurants avec un index sur le coût, afin que vous puissiez remplacer .filter () par une sélection conditionnelle.
Jannes Botis