Tool um Gegenstände zu tauschen

[Izibaar]

Jeder kennt die Spiele oder Bilder bei denen man zufällig etwas käuft bzw auch geschenkt bekommt. Man versucht die Bilder seiner Mannschaft zu bekommen oder das Kartendeck was man sich ausgedacht hat. Da man aber nur für viel Geld gezielt kaufen kann wird blind gekauft und dann getauscht, getauscht, getauscht...
Und hier möchte ich ansetzen. Ich hätte gerne ein Tool, dass nach eingabe von "Vertausche ich" und "Will ich" Listen in einer Gruppe einen idealen Tauschvorgang bestimmt. Am Ende soll jeder wissen was er an wen gibt. Dazu sollen noch Prioritäten wie "brauche ich unbedingt" und "wäre schön zu haben".

Und jetzt habe ich gedacht, da gibt es bestimmt schon etwas oder es hat wenigstens sich jemand gedanken darüber gemacht wie man es (auch ohne Programm) möglichst ideal machen kann. Eine google Suche war leider nicht sehr ergiebig. Ich weiß jetzt nur wer an welcher Uni/Schule eine Gruppe wechseln will... Was ich jetzt Suche sind:
a) Ein Programm, dann hätte ich nichts mehr zu tun
b) Schlagworte die in google mehr Erfolg bringen
c) Hilfe wie man am Besten ansetzt. Um zum Optimum zu kommen glaube ich, dass man alle Möglichkeiten austesten muss und dann das mit den meisten Tauschvorgängen nimmt. Hatte auch den Gedanken, dass alles in die Mitte wandert und sich jeder etwas nimmt. Nur bekommt man dann am Ende nicht mehr seine Gegenstände zurück, sondern andere. Wobei das wiederum egal sein könnte, da man weder das eine noch das andere braucht.
d) Jemand erklärt mir man findet auch so das Optimum und braucht kein Programm.

 

[FArt]

Das ist ein Optimierngsproblem und hört sich verdammt nach NP-Vollständigkeit ? Wikipedia an.

Viel Spaß beim Lesen: Karps 21 NP-vollständige Probleme ? Wikipedia

 

[Marco13]

Ja, könnte grob in Richtung Matching (graph theory) - Wikipedia, the free encyclopedia gehen, aber dazu bräuchte man eine formalere Beschreibung.

 

[Izibaar]

Zuerst beschreibe ich das Problem dann mal etwas genauer:
Es gibt n Sammler. Jeder Sammler hat eine Liste (Lv) mit 1..m Figuren die er vertauschen will. Minimum beträgt 1, da man schließlich nichts bekommen kann ohne etwas wegzugeben. Die Liste kann allerdings bei jedem unterschiedlich lang sein. Zudem hat jeder Sammler eine Liste (Lh) mit 1..m Figuren die er haben will. Hier könnte es sein, dass jemand mit macht der keine Figuren haben will, aber seine zur verfügung stellt und am Ende mit anderen Figuren da steht die wiederum nicht braucht. Da dies unwahrscheinlich ist gehe ich von mindestens 1 aus.
Rahmenbedinungen sind, dass jeder mindestens eine Figur bekommen sollte die er haben will und jeder ungefähr gleich gut weg kommt. Letzteres heißt wenn zwei Sammler annähernd gleiche Lh abgeben und Lv gleiche Länge hat sie auch gleich viele Figuren bekommen.

Der Vorgang aus der Realität:
Sammler A will etwas was Sammler B hergeben will. Und Sammler B will etwas was A hergeben will. Also wird getauscht. Das ganze geht solange bis kein Paar mehr gefunden wird.
Zudem kann man einen Kreistausch machen. A gibt etwas an B was B braucht. B etwas an C was C braucht. C wieder an A oder an D usw. bis etwas an A geht und der Kreis geschlossen ist. Normalerweise beschränkt sich das auf wenige Personen, da sonst der Überblick verloren geht.


Man könnte alle Lh in eine Liste stecken und alle Lv. Dann hätte man das Heiratsproblem bzw Sekretärinnenproblem?! Nur muss man dann auch dafür sorgen, dass jemand der nur eine Figur hergibt auch nur eine bekommt.

 

[JohannisderKaeufer]

Rätselraten und Bruteforce sind zwar schön, aber ein LP-Model sollte das auch lösen können
Bspl 2 Personen und 2 Figuren
Die Variablen
Person 1:
Figur 1 Nehmen, Figur 1 Geben, Figur 2 Nehmen, Figur 2 Geben
Person 2:
Figur 1 Nehmen, Figur 1 Geben, Figur 2 Nehmen, Figur 2 Geben

also 8 Variablen x1 bis x8
Nun kann man Bedingungen aufstellen
x1 bis x8 sind alle nicht negativ.
x1 <= der Anzahl der Figuren 1 die Person 1 haben möchte
x2 <= der Anzahl der Figuren 1 die Person 1 hergeben möchte
x3 <= der Anzahl der Figuren 2 die Person 1 haben möchte
...
x8

x1 -x2 + x5 -x6 = 0 //Eine Figur 1 die hergegeben wird, soll auch von jemandem genommen werden
x3 -x4 + x7 -x8 = 0 //Eine Figur 2 die hergegeben wird, soll auch von jemandem genommen werden

x1-x2+x3-x4 = 0 //Die Bedingung das Person 1 für jede hergegebene Figur eine Figur bekommt
x5-x6+x7-x8 = 0 //Die Bedingung das Person 2 für jede hergegebene Figur eine Figur bekommt

Die Zielfunktion
z1*x1 + z2*x2 +...+z8*x8 -> max //Max weil ja möglichst viel getauscht werden soll

wobei zj =1 sein kann, bzw. die verschiedenen zj Werte annehme (z.B. 4 Will ich unbedingt, 3 wäre schön, 2 wenn sonst nichts geht, ...), bzw. (4 Weg damit, ... 1 wenn#s unbedingt jemand braucht)


Damit kann man schön Matrizen aufbauen und beispielsweise mit einem Gauss, der Simplex-Methode oder was auch immer lösen. Da gibts echt schöne Software für. Und die Lösen auch riesige Datenmengen. Ich hab es mal mit dem Solver aus Open Office Calc ausprobiert und das funktioniert schon ganz gut.
Nach diesem Model das ich hier beschrieben habe, kommst du auf AnzahlPersonen*AnzahlFiguren*2 Variablen
und Anzahl der Variablen +AnzahlPersonen + AnzahlFiguren Nebenbedingungen

kleine Typos beseitigt

 

[Stinner]

Rätselraten und Bruteforce sind zwar schön, aber ein LP-Model sollte das auch lösen können

So wie du das geschrieben hast, sehe ich aber keine Lösung.
Zuerst mal legst du Variablen für fest vorgebene Werte an.
Jede Person legt ja fest, wieviel er von einer Figur haben will.
Aber auch wenn es nur die gehandelte Menge ist, beachtest du nicht,
dass diese nicht das Angebot übersteigen darf und weiter die Zahlen ganzzahlig sein müssen.
Auch macht es wohl keinen Sinn für jede Person und Figur 2 Variablen anzulegen, wenn man einfach eine Variable für Veränderung festlegen kann.

Das Problem riecht schon nach einem ganzzahligen Optimierungsproblem, allerdings wüsste ich auf Anhieb keinen geeigneten Ansatz und würde mal tippen, dass man wegen der Prios irgendwie das Transportproblem modifizieren müsste. Weiter sind diese Probleme auch nicht leicht zu lösen, wenn man einen Ansatz hat. Aber ohne die

Ich würde diese Aufgabe mit folgendem BruteForce Ansatz lösen:
Erstmal eine Priorisierung der Angebote und Nachfragen machen. Kritierien sind z.B. Quotient zwischen Angebot und Nachfrage sowie festgelegte durch Nutzer.

Danach würde ich einen Gesamtmarkt aller Figuren bilden und meine Priority-Queue der Nachfrage abarbeiten.

Es kann zwar dann passieren, dass jmd eine hohe Prio bei der Nachfrgae hat, aber weil seine Nachfrage vom Markt nicht bedient werden kann, er nix bekommt, aber viel abgibt.Zum wohle des maximalen Handels =)
Dazu könnte man die Prios updaten nachdem eine Nachfrgae bearbeitet wurde

 

[JohannisderKaeufer]

So wie du das geschrieben hast, sehe ich aber keine Lösung.
Zuerst mal legst du Variablen für fest vorgebene Werte an.
Jede Person legt ja fest, wieviel er von einer Figur haben will.
Aber auch wenn es nur die gehandelte Menge ist, beachtest du nicht,
dass diese nicht das Angebot übersteigen darf und weiter die Zahlen ganzzahlig sein müssen.
Auch macht es wohl keinen Sinn für jede Person und Figur 2 Variablen anzulegen, wenn man einfach eine Variable für Veränderung festlegen kann.

Das Problem riecht schon nach einem ganzzahligen Optimierungsproblem, allerdings wüsste ich auf Anhieb keinen geeigneten Ansatz und würde mal tippen, dass man wegen der Prios irgendwie das Transportproblem modifizieren müsste. Weiter sind diese Probleme auch nicht leicht zu lösen, wenn man einen Ansatz hat. Aber ohne die

Auch wenn du keine Lösung zu sehen scheinst. Mit dem Ansatz ist das ganze Lösbar.
Beschäftige dich mal mit Linear Programming dann wirst du schon sehen.

Passende Softwarepakete sind bspl. Tenor lino
oder Mops - Mathematical Optimisation System.
Selbst mit dem Solver aus Open Office Calc kann man das Problem lösen.

In einem Beispiel muß ich ja festlegen, wieviel ein User von einer Figur handeln möchte.
In einem Programm gibt natürlich der User an was er möchte.


Die Tatsächlich gehandelte Menge wird beachtet man muß nur die Augen aufmachen:

Bedingung für Figur 1
x1 -x2 + x5 -x6 = 0 //Eine Figur 1 die hergegeben wird, soll auch von jemandem genommen werden
Bedingung für Figur 2
x3 -x4 + x7 -x8 = 0 //Eine Figur 2 die hergegeben wird, soll auch von jemandem genommen werden

Ganzzahligkeit läßt sich bei vielen Solvern per Klick anwählen.

Zwei Variablen werden lediglich dafür gewählt um das zu lösende Model übersichtlicher/nachvollziehbarer zu gestalten.

Der Programmablauf von mir wäre beispielsweise per Java-Programm die Userwünsche einzulesen.
Aus allen Userwünschen eine eingabe für einen Solver zu erstellen, das ganze von eben jenem lösen zu lassen, das ergebnis einlesen und per Java-Programm auszugeben.

Und man bekommt als dreingabe ein optimales Ergebnis, wenn das Kriterium lautet möglichst viele Figuren sollen getauscht werden.

 

[Izibaar]

Ich habe das ganze mal mit dem Solver von OpenOffice anhand von 3 Personen und 8 Figuren versucht nach zu vollziehen. Und ich bekomme für (sehr) einfache Beispiele eine Lösung die gut aussieht. Dabei fällt mir auf, dass ich mir noch Beispiele ausdenken muss die nach der "Realitäts-Methode" nicht optimal enden. Schon mal ein Danke für die gute Idee.


Es gibt noch eine Verbesserung, um die Variablen zu reduzieren. Macht es Sinn eine Figur 2 mal haben zu wollen und sie gleichzeitig 1 mal wegtauschen zu wollen? Nein! Entweder man will sie haben oder vertauschen. Folglich kann man sagen:
x1 > 0 //Wenn die Person die Figur haben will
x1 < 0 //Wenn die Person die Figur vertauschen will

Bei den Nebenbedingungen floss x2 immer mit minus ein. So dass hier keine Änderung nötig ist. Bei der Zielfunktion muss man dann allerdings den Betrag nehmen:
z1*|x1| + z2*|x2| +...+z4*|x4| = max



Die ganzen Programme die mir eine Lösung bieten habe ich auch schon entdeckt. Jetzt muss darum eine Benutzeroberfläche. Mein jetziges Problem ist allerdings, dass ich nichts gefunden habe mit vernünftiger Dokumentation. ojalgo und jlinalg habe ich auf sourceforge gefunden. Aber kein Beispiel wie man eine Gleichung übergibt. Kann mir jemand helfen?
(Zur Zeit versuche ich ein Programm abzuwandeln welches Jama benutzt)

 

[JohannisderKaeufer]

Zielfunktion mit beträgen ist eine Möglichkeit die in manchen Programmen funktionieren mag.
Allerdings sind die meisten Bibliotheken darauf ausgerichtet keine "Funktionen" entgegenzunehmen, sondern nur die Koeffizienten

c1*x1 + c2*x2 -c3*x3  -> max
wird als
double[] array = new array[]{c1,c2, -c3};
übergeben

Was ich benutze ist aus dem Apache-Projekt math-commons (Version 2, gibt's momentan glaub ich allerdings nur als Dev-Snapshot)

Hier verwende ich org.apache.commons.math.optimization.linear.SimplexSolver (Wird es wie gesagt erst ab Version 2 geben, funktioniert aber schon!)

Da ich das ganze mal wieder ausprobieren wollte hab ich mich mal an die Aufgabenstellung gewagt.
Ich hab mir eine Eingabedatei gebastelt die folgendermaßen aussieht:

a
b c
x1
xb*c

a = Anzahl der Testfälle (1)
b = Anzahl der Personen die am Tauschprogramm teilnehmen
c = Anzahl der Gegenstände die Getauscht werden können
x1 ... xc = gibt jeweils an wie viele Gegenstände Person 1 vom jeweiligen Typ hergegeben (negativ) oder erhalten (positiv) möchte.
xc+1 ... xc*2 = für Person 2 ...

Die Ausgabe

Case #n: x1...xb*c

x1 ...xc = gibt an welche und wieviele Gegenstände die Personen 1 hergeben (negativ) bzw. erhalten (positiv) muß, damit möglichst viel getauscht wird.

Der Code den ich dazu verwendet habe sieht so aus

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Scanner;

import org.apache.commons.math.optimization.GoalType;
import org.apache.commons.math.optimization.RealPointValuePair;
import org.apache.commons.math.optimization.linear.LinearConstraint;
import org.apache.commons.math.optimization.linear.LinearObjectiveFunction;
import org.apache.commons.math.optimization.linear.Relationship;

public class Tauschtool {

	private PrintWriter writer = null;
	private Scanner scanner = new Scanner(System.in);
	private int testCases;

	public Tauschtool() {
		try {
			writer = new PrintWriter(new File("output/result.txt"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		try {
			scanner = new Scanner(new File("input/test.in"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public void run() {

		testCases = scanner.nextInt();
		// scanner.nextLine();

		long time = System.currentTimeMillis();
		for (int testCase = 1; testCase <= testCases; testCase++) {

			String ergebnis = ("Case #" + testCase + ": " + calcResult());

			System.out.println(ergebnis);
			writer.write(ergebnis + "\n");
		}
		writer.flush();
		writer.close();
		System.out.println(System.currentTimeMillis() - time);
	}

	private String calcResult() {
		int anzahlPersonen = scanner.nextInt();
		int anzahlFiguren = scanner.nextInt();
		int[][] wunschMatrix = new int[anzahlPersonen][anzahlFiguren * 2];
		for (int i = 0; i < anzahlPersonen; i++) {
			for (int j = 0; j < anzahlFiguren; j++) {
				int zahl = scanner.nextInt();
				if (zahl >= 0) {
					wunschMatrix[i][j * 2] = zahl;
					wunschMatrix[i][j * 2 + 1] = 0;
				} else {
					wunschMatrix[i][j * 2] = 0;
					wunschMatrix[i][j * 2 + 1] = zahl * -1;
				}
			}
		}
		printWunschmatrix(wunschMatrix);
		double[] array = new double[wunschMatrix.length
				* wunschMatrix[0].length];
		Arrays.fill(array, 1);
		LinearObjectiveFunction f = new LinearObjectiveFunction(array, 0);
		Boolean[] ganzZahlig = new Boolean[wunschMatrix.length
				* wunschMatrix[0].length];
		Arrays.fill(ganzZahlig, true);
		Collection<LinearConstraint> cons = getVarConstraints(wunschMatrix);
		addAngebotNachfrageConstraints(cons, anzahlPersonen, anzahlFiguren);
		addPersonConstraints(cons, anzahlPersonen, anzahlFiguren);
		RealPointValuePair solution = EinfachesSimplex.solve(f, cons,
				GoalType.MAXIMIZE, true, ganzZahlig);
		StringBuffer buffer = new StringBuffer();
		for (int i = 0; i < solution.getPoint().length; i = i + 2) {
			if (solution.getPoint()[i] > 0) {
				buffer.append(Math.round(solution.getPoint()[i]));
			} else {
				buffer.append(Math.round(solution.getPoint()[i + 1] * -1));
			}
			buffer.append(" ");
		}

		buffer.append("max " + solution.getValue());
		return buffer.toString();
	}

	private void addPersonConstraints(Collection<LinearConstraint> cons,
			int anzahlPersonen, int anzahlFiguren) {
		for (int i = 0; i < anzahlPersonen; i++) {
			double[] array = new double[anzahlFiguren * anzahlPersonen * 2];
			Arrays.fill(array, 0);
			for (int j = 0; j < anzahlFiguren * 2; j = j + 2) {
				array[(i * anzahlFiguren * 2) + j] = 1;
				array[(i * anzahlFiguren * 2) + j + 1] = -1;
			}
			cons.add(new LinearConstraint(array, Relationship.EQ, 0));
		}

	}

	private void addAngebotNachfrageConstraints(
			Collection<LinearConstraint> cons, int anzahlPersonen,
			int anzahlFiguren) {
		for (int i = 0; i < anzahlFiguren * 2; i = i + 2) {
			double[] array = new double[anzahlFiguren * anzahlPersonen * 2];
			Arrays.fill(array, 0);
			for (int j = 0; j < anzahlPersonen; j++) {
				array[(j * anzahlFiguren * 2) + i] = 1;
				array[(j * anzahlFiguren * 2) + i + 1] = -1;
			}
			cons.add(new LinearConstraint(array, Relationship.EQ, 0));
		}

	}

	private Collection<LinearConstraint> getVarConstraints(int[][] wunschMatrix) {
		Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
		for (int i = 0; i < wunschMatrix.length; i++) {
			for (int j = 0; j < wunschMatrix[0].length; j++) {
				double[] array = new double[wunschMatrix.length
						* wunschMatrix[0].length];
				Arrays.fill(array, 0);
				array[i * wunschMatrix[0].length + j] = 1;
				constraints.add(new LinearConstraint(array, Relationship.LEQ,
						wunschMatrix[i][j]));
			}
		}

		return constraints;
	}

	private void printWunschmatrix(int[][] wunschMatrix) {
		for (int i = 0; i < wunschMatrix.length; i++) {
			for (int j = 0; j < wunschMatrix[0].length; j++) {
				System.out.print(wunschMatrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		new Tauschtool().run();
	}
}

EinfachesSimplex.solve(f, cons,
				GoalType.MAXIMIZE, true, ganzZahlig);

verwendet eine Wrapper-Klasse die mir ganzzahligkeit ermöglicht. Deren Code möchte ich allerdings nicht veröffentlichen.
Dieses Codestück kann allerdings durch

SimplexSolver solver = new SimplexSolver();
			solver.setMaxIterations(10000);//je nach größe des Problems anpassen
			solution = solver.optimize(f, cons, GoalType.MAXIMIZE,
					true);

ersetzen. Da in meinen getesteten fällen immer ein natürliches Ganzzahliges Ergebnis herauskommt, ist die Wrapper-klasse in diesem Fall unnötig.

 

[Izibaar]

Nachdem ich mir 'Constraints' übersetzt habe und mir einige Ausgaben einebaut habe, denke ich ich habe es verstanden. Eine Wertigkeit einzubauen sollte kein Problem sein. Ohne Beispiel hätte ich da keine Chance gehabt. Danke. Übrigens ist die Version 2.0 schon seit August draußen.

Bei meinem Beispiel, welches ich mit dem Solver gelöst hatte, bin ich direkt auf einen Fehler gestoßen. 18 statt 14 ein- bzw abgaben. Was 9 statt 7 Tauschvorgängen entspricht. Hat sich allerdings als Tippfehler herrausgestellt. Doch dann kam das eigentliche Problem: 17 ein- bzw abgaben - 8,5 Tauschvorgänge. Es wird eine Figur abgegeben die niemand erhält und das löst weitere Tausche aus. Hier die Eingabe Matrix (habe ich so als Beispiel hardcodet):

private String calcResult() {
    	//Beispiel
        int anzahlPersonen = 3;
        int anzahlFiguren = 8;
        int[][] wunschMatrix = //new int[anzahlPersonen][anzahlFiguren * 2];
        	new int[][]{ 
        		{2,0, 1,0, 2,0, 0,2, 0,1, 0,0, 0,1, 0,0},	//Person 1
        		{0,1, 0,1, 0,0, 1,0, 0,0, 0,1, 0,0, 1,0},	//Person 2
        		{1,0, 0,2, 0,2, 0,1, 1,0, 3,0, 0,0, 0,2}	//Person 3
		//Figur  A     B    C     D    ...
        		};
        
        System.out.println("Pers "+wunschMatrix.length+"  Fig "+wunschMatrix[0].length);
       /*  
         Ergebnis:
          0  1  2 -1 -1  0 -1  0
         -1  0  0  1  0 -1  0  1
          1 -1 -2  0  1  1  0 -1  x
	                         x
         */
        
        printWunschmatrix(wunschMatrix);

Das Ergebnis welches ich bekomme ist als Kommentar drin. Die Zeilen / Spalten mit x sind nicht 0. Übrigens ergab sich durch den Tippfehler genau an dieser Stelle an der sich die beiden x kreuzen eine 1.
Irgendwelche Ideen was falsch läuft?

 

[JohannisderKaeufer]

{2,0, 1,0, 2,0, 0,2, 0,1, 0,0, HIER LIEGT DAS PROBLEM, 0,0}, //Person 1
{0,1, 0,1, 0,0, 1,0, 0,0, 0,1, 0,0, 1,0}, //Person 2
{1,0, 0,2, 0,2, 0,1, 1,0, 3,0, 0,0, 0,2} //Person 3
//Figur A B C D ...
};

Da in dieser Spalte sonst nur Nullen stehen scheint der Solver diese Spalte auszulassen.
Ein Versuch mit 1,0 statt 0,1 liefert ein wie ich meine korrektes Ergebnis, 0,2 an dieser Stelle schlägt ebenfalls Fehl. Da der Solver schon ausgeht "fertig zu sein".

Eine Lösung des Problems habe ich allerdings gefunden.
In Zeile 76 - 78
werden nacheinander constraints mit
getVarConstraints(wunschMatrix);
addAngebotNachfrageConstraints(cons, anzahlPersonen, anzahlFiguren);
addPersonConstraints(cons, anzahlPersonen, anzahlFiguren);
hinzugefügt.

Wenn man das nun so umschreibt, das sich die Reihenfolge ändert und die getVarConstraints erst am Schluß hinzugefügt werden löst sich das Problem und es kommt für dein Beispiel das Ergebnis 14, bzw. 7 heraus.

also:

addAngebotNachfrageConstraints(cons, anzahlPersonen, anzahlFiguren);
addPersonConstraints(cons, anzahlPersonen, anzahlFiguren);
getVarConstraints(cons, wunschMatrix);

 

[Izibaar]

Ich weiß zwar nicht warum es hilft die Reihenfolge zu verändert, aber es funktioniert. Zeigt aber auch, dass ich auf alle Fälle Fehlerabfragen einbauen muss. Werde die Bedingungen einfach nochmals testen bevor eine Ausgabe stattfindet bzw die wichtigsten davon (Zeile je 0 und Spalte je 0).