optimierung einiger listenoperationen

ichfalk

Hallo!

Ich muss einen Algorithmus implementieren (Nemhauser-Ullmann fürs Rucksack-Problem) und das hab ich auch hinbekommen.

der Alg. hat als Eingabe N Elemente, die jeweils aus einem Gewicht G_i und einem Profit P_i (beide double zwischen 0 und 1) bestehen.

zuerst erstellt der Alg eine Liste GRUND mit dem einzigen Element (0,0) (entspricht der leeren Menge in der Menge der Potenzmengen über die N Elemente)

auf Basis dieser Liste und des i-ten Elements (zu Begin natürlich das erste) wird eine neue Liste ERWEITERUNG berechnet: es wird einfach auf jedes Element aus GRUND das i-te Element drauf-addiert (also zu Beginn (0,0) + (G₁, P₁))

danach wird aus beiden Listen (GRUND, ERWEITRUNG) die neue Liste GRUND erstellt, und zwar werden nur dominante Elemente aufgenommen. Dominant ist ein Element, wenn es kein Element der beiden Listen gibt, welches mindestens so leicht und mindestens so profitabel ist wie das Vergleichselement.

nach Abschluss der Iteration über die N Elemente, hat man in der endgültigen Liste GRUND alle nicht-dominierten Elemente, die als Lösungen für das Rucksack-Problems in Frage kommen: das profitabelste (unter Beachtung der Rucksack-Kapazität) ist die optimale Lösung.

Hier mein Code:

element NemhauserUllmann(rucksackProblem rp)
{
	listElemente::iterator i, j, d, r;
	listElemente grund_liste, erweiterungs_liste, zwischen_liste;
	element dazu;

	dazu.gewicht = 0.0f;
	dazu.profit = 0.0f;
	grund_liste.clear();
	grund_liste.insert (grund_liste.end(), dazu);

	for (d = rp.elemente.begin(); d != rp.elemente.end(); ++d)
	{
		erweiterungs_liste.clear();
		for (j = grund_liste.begin(); j != grund_liste.end(); ++j)
		{	
			dazu.gewicht = j->gewicht + d->gewicht;
			if (dazu.gewicht < rp.kapazitaet)
			{
				dazu.profit = j->profit + d->profit;
				erweiterungs_liste.insert (erweiterungs_liste.end(), dazu);
			}
			else { break; }
		}

		i = grund_liste.begin(); 
		j = erweiterungs_liste.begin();
		zwischen_liste.clear();
		while ( (i != grund_liste.end()) || (j != erweiterungs_liste.end())) 
		{
			if (i == grund_liste.end())
			{
				zwischen_liste.insert(zwischen_liste.end(), j, erweiterungs_liste.end());
				break;
			}
			else if (j == erweiterungs_liste.end())
			{
				zwischen_liste.insert(zwischen_liste.end(), i, grund_liste.end());
				break;
			}
			else if ((i->profit >= j->profit) && (i->gewicht <= j->gewicht))
			{	
				++j;
			}
			else if ((i->profit <= j->profit) && (i->gewicht >= j->gewicht))
			{	
				++i; 
			}
			else if ((i->profit > j->profit) && (i->gewicht > j->gewicht))
			{
				dazu.gewicht = j->gewicht;
				dazu.profit = j->profit;
				zwischen_liste.insert(zwischen_liste.end(), dazu);
				++j;
			}
			else if ((i->profit < j->profit) && (i->gewicht < j->gewicht))
			{
				dazu.gewicht = i->gewicht;
				dazu.profit = i->profit;
				zwischen_liste.insert(zwischen_liste.end(), dazu);
				++i;
			}
		}

		grund_liste = zwischen_liste;
	}
	return grund_liste.back();
}

Was kann ich da verbessern:
*Kann man die Erstelleung der Liste ERWEITERUNG optimieren? (sprich: die Addition des i-ten Elements auf die GRUNDliste)
*Kann man die Dominanz-Prüfung verbessern?
*Vielleicht gar nicht Listen verwenden, sondern was anderes? (was ich aber vielleicht nicht kenne, weil ich gerade erst seit 2 Wochen C++ programmiere)

Wäre sehr dankbar für alle Hinweise!
Falk.

ichfalk

Kann mir keiner helfen?
Falk.