Autor Beitrag
Bergmann89
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: Mi 10.08.16 09:29 
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.

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 868
Erhaltene Danke: 144

Win7
VS 2013, VS2015
BeitragVerfasst: 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"
Bergmann89 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: 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.

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^
Bergmann89 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: 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.

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^
jaenicke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18727
Erhaltene Danke: 1628

W10 x64 (Chrome, IE11)
Delphi 10.2 Ent, Oxygene, C# (VS 2015), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: Do 29.09.16 09:17 
Gute Idee. Das probier ich heut Nachmittag mal aus. Danke.

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^
Bergmann89 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: Do 29.09.16 17:58 
Hey,

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

MfG Bergmann

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^