Erhalten Sie die effizienteste Kombination einer großen Liste von Objekten basierend auf einem Feld

9

Ich möchte die Anzahl der Sterne bei einem bestimmten Budget und einer maximalen Begrenzung der Kombination maximieren.

Beispielfrage:

Mit einem Budget von 500 Euro, wenn Sie nur die maximal zulässigen Restaurants oder weniger besuchen, speisen und sammeln Sie die meisten Sterne, die möglich sind.

Ich möchte einen effizienten Algorithmus schreiben, der möglicherweise 1 Million Restaurantinstanzen für maximal 10 Restaurants verarbeiten kann.

Beachten Sie, dass dies ein Kreuzbeitrag aus einer Frage ist, die ich gestern gestellt habe: Java: Holen Sie sich die effizienteste Kombination einer großen Liste von Objekten basierend auf einem Feld

Die folgende Lösung weist dem r8Restaurant 15 $ pro Stern zu , was bedeutet, dass beim Generieren der Liste diese zuerst in die Liste aufgenommen werden und mit den verbleibenden 70 $ nur 2 weitere Sterne erhalten werden, was insgesamt 4 Sterne ergibt. Wenn es jedoch klug genug wäre, das r8Restaurant zu überspringen (obwohl es das beste Verhältnis von Dollar zu Stern ist), wäre das r1Restaurant tatsächlich eine bessere Wahl für das Budget, da es 100 $ kostet und 5 Sterne kostet.

Kann jemand helfen, das Problem zu versuchen und die aktuelle Lösung zu schlagen?

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
quelle
2
Ist das Rucksack? Verzeih mir, ich überflog.
Kenny Ostrom
1
Es ist das gleiche Konzept des Rucksacks - budget= maximales Rucksackgewicht in kg, max= Anzahl der Gegenstände, die der Rucksack aufnehmen kann, stars= ein gewisser Wert auf dem Gegenstand und cost= Gegenstandsgewicht in kg
AK47
3
Und was ist das Problem mit dem veröffentlichten Code?
Cricket_007
1
@ Cricket_007 basierend auf der Bestellung weist es dem r8Restaurant 15 $ pro Stern zu , was bedeutet, dass es beim Generieren der Liste zuerst in die Liste aufgenommen wird und mit den verbleibenden 70 $ nur 2 weitere Sterne erhalten kann. Wenn es jedoch klug genug wäre, dies zu überspringen (obwohl es das beste Verhältnis von Dollar zu Stern ist, wäre das r1Restaurant tatsächlich eine bessere Wahl für das Budget, da es 100 $ kostet und 5 Sterne kostet
AK47

Antworten:

5

Klingt so, als ob Ihr Problem fast dasselbe ist wie das Rucksackproblem: Maximieren Sie den Wert bei bestimmten Gewichts- und Volumenbeschränkungen. Grundsätzlich Wert = Gesamtsterne, Gewicht = Preis, Rucksacklimit = Gesamtbudget. Jetzt gibt es eine zusätzliche Einschränkung für die Gesamtzahl der "Artikel" (Restaurantbesuche), aber das ändert nichts am Kern.

Wie Sie vielleicht wissen oder nicht wissen, ist das Rucksackproblem NP-schwer, was bedeutet, dass kein Algorithmus mit Polynomzeitskalierung bekannt ist.

Es kann jedoch effiziente Pseudopolynomalgorithmen geben, die dynamische Programmierung verwenden, und natürlich gibt es effiziente Heuristiken, wie die "gierige" Heuristik, die Sie anscheinend entdeckt haben. Diese Heuristik beinhaltet, zuerst mit dem Auffüllen der Gegenstände mit der höchsten "Dichte" (die meisten Sterne pro Bock) zu beginnen. Wie Sie gesehen haben, findet diese Heuristik in einigen Fällen nicht das wahre Optimum.

Der dynamische Programmieransatz sollte hier ziemlich gut sein. Es basiert auf einer Rekursion: Was ist angesichts eines Budgets B und einer Anzahl verbleibender Besuche V die beste Gruppe von Restaurants aus einer Gesamtmenge von Restaurants R?

Siehe hier: https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem

Grundsätzlich definieren wir ein Array mfür "maximale Sterne", wobei m[i, b, v]die maximale Anzahl von Sternen angegeben wird, die wir erhalten können, wenn wir Restaurants bis zur (einschließlich) Restaurantnummer i, höchstens Ausgaben bund höchstens vRestaurants besuchen dürfen (das Limit). .

Jetzt füllen wir dieses Array von unten nach oben. Zum Beispiel m[0, b, v] = 0für alle Werte von bund vweil wir keine Sterne bekommen können, wenn wir nicht in ein Restaurant gehen können.

Außerdem können wir m[i, b, 0] = 0für alle Werte von iund bweil wir keine Sterne mehr bekommen, wenn wir alle unsere Besuche aufgebraucht haben.

Die nächste Zeile ist auch nicht zu schwer:

m[i, b, v] = m[i - 1, b, v] if p[i] > b wo p[i]ist der Preis im Restaurant speisen i. Was sagt diese Zeile? Wenn das Restaurant iteurer ist als wir noch Geld haben ( b), können wir nicht dorthin gehen. Was bedeutet, dass die maximale Anzahl an Sternen, die wir bekommen können, gleich ist, unabhängig davon, ob wir Restaurants bis zu ioder nur bis zu einbeziehen i - 1.

Die nächste Zeile ist etwas knifflig:

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

Puh. s[i]ist die Anzahl der Sterne, die Sie iübrigens vom Restaurant erhalten.

Was sagt diese Zeile? Es ist das Herzstück des dynamischen Programmieransatzes. Wenn wir die maximale Anzahl von Sternen berücksichtigen, die wir erhalten können, wenn wir uns Restaurants bis einschließlich iansehen, dann gehen wir in der resultierenden Lösung entweder dorthin oder nicht, und wir müssen "nur" sehen, welcher dieser beiden Wege zu mehr führt Sterne:

Wenn wir nicht ins Restaurant gehen i, behalten wir den gleichen Geldbetrag und die verbleibenden Besuche. Die maximale Anzahl an Sternen, die wir auf diesem Weg bekommen können, ist die gleiche, als hätten wir uns nicht einmal das Restaurant angesehen i. Das ist der erste Teil in der max.

Aber wenn wir ins Restaurant gehen i, haben wir p[i]weniger Geld, einen Besuch weniger und s[i]mehr Sterne. Das ist der zweite Teil in der max.

Jetzt ist die Frage einfach: Welcher der beiden ist größer?

Sie können dieses Array erstellen und mit einer relativ einfachen for-Schleife füllen (lassen Sie sich vom Wiki inspirieren). Dies gibt Ihnen jedoch nur die Anzahl der Sterne, nicht die tatsächliche Liste der zu besuchenden Restaurants. Fügen Sie dazu der Berechnung von zusätzliche Buchhaltung hinzu w.


Ich hoffe, dass Informationen ausreichen, um Sie in die richtige Richtung zu lenken.

Alternativ können Sie Ihr Problem in Form von binären Variablen und einer quadratischen Zielfunktion schreiben und auf dem D-Wave-Quanten-Annelaer lösen :-p Nachricht an mich, wenn Sie mehr darüber wissen möchten.

Lagerbaer
quelle
In Bezug auf die Polynomzeit bedeutet das Maximum von 10 Restaurants, dass das Problem durch rohe Gewalt gelöst werden kann, indem alle Kombinationen von bis zu 10 Restaurants durchlaufen werden und das beste in O (n ^ 10) Zeit beibehalten wird. Jetzt möchte ich auch keinen O (n ^ 10) -Algorithmus mit n = 10 ^ 6 ausführen, aber es ist Polynomzeit.
Kaya3
Ist die Anzahl der "10 Restaurants" wirklich fest oder nur im obigen Beispiel festgelegt und könnte sie für ein anderes Beispiel größer sein?
Lagerbaer
Das ist eine gute Frage, und es ist nicht klar, welche Parameter des Problems bei der Analyse der Laufzeit verallgemeinert werden sollen. Natürlich gibt es keine bekannte Lösung, die in k polynomisch ist. Ich meine nur, dass dies eine ziemlich schwache Schlussfolgerung ist, wenn wir uns nur für das Problem für kleines k interessieren.
Kaya3
Die "maximale" Anzahl von Restaurants kann sich ändern. Diese Iteration kann 10 sein, und als nächstes kann es 5 sein.
AK47
@ AK47 Unabhängig davon sollte der Algorithmus, den ich oben skizziert habe, ziemlich ordentlich sein. Die Größe des mehrdimensionalen Arrays wird durch Ihr Budget, die Anzahl der Restaurants und die Anzahl der Besuche angegeben. Es ist O (1) erforderlich, um einen Eintrag des Arrays auszufüllen, sodass der Algo in der Zeit O (R) ausgeführt wird B V).
Lagerbaer
2

Mit der gleichen Idee wie meine Antwort hier :

In einer Sammlung von n positiven Zahlen, die sich zu S summieren, ist mindestens eine von ihnen kleiner als S geteilt durch n (S / n)

Sie könnten die Liste ausgehend von den potenziell "billigsten" Restaurants erstellen .

Die Schritte des Algorithmus:

  • Finden Sie die 5 Restaurants mit Kosten <500/10, jedes mit unterschiedlichen Sternen und den niedrigsten Kosten für jeden Stern . zB r1, r2, r3, r4, r5
  • Finden Sie für jeden der oben genannten Werte weitere 5 Restaurants mit Kosten <(500 - Kosten (x)) / 9 und verschiedenen Sternen . Wählen Sie erneut die niedrigsten Kosten für jeden Stern
  • Tun Sie dies, bis Sie 10 Restaurants erreichen und Ihr Budget nicht überschreiten .
  • Führen Sie die 3 oben genannten Schritte erneut aus, um das Limit von 1 bis 9 Restaurants zu erreichen.
  • Behalten Sie die Lösung, die die meisten Sterne erzeugt

Natürlich können Sie ein Restaurant nicht erneut auswählen.

Ich denke, im schlimmsten Fall müssen Sie 5x5x5 ... = 5 ^ 10 + 5 ^ 9 + ... + 5 ^ 2 + 5 (= ungefähr 12 Millionen) Lösungen berechnen.

In 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
quelle
Hey @Jannes Botis, es dauert 27 Sekunden für 100000 Restaurants: repl.it/repls/StripedMoralOptimization Glaubst du, es ist möglich, es für die Arbeit mit 1 Million Datensätzen zu optimieren?
AK47
Der Engpass ist die Funktion .filter () in findCheapestRestaurant (). Sie können die Restaurants nach ihrer Erstellung nach Kosten sortieren () und anstelle von filter () .find () verwenden, da nur die erste gefundene die billigste ist. Ich habe die Änderung im Link vorgenommen. Ich denke jedoch, dass die beste Lösung darin besteht, eine Datenbank (z. B. MySQL) für Restaurants mit einem Kostenindex zu verwenden, damit Sie .filter () durch eine bedingte Auswahl ersetzen können.
Jannes Botis