4. rekursiver Algorithmus gesucht

rekursiver Algorithmus gesucht

  • ?

    Hallo,

    ich habe folgende Problemstellung und komme einfach auf keinen gruenen Zweig:

    - es existieren x Objekte
    - jedes Objekt hat n bestimmte Eigenschaften
    - die Eigenschaften der Objekte lassen sich kombinieren
    - die Objekte sollen nach festgelegter Prioritaet nach den gesuchten Eigenschaften durchsucht werden
    - es gilt, die gesuchten Eigenschaften mit moeglichst wenigen Objekten zu befriedigen

    Beispiel:
    Objekt 1:
    rund und rot

    Objekt 2:
    eckig und blau

    Objekt 3:
    oval und gruen

    gesucht sind nun die Eigenschaften "oval und rot". Da keines der Objekte diese Eigenschaften sein eigen nennt, darf kombiniert werden.
    Ergebnis:
    Benoetigt werden die Objekte 1 und 3.

    Mein Ansatz waere ein rekursiver Algorithmus, der die Objekte nach folgendem Muster durchsucht (ausgehend von 4 Objekten; die Ziffern entsprechen den Objekten sortiert nach ihrer Prioritaet):

    1
2
3
4

1  2
1  3
1  4
2  3
2  4
3  4

1  2  3
1  2  4
1  3  4
2  3  4

1  2  3  4

    Gesucht waere nun ein Algorithmus, der mir diesen Suchvorgang abbilden kann.

    Ich hoffe jemand versteht was ich meine und kann mir helfen.

    (falls der Thread besser in "Rund um..." passt, bitte nicht schimpfen ;))

    Danke schon jetzt 🙂

    Bis bald
    ein Verzweifelter

    0
  • K

    Also typisch rekursiv ist das jedenfalls nicht glaub ich. ich würd erstmal geeignete Rahmenbedingungen schaffen, sprich der nach Priorität, Anzahl Eigenschaften sortieren. Dann von oben nach unten durchgehn, und so die Lösung zusammenbauen. Ein Branch&Bound Verfahren könnte auch gute Ergebniss bringen.

    0
  • ?

    Oh, ich vergass zu erwaehnen, dass die Anzahl Eigenschaften fuer alle Objekte gleich ist.

    0
  • K

    Nochmal folgender Tip (ich geb dir jetz keine Hausaufgabenlösung 😉
    Stelle eine Menge der in Frage kommenden Objekte auf. Dabei gewichtest du sie nach Priorität und (wichtiger) Nutzeneffekt (ein Objekt das 2 Eigenschaften abdeckt, ist nützlicher als eins das nur 1 schafft). Mit dieser Tabelle (sortierte Objekte mit Gewichtung) und dem Branch and Bound Verfahren dürftest du zügig zu allen optimalen Lösungen kommen. (Das ist bereits eine fertige Lösung, jetz musst du dir nur noch das B&B Verfahren raussuchen sowie eine geschickte Gewichtung überlegen)

    0
Anmelden zum Antworten