3. Heuristik fuer NPP Problem

Heuristik fuer NPP Problem

  • P

    Servus,

    ich hab ein Problem, ein NP-hartes. Naemlich das Number Partition Problem. Ich hab einen Satz von k Integern und muss die in zwei moeglichst gleich grosse Mengen einteilen (muss nicht exakt gleich sein, aber moeglichst nah dran).

    Ich hab gegoogelt und im Sedgewick nachgeschlagen, es soll eine dynamic programming Loesung geben, leider konnte ich keine gute Anleitung oder keinen fertigen Algorithmus finden.
    Hat jemand ne Anleitung oder nen fertigen Algo in irgend einer Sprache (mein Programm ist in C) (Also die Anleitund auf deutsch/englisch/spanisch, der Code in beliebiger Sprache) oder nen Link wo ich das bekommen kann? Ich braeuchte halt was um meinen Algo zu verbessern/ersetzen. Ich hab ne eigene Heuristik mit stochastischer Suche die fuer n < 20 (~95% der Faelle) super und schnell geht, aber da n auch mal an die 100 werden kann ist das nicht ausreichend.

    Bin fuer jeden Tip dankbar!

    0
  • ?

    Hi

    Ich hab einen Satz von k Integern und muss die in zwei moeglichst gleich grosse Mengen einteilen

    Hmm ist ein bisschen unexakt.

    Aber soweit ich das verstanden habe meinst du folgendes:
    Sei S eine Menge. Existiert eine disjunkte Partitionierung von S durch Teilmengen S_1 und S_2 s.d.
    ∑a∈S_1a=∑_a∈S2a\sum_{a \in S\_1} a = \sum\_{a \in S_2} a

    Das kann man aber auch wie folgt formulieren.
    Sei S eine Menge und
    B:=∑a∈SaB:= \sum_{a \in S} a
    Existiert eine Teilmenge S_1 s.d.
    ∑a∈S1a=B2\sum_{a \in S_1} a = \frac{B}{2}

    Das entspricht dann dem subset-sum Problem (Untermengensummenproblem).

    Dafür dürfte dir z.B. das hier weiterhelfen http://www-ag-mayer.informatik.uni-kl.de/~agmlehre/ws03/eaa/folien/kapitel-13.5.ps

    Näheres dazu in "Introduction to Algorithms - Second Edition" von Cormen, Rivest.

    0
  • J

    pli:

    Wie falsch wird denn das Greedy-Verfahren mit nach Größe sortierten Elementen? Das ist zumindest verflixt schnell.

    0
Anmelden zum Antworten