Autor |
Beitrag |
Bergmann89
![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. offtopic star](./graphics/ranks/star_offtopic_full.png)
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)
|
Verfasst: 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
![jfheins hat insgesamt 76.6% On-Topic und 23.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jfheins hat insgesamt 76.6% On-Topic und 23.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jfheins hat insgesamt 76.6% On-Topic und 23.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jfheins hat insgesamt 76.6% On-Topic und 23.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jfheins hat insgesamt 76.6% On-Topic und 23.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jfheins hat insgesamt 76.6% On-Topic und 23.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jfheins hat insgesamt 76.6% On-Topic und 23.4% Off-Topic Beiträge geschrieben. offtopic star](./graphics/ranks/star_offtopic_full.png)
Beiträge: 918
Erhaltene Danke: 158
Win 10
VS 2013, VS2015
|
Verfasst: 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 Threadstarter](./graphics/viewtopic/threadstarter.png)
![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. offtopic star](./graphics/ranks/star_offtopic_full.png)
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)
|
Verfasst: 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 Threadstarter](./graphics/viewtopic/threadstarter.png)
![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. offtopic star](./graphics/ranks/star_offtopic_full.png)
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)
|
Verfasst: 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
![jaenicke hat insgesamt 87.9% On-Topic und 12.1% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jaenicke hat insgesamt 87.9% On-Topic und 12.1% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jaenicke hat insgesamt 87.9% On-Topic und 12.1% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jaenicke hat insgesamt 87.9% On-Topic und 12.1% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jaenicke hat insgesamt 87.9% On-Topic und 12.1% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jaenicke hat insgesamt 87.9% On-Topic und 12.1% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![jaenicke hat insgesamt 87.9% On-Topic und 12.1% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png)
Beiträge: 19285
Erhaltene Danke: 1743
W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: 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 Threadstarter](./graphics/viewtopic/threadstarter.png)
![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. offtopic star](./graphics/ranks/star_offtopic_full.png)
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)
|
Verfasst: 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 Threadstarter](./graphics/viewtopic/threadstarter.png)
![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Bergmann89 hat insgesamt 76.5% On-Topic und 23.5% Off-Topic Beiträge geschrieben. offtopic star](./graphics/ranks/star_offtopic_full.png)
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)
|
Verfasst: 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^^
|
|
|