Algoritme laagste prijs bij meerdere aanbieders

[RwD]

Ik loop vast op het schrijven voor een algoritme dat de laagste prijs berekent gegeven meerdere aanbieders met prijzen en transportkosten. Op het eerste gezicht lijkt het eenvoudig, misschien mis ik iets.

• Ik heb een winkelwagen met producten.
• Ieder product heeft een aantal en een prijs (die afhankelijk is van de leverancier)
• Er zijn meerdere leveranciers met allen eigen prijzen en transportkosten.
• Als dat goedkoper is mag een product bij meerdere leveranciers besteld worden om tot het totaal te komen.

Wat ik probeer te bereiken is efficient uit te rekenen wat de goedkoopste combinatie is. Dus als een product 3 keer besteld is en de goedkoopste leverancier heeft hem 2 keer, maar samen met leverancier 2 kom ik aan drie. Echter doordat ik twee keer transportkosten betaal is deze combinatie duurder dan 3 keer bij leverancier 2.

Het is een beetje lastig om hierbij te laten zien wat ik al heb geprobeerd omdat niks wat ik schreef me echt het idee geeft dat ik het opgelost heb. In bovenstaande voorbeeld zou het best kunnen zijn dat leveranciers 3 en 4 samen goedkoper zijn als ik de producten daar over verdeel. Of ook mogelijk is dat de transportkosten vs prijs zo gunstig zijn dat 1 keer lev 3 + 2 keer lev 4 goedkoper is dan 3 keer lev 4. Als iemand me al kan vertellen in woorden wat de beste aanpak is ben ik misschien al geholpen.

Wat ik (in woorden) heb geprobeerd is (een beetje brute force):

1. Iedere leverancier afzonderlijk tellen.
2. Als er minstens 1 is die het alleen kan leveren is dat mijn streefprijs.
3. Iedere combinatie van twee leveranciers afgaan. Dit betekend dus ook artikelaantallen varieren. Kom ik onder de streefprijs heb ik een nieuw doel.
4. Iedere combinatie van 3 leveranciers ...
5. Iedere combinatie van x tot alle leveranciers ...

Nogmaals, ik denk vast te moeilijk, maar aan het einde van het algoritme heb ik nodig een rijtje leveranciers, met aantal dat ik er bestel (en tegen welke prijs dat is).

[pedorus]

[Java] Efficienter varianten bitmap genereren (winkelmand) gelezen?

[RwD]

Zojuist gelezen. Als ik me niet vergis is de vraag daar hoe je de verschillende combinaties efficient kunt berekenen. Ik snap alleen niet goed hoe ik deze combinaties toepas op mijn situatie. In mijn geval heb ik alleen nog leveranciers over die het product kunnen leveren. Ik denk dat dat mij een stap te abstract is om meteen te snappen hoe ik dit kan gebruiken...

Ik heb ook over het knapzakprobleem gelezen, maar mijn situatie is toch anders? Ik heb geen maximum waar ik onder moet blijven, bovendien zijn de verzendkosten 1 keer per leverancier, niet een gewicht per product.

Voorlopig ga ik het brute-forcen. Maar iedere verbetering is welkom...

[Big Womly]

Ik heb bovenstaande zaken niet gelezen, maar zelf was ik aan het denke aan een variant van het Shortest path problem

Edit:
Lees op Wikipedia eens het gedeelte van Dynamic Programming van het knapzakprobleem. Dit is volgens mij de beste oplossing voor jouw probleem

[ Voor 40% gewijzigd door Big Womly op 17-07-2012 14:12 ]

[Soultaker]

Zoals in dat topic van ACM ook genoemd wordt gaan “efficiënte” oplossingen door middel van dynamic programming en dergelijke de mist in doordat de prijzen van producten verschillen per leverancier. Voorlopig lijkt brute force me dus de enige werkbare aanpak.

Als je wil nadenken over een dp-aanpak zou ik beginnen met een meer beperkte variant zoals: gegeven een verzameling producten en een lijst van winkels die elk een deelverzameling van die producten kunnen leveren, wat is het minimum aantal winkels dat je moet selecteren zodat je alle producten kunt bestellen?

Zolang je daar geen efficiënte oplossing voor kunt bedenken hoef je aan het probleem van de TS niet eens te beginnen.

[Big Womly]

Soultaker schreef op dinsdag 17 juli 2012 @ 15:06:
Zoals in dat topic van ACM ook genoemd wordt gaan “efficiënte” oplossingen door middel van dynamic programming en dergelijke de mist in doordat de prijzen van producten verschillen per leverancier. Voorlopig lijkt brute force me dus de enige werkbare aanpak.

Als je wil nadenken over een dp-aanpak zou ik beginnen met een meer beperkte variant zoals: gegeven een verzameling producten en een lijst van winkels die elk een deelverzameling van die producten kunnen leveren, wat is het minimum aantal winkels dat je moet selecteren zodat je alle producten kunt bestellen?

Zolang je daar geen efficiënte oplossing voor kunt bedenken hoef je aan het probleem van de TS niet eens te beginnen.

Creëer een 2D tabel, per kolom 1 product (3 schijven = 3 kolommen), per rij een winkel: double prijzen [w][h]
Als een winkel een bepaald artikel te weinig op voorraad heeft (3 nodig, 2 beschikbaar), dan zet je die prijs ofwel op +oneindig (gemakkelijkst), oftewel negatief en filter je die er later uit.
Hou een tabel bij of je al eerder in een bepaalde winkel iest gekocth hebt: besteld[h]

creëer nu een graaf door alle prijzen in nodes te steken en ze met elke node uit de volgende kolom te verbinden. Hier kan je de producten die niet of onvoldoende beschikbaar zijn eruit filteren.

Pas nu het shortest path algoritme toe

code:

if (huidige_prijs + prijs[x][y1]+besteld[y1]?0:transport[y1] < huidige_prijs + prijs[x][y2]+besteld[y2]?0:transport[y2])
  //Ga voor y1
else
  //Ga voor y2

[Soultaker]

Ik vind het maar een warrig verhaal, maar volgens mij pas je nu een greedy algoritme toe, wat niet gegarandeerd een optimaal antwoord oplevert.

Bijvoorbeeld als je producten x en y wil kopen, die overal hetzelfde kosten, maar winkel 1 heeft alleen product x en rekent 2 euro transportkosten, winkel 2 heeft alleen product y en rekent ook 2 euro transportkosten, terwijl winkel 3 beide producten heeft maar 3 euro transportkosten heeft.

In dat geval kun je het beste beide producten bij winkel 3 bestellen, maar een greedy algoritme dat steeds één product toevoegt zal dat niet inzien.

Hoe je graaf er precies uitziet is me ook niet duidelijk, maar ik vermoed dat als je het juiste antwoord kunt vinden met een kortste-pad algoritme, de grootte van de graaf exponentieel is in het aantal winkels/producten, en dan kun je net zo goed direct de brute-force oplossing toepassen.

[ACM]

In het geval van het winkelmandje op Tweakers.net (de link hierboven) is het zo dat een extra product toevoegen aan je berekening ervoor kan zorgen dat de totale aanvullende kosten afnemen, ipv toenemen. Denk bijvoorbeeld aan regels als "vanaf 100 euro gratis verzenden". Dan kan je dus krijgen dat je dan met 2 producten op 99 euro zit en met een derde product boven de 100 euro uitkomt. Waardoor ineens de opgetelde verzendkosten die eerder wel bestonden ineens wegvallen.
En alle optimalisatie-oplossingen die ik destijds bekeken heb, inclusief gebaseerd op grafen en andere alternatieve representaties, kunnen daar niet tegen. Er is vziw geen enkel standaard shortest-path-algoritme voor een graaf, dat er tegen kan dat als je route A, B, C neemt dat dat afstand X oplevert, maar als je A, B, C, D neemt, dat dan het stukje van A, B, C verandert in Y.
Tenzij je natuurlijk een los pad constueert voor A, B, C met D ten op zichte van A, B, C zonder D

Als van dat soort onhandige situaties geen sprake is, dan kan je waarschijnlijk wel de boel met meer generieke algoritmes oplossen.
Desalniettemin is voor een beperkt aantal mogelijkheden het domweg brute-forcen alsnog geen gek idee.

[ Voor 4% gewijzigd door ACM op 19-07-2012 15:42 ]

[Ventieldopje]

Je zou als je voor brute-force gaat ook nog delen kunnen cachen Denk dat dat gewoon de makkelijkste oplossing is voor zo'n complex probleem.

[ Voor 36% gewijzigd door Ventieldopje op 19-07-2012 16:01 ]