Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Maximaler Schnitt und Zielfunktionen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Maximaler Schnitt und Zielfunktionen
joey24
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 11.08.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-08-11


Hallo Community,
ist mein erster Post daher nimmt es mir bitte nicht übel wenn ich einige Formalien nicht richtig einhalte.

Ich befasse mich aktuell mit dem MaxCut Problem.
Die Zielfunktion ist recht trivial.
Meine Frage wäre, gibt es verschiedene Zielfunktionen, die sich auf das MaxCut Problem beziehen und welche Vorteile bringen sie ?

Bspw ist Goemans Williamson ein approximations Algorithmus, wäre es sinnvoll es hier umzuformulieren um eine andere Zielfunktion zu erhalten ?

Und ausserdem ist es nicht so dass MaxCut <=> MinCut mit negativen Gewichten ist ? Ist dann MinCut.. auch NP ?
Dann würden sich einige vers. Zielfunktionen ergeben.

LG
Joey



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6248
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-08-11


Hallo joey24,

willkommen auf dem Matheplaneten.

Beim Max-Cut- und beim Min-Cut-Problem werden stets nicht-negative Kantengewichte vorausgesetzt. Und: Das Min-Cut-Problem liegt in P.

Deine Frage nach den verschiedenen Zielfunktionen habe ich nicht verstanden.

Grüße
StrgAltEntf


[Verschoben aus Forum 'Numerik & Optimierung' in Forum 'Graphentheorie' von StrgAltEntf]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
joey24
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 11.08.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-08-11


Hi, vorweg danke für die Antwort.

Die eigentliche Problematik besteht darin , das MaxCut Problem in Quantum Computer zu formulieren, sprich die Zielfunktion als Hamiltonian.

Die Zielfunktion die hier normalerweise Verwendet wird lautet:
C(z) = 1/2 sum(1-z_i*z_j)

Nun ist die Aufgabe:
Verschiedene Zielfunktionen bereitzustellen, die sich auf das MaxCut Problem beziehen.

LG



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6248
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-08-11


Wahrscheinlich bin ich hier nicht der richtige Kompetenzträger.

Was ist denn z bzw. z_i?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6582
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-08-11


Sei $G=(V,E)$ der Graph.
Ich vermute, dass die Zielfunktion $1/2\sum_{i<j,\{i,j\}\in E}{1-z_iz_j}$ heißen soll.
Dabei nimmt $z_i$ den Wert $1$ an, wenn der Knoten $v_i$ in der Knotenmenge $A$ ist und den Wert $-1$, wenn der Knoten in der Menge $V-A$ ist.
Die Summe zählt also alle Kanten, bei denen ein Endknoten in $A$ ist und der andere nicht.

Eine andere mögliche Zielfunktion wäre $\sum_{\{i,j\}\in E}{(1-z_i)z_j}$, wobei die $z_i$ Werte aus $\{0,1\}$ annehmen.

Das Ganze kann man auch mit Kantengewichten versehen, also in etwa
$1/2\sum_{i<j,\{i,j\}\in E}{(1-z_iz_j)\cdot w_{ij}}$ .



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
joey24
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 11.08.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-08-11


Danke euch beiden :)

Genau so habe ich es gemeint :)

Die Frage die sich mir jetzt stellt ist, man könnte auch äquivalent z_j aus {0,1} nehmen und hätte die gleiche Zielfunktion.

Ausserdem, kann man die Bedingung dass die Klausel erfüllt ist auch auf {0,1} überführen und behaupten das es der Knoten in der Menge V-A enthalten ist z_i = 0 gesetzt wird ?

Alle guten Dinge sind drei :D daher noch die Frage, wären die drei Zielfunktionen die einzigen die man aus der MaxCut Problematik formulieren kann ?
LG



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6582
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-08-11


Ich verstehe nicht, worauf Du hinaus willst.
Du hast jetzt zwei verschiedene Modellierungen für das MAXCUT-Problem.
Die Variablen-Werte haben unterschiedliche Bedeutungen, es wird auf unterschiedliche Weise gezählt und die Summenformeln sehen unterschiedlich aus.
Das lässt sich sicher auch noch anders formulieren:
$\sum_{i\in V}{(1-z_i)\sum_{j\in N(i)}{z_j}}$, oder ...
Letzten Endes zählen aber alle Formeln das Gleiche: Die Zahl der Kanten zwischen eine irgendwie gekennzeichneten Menge A und dem Rest V-A.

Mir ist nicht klar, ob Du das suchst, oder eigentlich Varianten des MAXCUT-Problems mit _anderen_ Zielfunktionen oder zusätzlichen Bedingungen:
- gewichtetes MAXCUT
- maximaler Schnitt, der den Graph in genau zwei Zusammenhangskomponenten teilt
- MAXCUT auf speziellen Graphen
- ...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
joey24
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 11.08.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-08-11


Die eigentliche Frage lautet:

"Stelle verschiedene Zielfunktionen auf, die sich auf das MaxCut Problem beziehen:

    -Welche Aspekte tragen zum Erfolg bei?
    -Welche Aspekte halten sie für nützlich?
    -Können sie andere nützliche Zielfunktionen für das MaxCut Problem
     bereitstellen ? "


Da bin ich davon ausgegangen dass die Rede von Zielfunktionen ist und jetzt bin ich auch ein wenig verwirrt 🙄



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6582
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-08-11


Beziehen sich diese Fragen auf die Lösbarkeit mit Hilfe eines Quantencomputers? Leider kann ich in dem Fall nicht sagen, welche Aspekte dafür nützlich sind.

Eine interessante Gleichung ist mir noch eingefallen. Im Fall $z_i, z_j\in\{-1,+1\}$ gilt wegen $z_i^2=z_j^2=1$:
$1-z_i\cdot z_j = (z_i-z_j)^2/2$.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
joey24
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 11.08.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2020-08-12


Genau, mit Hilfe des Quantencomputers und in diesem Fall QAOA.
Danke für die interessante Gleichung :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
joey24 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]