2010-09-14 16 views
6

Ich versuche, eine C# Anwendung zu entwickeln, die eine Liste aller möglichen Permutationen, innerhalb einer Grenze, und die Kosten generieren. Zum Beispiel habe ich eine Liste von 80 Jobs. Jeder Job hat einen Wert (1-5) (typischerweise 3) und jeder Ingenieur hat eine Grenze, wie viel er tun kann, typischerweise einen Wert von 20.C# geordneten Kombinationen Algorithmus

Im Moment habe ich angefangen, indem ich eine Liste von allen erstellt habe mögliche Kombinationen (n!/(k! * (nk)! wobei n die Gesamtanzahl der Jobs ist und k 2 ist.) Die Verbindung zwischen jedem Job sollte mit der Entfernung zwischen jedem Job gewichtet sein.

Von hier I Ich möchte einen ersten Start-Job auswählen und eine Liste aller möglichen Kombinationen von Jobs (vom Start-Job) bis zum Limit von 20 erstellen und dann nach der Summe des Gewichtes ordern. Die niedrigste Gewichts-Route würde gewinnen und zugeteilt werden der Ingenieur Mein Problem ist, dass ich nicht weiß, wie ich das angehen soll - welche Datenstruktur wäre am besten?

Typischerweise gibt es ca. 6-8 Ingenieure (auf die Arbeitsbelastung abhängig), I auf Routing jeden Ingenieur einer nach dem anderen geplant hatte - einmal eine Route zu einem anderen Ingenieur zugeteilt worden waren, würden diese Arbeitsplätze aus der Liste und eine neue entfernt werden Startjob ausgewählt mit einem neuen Satz von Kombinationen generiert. Klingt das nach einem akzeptablen Ansatz?

Jede Hilfe wäre willkommen.

+1

das klingt wie ein mathematisches Problem im Grunde, anstelle von einem C# -Problem. (obwohl beide sehr nah sind): –

+1

Wiederholtes Rucksackproblem? – dtb

+6

eine C# -Bibliothek für Permutationen, Kombinationen, cartesianischen Produkte und andere praktische Funktionen Kombinatorik denn hier gibt es: http://www.codeproject.com/KB/recipes/Combinatorics.aspx –

Antwort

2

würde ich simuliertes Glühen versuchen, ein Algorithmus ein globales Optimum zu finden, indem Konfigurationen nach dem Zufall entsprechend die Energie des Systems zu testen.

http://en.wikipedia.org/wiki/Simulated_annealing

Überprüfen Sie die Artikel für den Pseudo-Code.

1

Es gibt keinen effizienten Algorithmus zu lösen dieses Problem. Ich würde einen genetischen Algorithmus verwenden (findet nicht unbedingt die optimale Lösung, sondern findet eine akzeptable Lösung).

Verwandte Themen