[MySQL] Vorgehensweise Kombinationen durchrechnen

Antilogarithm

Grünschnabel
Hallo zusammen,

ich stehe mittlerweile total auf dem Schlauch je länger ich mich mit dem Problem befasse. Kann mir bitte jemand einen Tipp geben, wie ich folgendes Problem am besten angehen kann?

Aufgabe:
Es sollen mehrere Produkte eingekauft werden.
7xtt6479.png

Diese Produkte werden von verschiedenen Händlern angeboten. Jeder Händler verlangt einen anderen Preis für die Produkte und nicht jeder Händler hat alle gesuchten Teile vorrätig.
txcn7lwp.png

Die Händler haben jeweils individuelle Versandkosten und unterschiedliche Mindestbestellwerte, die pro Bestellung mindestens erreicht werden müssen.
ao65dl97.png

Ich möchte die günstigste Kombination finden. Also: Wo bestellt man welches Produkt um die geringsten Gesamtkosten zu haben.
Die in den Screenshots gezeigten Werte sind nur Beispiele. Die tatsächlichen Tabellen sind deutlich umfangreicher.



Zwei Fragen habe ich dazu:

1. Gibt es einen Weg um mit möglichst wenigen Rechenschritten die günstigste Kombination zu finden, oder muss man alle Kombinationsmöglichkeiten durchgehen?

2. Wie kann man das Durchprobieren aller Kombinationsmöglichkeiten möglichst effektiv in SQL (stored procedure) programmieren?


Vielen Dank!
 
Zuletzt bearbeitet:
Was heisst günstigste Kombination?
shopC zum Beispiel hat nicht alle items.
Willst du jetz alles von einem shop oder dürcfen auch die shops kombiniert werden? Das wird dann extrem komplex dank der Mindestbestellmengen
 
Genau - gesucht wird die günstigste Kombination aus allen Shops. Da es nur sehr wenige Shops gibt, die alle gesuchten Items am Lager haben und manchmal gibt es auch gar keinen Shop der alle Artikel hat, dürfen bzw. müssen die Shops kombiniert werden.

Hier hat bereits jemand eine ähnliche Problemstellung mit Excel gelöst:
http://www.office-loesung.de/ftopic544846_0_0_asc.php

Ich habe versucht das in SQL zu übertragen, dreh mir dabei aber einen Knoten ins Hirn. :eek:

Außerdem hatte ich noch die stille Hoffnung, dass es vielleicht eine intelligentere Lösung für das Problem gibt, als alle Möglichkeiten durchrechnen zu müssen und ich nur zu unwissend bin, diese zu erkennen. ;-)
 
Zuletzt bearbeitet:
Die Zieltabelle sollte in etwa so aussehen:
orderitems.png

SQL:
SELECT SUM( `Total` )
ergibt in diesem Fall 50.00
 
Zuletzt bearbeitet von einem Moderator:
Bist du sicher dass du das rein in MySQL machen willst?
Ich habe heute über Mittag mal ein wenig herumgespielt und musste dabei bereits 2 temporäre Zwischentabellen erstellen, damit kein SQL entsteht das 1000 Zeilen hat und sich grosse Blöcke dauernd wiederholen.

Mit Stored Procedure bin ich in MySQL noch nie warm geworden, da sie sehr primitiv gehalten sind.
Auch Views taugen nix, da mir MySQL dauernd sagt, dass sie keine Subqueries erlaubt seien.

Das ganze in PHP lösen währe viel Einfacher.


Das Porblem: Ja, du musst alle Möglichkeiten durchrechnen. Aber zuerst musst ud alle Möglichkeiten haben. Daran habe ich mir 3/4 Stunden lang den Kopf zerbrochen bis ich dann das folgende schrieb.
SQL:
SELECT
	GROUP_CONCAT( CONCAT('vt_', o.item, '.vendor AS v_', o.item)),
	GROUP_CONCAT( CONCAT('b_vendor AS vt_', o.item)) 
	INTO @sel, @from1
FROM
  b_order o;
-- Mögliche Kobinationen zu einer ID auswerten
SET @sql = CONCAT('SELECT @id := @id+1 AS id, ', @sel, ' FROM (SELECT @id:=0) AS vars, ', @from1);

-- Diese wieder mittels UNION normalisieren
SELECT
	GROUP_CONCAT( CONCAT('SELECT id, \'', o.item, '\' AS item, v_', o.item, ' AS vendor FROM (', @sql, ') AS t') SEPARATOR ' UNION ALL ')
	INTO @sql
FROM
  b_order o;

-- Führt beim ersten Mal zu einem Fehler, dann temporär den DROP auskommentieren
DROP TABLE b_groups;
SET @sql = CONCAT('CREATE TABLE b_groups AS ', @sql, ' ORDER BY id, item');

-- SELECT @sql AS t;

PREPARE stmt FROM @sql;
EXECUTE stmt;
DEALLOCATE PREPARE stmt;
Das erstellt mir eine Gruppentabellen mit allen möglichen Kombinationen von Shops auf die Anzahl items.

Darauf ein Query das 1) Nur noch die Möglichkeiten berücksichtigt, die auch in vorhanden sind und 2) die Daten mit den Preisen etc. erweitert. Auch deses wieder in eine tabelle, da es nachher mehrfach genutzt werden muss
SQL:
SELECT
	g.*,
	iv.price_per_unit,
	o.qty,
	iv.price_per_unit * o.qty AS total,
	v.shipping_coasts,
	v.min_buy
FROM
	(
		-- Nur die Auswählen die auch leifern können
		SELECT
			g1.id
		FROM
			b_groups g1
			LEFT JOIN b_item_by_vendor v1
				ON v1.item = g1.item
				AND v1.vendor = g1.vendor
		WHERE
			NOT v1.item IS NULL
		GROUP BY
			g1.id
		HAVING
			COUNT(*) = 3
	) ids
	INNER JOIN b_groups g
		ON ids.id = g.id
	INNER JOIN b_item_by_vendor iv
		ON iv.item = g.item
		AND iv.vendor = g.vendor
	INNER JOIN b_order o
		ON o.item = g.item
	INNER JOIN b_vendor AS v
		ON v.vendor = g.vendor;

Darauf kann man dann so zugreiffen
SQL:
SELECT
	d1.*
FROM
	b_detail d1
	INNER JOIN (
			SELECT
				id
			FROM
				(
					SELECT
						d.id,
						d.vendor,
						MAX(d.shipping_coasts) AS shipping_coasts,
						SUM(d.total)	AS total_price,
						SUM(d.qty)		AS qty,
						MAX(d.min_buy) AS min_buy,
						MAX(d.shipping_coasts) + SUM(d.total)	AS total_vendor,
						-- Prüfen ob die Gesammtmenge nicht unter den Anforderungen des Verkäufers leigen
						(SUM(d.qty) > MAX(d.min_buy)) AS valid
					FROM
						b_detail d
					GROUP BY
						d.id,
						d.vendor
				) AS per_v
			GROUP BY
				id
			HAVING
				-- Alle bei denen bei einem Verkäufer die Mindestmenge durchgefallen ist ignorieren
				MIN(valid) != FALSE
			-- Und den kleinsten auswählen
			ORDER BY
				SUM(total_vendor)
			LIMIT 1 	
		) AS m
	ON m.id = d1.id
;
Das Resultat sieht mal so aus
Code:
id ; item  ; vendor ; price_per_unit ; qty ; total ; shipping_coasts ; min_buy
17 ; item1 ; shopB  ; 3              ; 5   ; 15    ; 6               ; 0
17 ; item2 ; shopC  ; 2              ; 11  ; 22    ; 5               ; 3
17 ; item3 ; shopB  ; 2              ; 1   ; 2     ; 6               ; 0
Wenn du das ganze jetzt noch so dargestellt haben willst wie du schreibst, kommst du fast nicht um eine Dritte Zwieschentabelle hinaus

Ich habs auch mit TEMPORARY TABLES versucht. Jedch hat er ein Problem damit diese innerhalb eines SQLs mehrfach anzusprechen.

So bleibt also das Problem, dass diese Lösung NICHT Multi-Session fähig ist.
 
Zuletzt bearbeitet von einem Moderator:
Wow! Ich bin beeindruckt was dir alles in einer 3/4 Stunde einfällt. :eek: Ich wäre auch in 3 - 4 Wochen nicht darauf gekommen.
Ich möchte das in MySQL lösen, weil ich hoffe, dass das am Enden schneller ist als eine Lösung in PHP.

Leider funktioniert es noch nicht so ganz.

Das dritte GROUP_CONCAT (im ersten Script #12) erzeugt eine zu lange Zeile
Code:
1 row(s) affected, 1 warning(s): 1260 Row 3 was cut by GROUP_CONCAT()
Die Zeile wird abgeschnitten.
Daraufhin habe ich den Wert für 'group_concat_max_len' in der mysql.conf auf 100M hoch setzten.
Da ich aber später mit wesentlich umfangreicheren Tabellen arbeiten muss, als hier bei diesem 3^3 Beispiel, fürchte ich, dass das keine dauerhafte Lösung sein wird. Aber erst mal egal - weiter...

/// EDIT: Fehlerbeschreibung gelöscht, da unsinnig
 
Zuletzt bearbeitet:
Sorry, mein Fehler! Ich habe die Tabellen falsch umbenannt. :mad:
(Habe 'b_item_by_vendor' versehentlich 'b_order' genannt)

Jetzt läuft es. VIELEN DANK!
 
Zuletzt bearbeitet:
Hallo und guten Abend,

die oben beschriebene Lösung des Problems ist leider nur für kleine Datenmengen geeignet.
Ich habe nun mal mit echten Daten gearbeitet. Dabei ging es um gerade einmal 38 gesuchte Produkte. Hierzu habe ich 130 Händler gefunden. Es hat aber nicht jeder Händler alle Teile. Manche haben viele Teile, manche nur ein einzelnes der gesuchten Teile.

Der oben beschriebene Ansatz, alle möglichen Kombinationen zu ermitteln und dann daraus diejenigen auszuwählen, die die Rahmenbedingungen erfüllen, ist nicht sinnvoll, da die Datenmenge einfach gigantisch wird. Bei meinem Beispiel mit den 38 Teilen von 130 Händlern kommt man auf 34.269.213.410.933.874.184.347.177.621.389.312 mögliche Kombinationen!

Ich muss also die zu betrachtende Datenmenge deutlich reduzieren.
Daher verfolge ich nun den Ansatz, nur jene Kombinationen zu berücksichtigen, bei denen maximal x Händler genutzt werden. Aber wie ermittele ich, welche Kombinationen maximal x unterschiedliche Händler enthalten, ohne wieder alle Kombinationen durchlaufen zu müssen?

Hat jemand von euch hierzu einen schlauen Gedanken?
(Im Anhang ist eine Testtabelle mit 6 Teilen von 10 Händlern.)

Nachtrag: Es darf gerne auch eine PHP-Lösung sein.


Schönen Gruß und schon mal vielen Dank für Eure Tipps.
 

Anhänge

  • b_item_by_vendor_BSP.sql.zip
    781 Bytes · Aufrufe: 3
Zurück