Optimale Aufstellung bei Wettbewerb

[jakobwenzel]

Hallo zusammen!

Bei einem Schwimmwettbewerb muss pro Disziplin eine bestimmte, je nach Disziplin verschiedene, Anzahl an Personen starten, die wiederum in nur einer bestimmten Gesamtanzahl an Disziplinen starten dürfen. Die Gesamtanzahl der Person ist auch festgelegt. Die Zeit der gesamten Mannschaft wird durch Addition der Einzelzeiten bestimmt.
Mein Programm soll nun aus einer Liste von Personen und ihren Zeiten in den einzelnen Disziplinen die optimale Aufstellung berechnen. Leider fällt mir dazu kein besserer Algorithmus als simples Durchprobieren aller Möglichkeiten ein, dessen Laufzeit bei 10 Personen und 5 Disziplinen schon relativ bescheiden ist (rechnet seit 50 Minuten...).
Gibt es da irgendeinen besseren Ansatz?

Crosspost DF: http://www.delphi-forum.de/viewtopic.php?t=89327

Vielen Dank schonmal im Voraus

Jakob

[Luckie]

Ja unbd wie sieht dein Algorithmus jetzt aus?

[jfheins]

Man könnte evtl. in 2 Schritten da ran gehen:

1. Optimale Lösung finden (ohne die Einschränkungen)
Du suchst für jede Disziplin die Personenkombination heruasm, die am schnellsten ist.

2. Du passt die optimale Lösung den Einschränkungen an (min. Disziplin/Person)

Du gehst die Personen duch und schaust, an wievielen Disziplinen sie teilnehmen, und versuchst dann gezielt Personen zu tauschen, die die Gesamtzeit möglichst wenig erhöhen ...

Sollte was gutes dabei herauskommen, ob es aber die beste Lösung ist, weis ich nicht

@Luckie: Brute-Force

Zitat von jakobwenzel:

Durchprobieren aller Möglichkeiten

[mkinzler]

Du benötigst zudem ne Möglichkeit zur Gewichtung von Ergebnisen. So könntest du für jede Diziplin eine Rangliste aufstellen und anhand der Gewichtungen Personen tauschen

[WInfo]

Moin Moin Jung,

das scheint mir ein Standard LP Problem zu sein, probiere es doch mal mit dem Excel Solver, nachdem Du dein Modell modelliert hast. Falls Du es just for fun machst, kannst Du auch noch Geschwindigkeitsvorteile mit einer nativen Implementation finden. Für den skizzierten Umfang solltest Du selbst mit den Taschenrechner und Papier und Bleistift keine 50 Minuten zur Lösung benötigen.

[google]define: LP[/google]

[jakobwenzel]

Whow, das hat mir schonmal sehr viel weiter geholfen.
Ich speicher mir jetzt eine Datei im "CPLEX LP Format" um dann mit der glpsol.exe die Lösung zu berechnen.

Die zu optimierenden Werte hab ich jetzt Ny/x genannt, wobei y die Zeile (=Person) und x die Spalte (=Disziplin) ist. Die Variablen können jeweils 1 (=dabei) oder 0 (=nicht dabei) haben.

So sieht das speichern dann in Delphi aus:

Delphi-Quellcode:

procedure SaveLP(filename: String;RowCount,ColCount:Integer);
var
  sList: TStringList;
  s:String;
  Row: Integer;
  Col: Integer;
begin
  sList:=TStringList.Create;

  //Berechnung der Zeit
  sList.Add('Minimize');
  for Row := 0 to RowCount - 1 do
  begin
    if Row>0 then
      s:=' + '
    else
      s:='value: ';

    for Col := 0 to ColCount - 1 do
      s:=s+' '+TimeToSecStr(LPList[Row][Col])+' N'+Inttostr(Row)+'/'+Inttostr(Col)+' +';

    sList.Add(Copy(s,1,length(s)-1));

  end;


  sList.Add('subject to');

  //Anzahl Starts pro Disziplin
  for Col := 0 to ColCount - 1 do
  begin
    s:='ns'+Inttostr(col)+': ';
    for Row := 0 to RowCount - 1 do
    begin
      s:=s+' N'+Inttostr(Row)+'/'+Inttostr(Col)+' +'
    end;
    s:=Copy(s,1,length(s)-1);
    s:=s+' = '+Inttostr(RowList.HeaderRow.NumStarts[Col]);
    sList.Add(s);
  end;

  //Starts pro Person
  for row := 0 to RowCount - 1 do
  begin
    s:='np'+Inttostr(row)+': ';
    for col := 0 to ColCount - 1 do
    begin
      s:=s+' N'+Inttostr(Row)+'/'+Inttostr(Col)+' +';
    end;
    s:=Copy(s,1,length(s)-1);
    s:=s+' <='+Inttostr(RowList.Settings.FNumPersonStarts);
    sList.Add(s);
  end;

  sList.Add('Bounds');

  for row := 0 to RowCount - 1 do
    for col := 0 to ColCount - 1 do
      sList.Add('  N'+Inttostr(Row)+'/'+Inttostr(Col)+' <=1');

  sList.Add('Integer');

  for row := 0 to RowCount - 1 do
    for col := 0 to ColCount - 1 do
      sList.Add('  N'+Inttostr(Row)+'/'+Inttostr(Col));

  sList.SaveToFile(filename);
  sList.Free;
end;

Falls sich irgendwer den Code aufmerksam (naja, Kommentare lesen reicht eigentlich) durchgelesen hat, wird merken, dass die Beschränkung auf die Gesamtzahl noch fehlt, was auch noch mein Problem ist.
Bei dem Format kann man ja nur Faktor * Variable + nächster Faktor * ... rechnen, womit sich das meines Wissens nicht machen lässt.
Hat irgendwer nen Tipp?

Jakob

[WInfo]

Moin Moin Jung,

hast Du dir denn meinen Beitrag durchgelesen und mal nachgedacht wie du das am besten lösen kannst?

[alzaimar]

Ist das nicht ein Knapsack 0/1-Problem, und damit NP-komplett? Ist nur so ne Annahme, da ich seit einiger Zeit keine Probleme dieser Art mehr auf dem Tisch habe (Arbeitgeberwechsel).

[3_of_8]

Es sieht wirklich sehr NP-vollständig aus, also ich fürchte fast, effizienter als Bruteforcen geht nicht - man kann höchstens noch das Bruteforcing an sich optimieren.

[Cyf]

Kann man daraus nicht einen Graph modelieren mit den Personen als Knoten, die Kanten verlaufen jeweils von einer Person zu allen anderen, sie sind aber jeweils (bei 5 Disziplinen) mit 5 verschiedenen Kanten, die den Zeiten entsprechen verbunden.
Dann sollte man jetzt Ameisen auf den Graph loslassen können und muss dabei bei jedem Durchlauf immer für die Knoten einen Zähler einbauen, wie oft der Knoten schon besucht wurde (also in wievielen Disziplinen die Person schon teilnimmt), ist der Grenzwert erreicht, so darf der Knoten nicht mehr besucht werden. Pro Durchlauf muss es 5 (5 Disziplinen) geschlossene Kreise mit der Länge der an der jeweiligen Disziplin teilnehmenden Personenanzahl geben (backtracking). Dann wird zurückgesetzt, die Erfahrungswerte der Ameisen werden gespeichert und die bester erreichte Zeit (also hier überhaupt erstmal die vom ersten Durchlauf) mit ihrern 5 Ruten ebenfalls. Dann startet eine neue Runde die Ameisen erneut, aber diesmal mit Einfluss durch die Erfahrung. Für mehr Variation löscht man nach jeder Runde noch einen Teil der Erfahrung. Nun lässt man das Ding beliebig lang laufen und hofft auf das Beste.
ACO ist schon was tolles. War jetzt meine spontane Idee, wie sich das umsetzen lässt, müsste man sehen.