Bergmann89 - Mi 10.08.16 09:29
Titel: Optimierungsproblem in Graphen

---

Hey Leute,

ich arbeite zur Zeit an einem Optimierungsproblem eines Graphen, an dem ich mir die Zähne ausbeiße.
Ich habe einen einfachen ungerichteten Graphen G(V,E). Ich suche eine Menge M <= V für die gilt: Für alle Knoten x aus V exestiert mindestens eine Kante e(x,y) sodass x € M oder y € M. Die Menge M soll minimal werden.
Mein Problem hat Ähnlichkeiten zum minimalen Vertex Cover, mit dem Unterschied, dass das Vertex Cover nach allen Kanten fragt und ich nur nach mindestens einer. Gibts für mein Problem vlt auch schon eine fertige Lösung, oder muss ich mir einen Algo vom Vertex Cover nehmen und an mein Problem anpassen?

MfG & Thx Bergmann.

jfheins - Mi 10.08.16 19:07

---

Ist das:

Zitat:

Für alle Knoten x aus V existiert mindestens eine Kante

richtig?

Also du möchtest ein Subset der Knoten, sodass jeder Knoten entweder 1. in diesem Subset enthalten ist oder 2. über min. eine Kante mit dem Subset verbunden ist?

Dann wäre es wohl die Suche nach dem kleinsten "dominating set [https://en.wikipedia.org/wiki/Dominating_set]"

Bergmann89 - Do 11.08.16 17:44

---

Hey,

ja das passt auf mein Problem. Ich guck mal ob ich da nen guten Algo finde. Danke erstmal :)

MfG Bergmann.

Bergmann89 - Di 27.09.16 22:10

---

Hey,

ich muss das Thema nochmal ausgraben. Ich hab jetzt einen Algo der mir das Minimale Dominating Set raus sucht. Das funktioniert auch ganz gut, ist aber noch nicht das Optimum. Ich geh folgendermaßen vor:
- Ich kenne für jeden Knoten die Anzahl an benachbarten, nich nicht dominierten Knoten die er abdecken würde, wenn er der Lösungsmenge hinzugefügt werden würde (der 'Gain' Wert).
- Suche die Knoten mit den kleinsten, identischen Gain-Werten
- Suche aus allen Nachbarn dieser Knoten den Knoten mit dem größten Gain-Wert
- Füge den Knoten der Ergebnis-Menge hinzu
Idee dahinter: Es wird nach Rand-Knoten gesucht (min. Gain) und dann der besste Nachbar dieses Knotens hinzugefügt. Damit wird der schlechte Knoten automatisch abgedeckt. So entstehen im Graph keine nicht-abgedeckten Bereiche die nur sehr wenige oder sogar nur einen Knoten enthalten.

Wie schon gesagt arbeitet der Algo sehr gut, aber es geht noch besser. Ich weiß das für meinen Graphen (52658 Konten; Dominating Set: 1220 Konten) noch ein kleiners Dominating Set existiert (1008 Knoten). Kann mir da einer von euch vlt nochmal nen Tipp geben wie man das Ganze noch verbessern kann? Ich hatte auch schon 4-5 Whitepapers zu verschiedenen Algos auf dem Tisch, aber die passen entweder nicht genau auf mein Graphen oder sind generisch und "erraten" die Lösung nur durch Zufallswerte bzw. Mutation. Ich brauch aber immer die selbe Lösung für einen gegebenen Graphen. Mein Algo ist die Kombination aus allem was ich aus den Whitepapern gelernt hab.

Ich bin für jeden Rat dankbar.

MfG & Thx bergmann.

jaenicke - Do 29.09.16 06:02

---

Du suchst aktuell den Nachbarn mit dem besten Gain zu einem Knoten mit einem schlechten Gain.
Was aber, wenn zwei solcher Knoten an einem gemeinsamen Knoten hängen?
Dann müsstest du den gemeinsamen statt des Knoten mit dem höchsten Gain nehmen. Zumindest dann, wenn einer der Nachbarn in der Menge schon drin ist. Dann wählst du aktuell ggf. einen zusätzlich aus.

Bergmann89 - Do 29.09.16 09:17

---

Gute Idee. Das probier ich heut Nachmittag mal aus. Danke.

Bergmann89 - Do 29.09.16 17:58

---

Hey,

ich habs grad ausprobiert, funktioniert leider nicht. Macht das Ergebnis sogar schlechter :/

MfG Bergmann