Antworte auf:  Maximaler Schnitt und Zielfunktionen von joey24
Forum:  Graphentheorie, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Herkunft:
 Beitrag No.9, eingetragen 2020-08-12 18:49    [Diesen Beitrag zitieren]

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


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6610
Herkunft: Niedersachsen
 Beitrag No.8, eingetragen 2020-08-11 21:10    [Diesen Beitrag zitieren]

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$.


joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Herkunft:
 Beitrag No.7, eingetragen 2020-08-11 16:15    [Diesen Beitrag zitieren]

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 🙄


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6610
Herkunft: Niedersachsen
 Beitrag No.6, eingetragen 2020-08-11 15:52    [Diesen Beitrag zitieren]

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
- ...


joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Herkunft:
 Beitrag No.5, eingetragen 2020-08-11 14:11    [Diesen Beitrag zitieren]

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


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6610
Herkunft: Niedersachsen
 Beitrag No.4, eingetragen 2020-08-11 13:23    [Diesen Beitrag zitieren]

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}}$ .


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6408
Herkunft: Milchstraße
 Beitrag No.3, eingetragen 2020-08-11 12:20    [Diesen Beitrag zitieren]

Wahrscheinlich bin ich hier nicht der richtige Kompetenzträger.

Was ist denn z bzw. z_i?


joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Herkunft:
 Beitrag No.2, eingetragen 2020-08-11 11:30    [Diesen Beitrag zitieren]

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


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6408
Herkunft: Milchstraße
 Beitrag No.1, eingetragen 2020-08-11 11:24    [Diesen Beitrag zitieren]

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]


joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Herkunft:
 Themenstart: 2020-08-11 10:50    [Diesen Beitrag zitieren]

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


 
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]