Mindestanzahl von Einkaufstouren für eine Gruppe von Personen, um Geschenke für einander zu kaufen

10

Wir haben eine Gruppe von $n$ Leuten. Wir erhalten eine Liste, wer innerhalb der Gruppe Geschenke für wen kaufen muss. Jede Person muss möglicherweise eine beliebige Anzahl von Geschenken kaufen / erhalten oder möglicherweise gar keine. Bei einem Einkaufsbummel reist eine Untergruppe der Personen zusammen zum selben Geschäft und kauft Geschenke für alle, die nicht im Geschäft anwesend sind. Sie kaufen möglicherweise keine Geschenke für jemand anderen auf demselben Einkaufsbummel, da dies dann keine Überraschung wäre. Eine Person kann mehrere Einkaufstouren unternehmen. Wir möchten die Gesamtzahl der Einkaufstouren minimieren, die jeder benötigt, um alle benötigten Geschenke zu kaufen.

Betrachten Sie als Beispiel den Fall, in dem 5 Personen anwesend sind und jeder Geschenke für jede andere Person in der Gruppe kaufen muss. Lassen Sie die Personen von 1 bis 5 nummerieren. Dies kann in 4 Einkaufstouren erfolgen, wie gezeigt:

Reise 1: 1, 2, 3 einkaufen gehen
Reise 2: 1, 4, 5 einkaufen gehen
Reise 3: 2, 4 einkaufen gehen
Trip 4: 3, 5 einkaufen gehen

Wie würde ich dieses Problem lösen? Es ist offensichtlich, dass die Eingabe durch ein gerichtetes Diagramm dargestellt werden kann, aber ich weiß nicht, wohin ich von dort aus gehen soll. Jemand hat das Problem mit dem Biclique-Cover angesprochen , aber obwohl es ähnlich ist, beantwortet es diese Frage nicht.

Wir können uns die Eingabe als einen gerichteten Graphen auf Eckpunkten vorstellen , wobei die Kante bedeutet, dass die Person ein Geschenk für die Person kaufen muss . Das Ziel ist es, eine Menge von Bicliques so zu finden, dass minimal ist und die Kantenmenge des Graphen eine Teilmenge von $G$ $n$ $(u,v)$ $u$ $v$ $(S_1,T_1),\dots,(S_k,T_k)$ $k$ $E$ . Bei der Erweiterung der Definition von Bicliques auf einen gerichteten Graphen enthält ein Biclique nur Kanten, die auf abbilden. Dies unterscheidet sich vom Biclique-Cover-Problem darin, dass nicht jedes Biclique ein Untergraph von (wir benötigen nicht für jedes ). $\cup_i (S_i \times T_i)$ $(S_i,T_i)$ $S_i$ $T_i$ $G$ $S_i \times T_i \subseteq E$ $i$

Insbesondere werde ich eine Antwort akzeptieren, die entweder:

Zeigt, dass dieses Problem NP-schwer ist oder
Präsentiert einen Polynomzeitalgorithmus, der diese Frage genau beantwortet (keine Approximanten oder Obergrenzen)

Für die Aufzeichnung, ich habe dieses Problem nirgendwo gesehen, ich wundere mich nur über meine eigene Neugier.

algorithms graph-theory set-cover Riley
quelle

2

Dieses Problem ist NP-schwer . Um dies zu zeigen, werde ich dieses (Optimierungs-) Problem zunächst in ein Entscheidungsproblem umformulieren. Dann formuliere ich dieses Problem in ein äquivalentes um, aus dem es ziemlich einfach ist, eine Reduktion aus dem Farbproblem zu erhalten, das für jedes NP-schwer ist . $k$ $k\geq 3$

Eine kurze Formulierung des Problems lautet wie folgt:

Finden Sie bei Personen und einem Diagramm , das ihre "Geschenk" -Beziehungen kodiert, die Mindestanzahl der erforderlichen Reisen, damit alle Geschenke gekauft werden können, ohne Überraschungen zu ruinieren. $n$ $G$

Dies ist jedoch ein Optimierungsproblem. Die Klasse NP wird normalerweise für Entscheidungsprobleme definiert (wobei die Antwort auf jede Instanz entweder JA oder NEIN lautet). Eine Entscheidungsvariante davon ist:

Ist es bei Personen und einem Diagramm , das ihre "Geschenk" -Relationen und eine ganze Zahl codiert , höchstens Reisen ausreichend, um alle Geschenke zu kaufen, ohne irgendwelche Überraschungen zu ruinieren? $n$ $G$ $t$ $t$

Ich definiere das Problem, eine richtig gerichtete Mehrfachfärbung $t$ eines Graphen als eine Mehrfarbenfunktion die richtig ist , wobei eine Menge von 'Farben' ist ( dh ) und ist die Potenzmenge von (dh die Menge aller Teilmengen von $G=(V,E)$ $c:V\rightarrow \mathcal{P}(C)$ $C$ $t$ $|C|=t$ $\mathcal{P}(C)$ $C$ $C$ $(u\rightarrow v)\in E$ $c(u) \not\subseteq c(v)$

Ich behaupte, dass das Problem der Einkaufstour dem Problem entspricht, die Existenz einer gerichteten Mehrfachfärbung $t$ desselben Graphen . $G$

Beweis : Wenn wir eine richtige gerichtet haben -multicoloring für , wo wir die Farben , so dass umbenennen dann betrachten die Folge von stellt , wo ein Scheitelpunkt geht in Reise genau dann einkaufen, wenn . Dann haben wir für jede Kante , dass es eine Reise so dass und , da . Daher sind die Fahrten $t$ $c$ $G$ $C = \{1,\ldots, t\}$ $t$ $T_1,\ldots, T_t$ $v$ $T_i$ $i\in c(v)$ $(u\rightarrow v)\in E$ $T_i$ $u\in T_i$ $v\notin T_i$ $c(u) \not\subseteq c(v)$ $T_i$ sind ausreichend, um alle Geschenke zu kaufen.

Wenn wir eine Folge von , konstruieren Sie die Mehrfarbenfunktion auf der so, dass . Dann wird für jede Kante existiert eine Reise so dass und (da ein Geschenk kaufen auf einige Fahrt), was bedeutet , dass und , also . $T_1,\ldots, T_t$ $c$ $C=\{1,\ldots, t\}$ $c(u) = \{ i \in \mathbb{N} | u \in T_i\}$ $(u\rightarrow v)\in E$ $T_i$ $u\in T_i$ $v\notin T_i$ $u$ $v$ $i\in c(u)$ $i\notin c(v)$ $c(u) \not\subseteq c(v)$ $\square$

Das Finden einer richtigen gerichteten Mehrfachfärbung ist im Grunde eine seltsame Neuformulierung eines bestimmten Falles der Färbung. Daher kann ich eine Polynomzeitverkürzung aus dem -Farbproblem zeigen: Wenn ein ungerichteter Graph , transformiere zuerst diesen Graphen in den gerichteter Graph , so dass und genau dann, wenn oder ( Mit anderen Worten, wir ändern ungerichtete Kanten in zwei gerichtete Kanten. $t$ $k$ $\binom{t}{\lfloor t/2 \rfloor}$ $G' = (V',E')$ $G=(V,E)$ $V=V'$ $(u\rightarrow v)\in E$ $(u,v)\in E'$ $(v,u)\in E'$

Betrachten Sie eine größte Menge , so dass es , kein gibt , so dass . Die Menge aller Teilmengen von der Größe , wobeiist so ein Satz. Daher ist die maximale Größe einer solchen Teilmenge . $K\subset \mathcal{P}(C)$ $a,b\in K$ $a\neq b$ $a\subset b$ $C$ $\lfloor t/2\rfloor$ $t=|C|$ $\binom{t}{\lfloor t/2 \rfloor}$

Wenn für eine richtige Mehrfachfärbung existiert , gibt es eine richtige Färbung, die nicht mehr als ungleiche Elemente aus (*) verwendet. Dies ist also eine gültige -Farbe für . $t$ $G$ $\binom{t}{\lfloor t/2 \rfloor}$ $\mathcal{P}(C)\$ $\binom{t}{\lfloor t/2 \rfloor}$ $G'$

Wenn für eine richtige -Farbe existiert , dann existiert eine Menge , , so dass und es gibt kein , , so dass . Also, hat ein richtigen gerichtet -multicoloring. $\binom{t}{\lfloor t/2 \rfloor}$ $G'$ $K\subset \mathcal{P}(C)$ $|C|=t$ $|K| \geq \binom{t}{\lfloor t/2 \rfloor}$ $a,b\in K$ $a\neq b$ $a\subset b$ $G$ $t$

Daher ist dies eine gültige Polynomzeitverkürzung von -Farbe auf das gegenwärtige Einkaufsproblem mit Reisen, was bedeutet, dass das gegenwärtige Einkaufsproblem NP-schwer ist. Beachten Sie, dass das derzeitige Einkaufsproblem NP-vollständig ist, da wir leicht überprüfen können, ob eine bestimmte Liste von höchstens Reisen es uns ermöglicht, alle Geschenke zu kaufen, ohne Überraschungen zu ruinieren. $\binom{t}{\lfloor t/2 \rfloor}$ $t$ $t$

(*): Wenn einige Mehrfachfarben mehr Farbsätze verwenden als eine maximale Mehrfachfärbung ohne Untermenge , können wir so umbenennen, dass Es ist eine Obermenge von . bleibt korrekt, da keines der Elemente aus neben einem anderen Element als ein Problem darstellt und keines der Farbsätze in nebeneinander liegt das Original . Ohne Verlust der Allgemeinheit können wir also annehmen . $\mathcal{C}$ $\mathcal{C}^*$ $\mathcal{C}$ $\mathcal{C}^*$ $\mathcal C$ $\mathcal{C}^*$ $\mathcal{C}^*$ $\mathcal{C}$ $\mathcal{C}^* \subset \mathcal{C}$

Beachten Sie dann, dass das Umbenennen von in eine beliebige Teilmenge von die Kanten zwischen den Knoten von Farbsätzen nicht ruiniert , da keine Elemente enthält, die eine Teilmenge eines anderen sind. Sie müssen nur noch sicherstellen, dass die Kanten zwischen und die Farbgebung nicht "ruinieren". $\mathcal{C}\setminus \mathcal{C}^*$ $\mathcal{C}^*$ $\mathcal{C}\setminus \mathcal{C}^*$ $\mathcal{C}^*$ $\mathcal{C}\setminus \mathcal{C}^*$ $\mathcal{C}^*$

Betrachten Sie die folgende Beziehung für die Farbsätze in : Zwei Farbsätze und sind genau dann verbunden, wenn ein Paar von Eckpunkten so dass hat farb gesetzt und Farbsatz und . Diese Beziehung kann durch den ungerichteten Graphen . $R$ $\mathcal{C}\cup \mathcal{C}^*$ $A$ $B$ $a,b$ $a$ $A$ $b$ $B$ $(a,b)\in E$ $\mathcal G = (\mathcal{C}\cup \mathcal{C}^*, R)$

Erstens können wir 'reduzieren', indem wir jedes Paar, das in keine Kante hat, durch einen einzelnen Farbsatz ersetzen . Die Färbung bleibt korrekt, da das Ändern von zwei Farbsätzen, die überhaupt nicht benachbart sind, in dieselbe Farbe keine ungültigen Kanten einführt. Infolgedessen haben wir auf ein vollständiges Diagramm reduziert . $\mathcal{C}\setminus \mathcal{C}^*$ $\mathcal G$ $\mathcal G$

Dies bedeutet, dass wenn weniger oder gleich viele Farbsätze hat wieist die gewünschte Färbung vorhanden. Andernfalls gibt es überhaupt keine richtige Mehrfachfärbung, da eine größte 'Nicht-Teilmenge' ist, sodass wir diese Clique nicht färben können. Daher besteht notwendigerweise die erforderliche Mehrfachfärbung. $\mathcal G$ $|\mathcal{C}^*|$ $\mathcal{C}^*$

Da der vollständige Graph auf Knoten genau dann farbfähig ist, wenn wir mindestens Farben haben, haben wir die Möglichkeit , dass Personen in Reisen genau dann Geschenke für einander einkaufen können, wenn . Dies bedeutet insbesondere, dass bei nur Fahrten ausreichen. Wenn weniger Geschenke zu kaufen sind, werden keine weiteren Reisen benötigt, sodass dies eine allgemeine Obergrenze für jede Lösung ist. $n$ $K_n$ $n$ $n$ $t$ $\binom{t}{\lfloor t/2 \rfloor} \geq n$ $n\leq 12870$ $16$

Unten ist meine frühere 'Antwort', die einen heuristischen Algorithmus liefert, der nicht garantiert, dass das Optimum erreicht wird, sondern in Polynomzeit berechnet werden kann.

Eine andere Möglichkeit, dieses Problem zu formulieren, besteht darin, eine Abdeckung von zweigeteilten Graphen auf den Partitionen für einen gerichteten Graphen mit Knoten zu finden , so dass die Anzahl der Partitionen (dh Auslösungen), hier , minimal ist. $C = \{(S_1,T_1), \ldots, (S_m,T_m)\}$ $(S_i,T_i)$ $G$ $n$ $m$

Erstens einige Beobachtungen, die teilweise aus anderen Antworten stammen:

Die gierige Strategie, bei der wir ein mit einem zweigeteilten Graphen auswählen bei dem die Anzahl der mit gemeinsamen Kanten maximal ist, führt nicht zu einer optimalen Lösung (Ein starkes Gegenbeispiel ist der vollständige Graph mit Knoten). wo diese Strategie fehlschlägt, egal welcher maximale zweigliedrige Graph gewählt wird.). $(S_i,T_i)$ $G$ $6$
Die gierige Strategie ist für beliebige azyklische Graphen nicht optimal. Betrachten Sie den folgenden Graphen: Sowohl für als auch für der zweigeteilte Graph Kanten, aber nur ist optimal. $S_i = \{3,5,6\}$ $S_i=\{1,3,6\}$ $4$ $\{3,5,6\}$
Jeder (optimale) Greedy-Algorithmus kann die Größe der ausgewählten Partition nicht der Anzahl der von der Partition "entfernten" Zyklen ( beliebiger Größe) vorziehen . Um dies zu sehen, betrachten Sie das Diagramm mit Knoten, wobei es einen Zyklus von Knoten gibt und jeder Knoten im Zyklus zusätzliche ausgehende Kanten zu zusätzlichen Knoten , die keine ausgehenden Kanten haben (siehe Abbildung unten für ein Beispiel mit ). Eine gierige Wahl, die es vorzieht, die Anzahl der Kanten über Zyklen der Länge zu maximieren, sendet alle Eckpunkte im Zyklus auf der ersten Fahrt. Dies ist nicht optimal, da dadurch keine Kanten des Zyklus entfernt werden und einfach ignoriert $n+2$ $n$ $2$ $2$ $A,B$ $n=4$ $n$ $A,B$ Wenn Sie alle Kanten aus dem Zyklus entfernen, werden auch alle Kanten in Richtung . Daher ist jede gierige Wahl, die die Größe der Partition dem Entfernen eines Zyklus vorzieht, nicht optimal. $A,B$

Basierend auf diesen Beobachtungen schlage ich die folgende gierige Wahl vor: Wählen Sie so, dass die Anzahl der Zyklen, die diese Reise von 'entfernt', maximal ist, und wählen Sie im Fall von Bindungen eine Partition mit maximaler Überlappung mit unter sie (dh schauen Sie sich die Kanten nicht auf Zyklen). $(S_i, T_i)$ $G$ $G$

Da sich dieser Algorithmus nicht von der "grundlegenden" Greedy-Strategie für azyklische Graphen unterscheidet (Entfernen einer maximalen Anzahl von Kanten bei jeder Fahrt), ist dieser Greedy-Algorithmus daher nicht optimal. Die Intuition, Zyklen zu entfernen, ist jedoch immer noch sinnvoll und stellt eine Verbesserung gegenüber der grundlegenden Strategie der Gier dar, sodass es sich um eine anständige Heuristik handeln könnte.

Diskrete Eidechse
quelle

1

Sie geben an, "Wenn für eine Mehrfachfärbung existiert , verwendet diese Färbung nicht mehr als ungleiche Elemente aus ". Diese Aussage ist falsch. In dem trivialen Beispiel von 3 getrennten Knoten existiert ein 2-mehrfarbiges , wobei . Dies ist eine richtige 2-Mehrfarbigkeit, die mehr als verschiedene Elemente verwendet. Wollten Sie sagen "Wenn für eine Mehrfachfärbung existiert , verwendet eine solche Färbung nicht mehr als

t

$t$

G

$G$

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2 \rfloor}$

P (C)

$\mathcal{P}(C)$

a, b, c

$a,b,c$

v

$v$

v (a) = {1}, v (b) = {2}, v (c) = {1, 2}

$v(a)=\{1\},v(b)=\{2\},v(c)=\{1,2\}$

(\binom{2}{1}) = 2

$\binom{2}{1}=2$

t

$t$

G

$G$

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2 \rfloor}$ ungleiche Elemente aus "?

P (C)

$\mathcal{P}(C)$

Riley

Genau das habe ich gemeint. Eine andere Sichtweise ist, dass wenn es sich um eine minimale t-Mehrfarbigkeit handelt (dh dieses ist nicht -multicolorable), genau -Elemente verwendet . Das von Ihnen angegebene Beispiel ist eindeutig kein Gegenbeispiel für die korrekte Neuformulierung.

G

$G$

(t - 1)

$(t-1)$

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2 \rfloor}$

Diskrete Eidechse

Nein, warte. Es werden nicht genau -Elemente verwendet, sondern höchstens.

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2\rfloor}$

Diskrete Eidechse

Ich kann verstehen, wie diese überarbeitete Aussage intuitiv Sinn macht, aber können Sie es beweisen? Vielleicht könnten Sie irgendwie zeigen, dass jede t-Multicoloring "verbessert" werden kann, so dass alle Multicolors Elemente einer Menge , die die Anforderungen der Größe erfüllen, und dass es kein so dass .

K

$K$

a, b \in K

$a,b\in K$

a \subset b

$a\subset b$

Riley

@ Riley Ich bin mir nicht sicher, was du meinst. Welche Aussage soll ich ausarbeiten? Ich habe meine Antwort so aktualisiert, dass sie angibt, was Ihr ursprünglicher Kommentar vorgeschlagen hat. Der Rest des Beweises bleibt unberührt. In Bezug auf die Beziehung zwischen dem Problem der Mehrfach- und Originalfarbe besteht die Schlüsselidee darin, dass die Mehrfachfärbung so gesehen werden kann, dass sie keine benachbarten "Teilmengen" aufweist. Da die größte 'nicht paarweise Teilmenge' von die Größe , können wir diese Menge genauso gut als Farbsatz betrachten und erhalten das Farbproblem.

P (C)

$\mathcal{P}(C)$

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2\rfloor}$

Diskrete Eidechse

2

Ich kann sehen, wie Sie dieses Problem auf Graph Coloring reduzieren können , wodurch Sie ein Werkzeug zur Lösung des Problems erhalten (für kleine Fälle!), Aber noch nicht, wie Sie es in die andere Richtung reduzieren können (wodurch die NP-Härte hergestellt wird).

Die Grundidee besteht darin, ein Diagramm zu erstellen, das für jeden Einkauf einen Scheitelpunkt und eine Kante zwischen zwei Käufen enthält, die nicht auf derselben Reise erfolgen können. Wir versuchen dann, die Einkäufe in die kleinstmögliche Anzahl von Gruppen ("Reisen") zu gruppieren, so dass keine zwei Einkäufe in derselben Gruppe in Konflikt geraten würden. Insbesondere wenn der ursprünglich gerichtete Graph ist, in dem eine Kante angibt, dass die Person der Person ein Geschenk kaufen muss , dann erstellen Sie einen ungerichteten Graphen in dem sich ein Scheitelpunkt befindet für jede Kante in und eine (ungerichtete) Kante wann immer $G = (V, E)$ $uv$ $u$ $v$ $H = (X, Y)$ $x_{uv}$ $uv$ $G$ $x_{uv}x_{vw}$ $uv$ und sind beide (gerichtet) Kanten in (wenn einige kauft Geschenk während einer Reise, dann kann niemand kaufen während dieser gleichen Reise ein Geschenk). Eine Scheitelpunktfärbung von ist eine Aufteilung der erforderlichen Käufe (Scheitelpunkte in ) in Fahrten (Farben), die nicht in Konflikt stehen (eine Kante teilen), und eine Scheitelpunktfärbung mit minimaler Größe erfordert die geringstmöglichen Fahrten. $vw$ $G$ $v$ $w$ $v$ $H$ $H$

Es könnte möglich sein, in die andere Richtung zu gehen (die Graphfärbung oder ein anderes NP-hartes Problem auf Ihr Problem zu reduzieren und dadurch seine NP-Härte festzustellen), indem eine Reduzierung von 3SAT an die Graphfärbung angepasst wird (wie z. detailliert auf S. 10 von Jeff Ericksons Notizen ), aber ich habe es selbst nicht versucht.

j_random_hacker
quelle

Diese Antwort ist brillant; es ist genau das, wonach ich gesucht habe. Bei der Analyse der zeitlichen Komplexität dieses Algorithmus gibt es höchstens Eckpunkte (Geschenke) und Kanten. Wenn ich einen Algorithmus zum Färben von Graphen nachschlage, finde ich nur für einen Graphen mit Eckpunkten. Gibt es in diesem Fall einen effizienteren Algorithmus, weil die Anzahl der Kanten durch ein Polynom begrenzt ist?

n^{2} - n

$n^2-n$

\frac{(2 n - 3) (n^{2} - n)}{2}

$\frac{(2n-3)(n^2-n)}{2}$

O (2^{n} n)

$O(2^nn)$

n

$n$

Riley

1

@Riley Wahrscheinlich nicht, wenn man die Färbbarkeit entscheidet, ist für einen Graphen mit maximalem Grad bereits NP-hart. In diesen [Vorlesungsskripten] (www-sop.inria.fr/members/Frederic.Havet/Cours/coloration.pdf) finden Sie eine Reduzierung von 3-SAT auf Diagramme mit maximalem Grad 3.

k

$k$

k \geq 3

$k\geq 3$

3

$3$

Diskrete Eidechse

@ Diskrete Eidechse: Wo in diesen Vorlesungsunterlagen geben sie eine solche Reduzierung?

Warum wird diese Antwort akzeptiert? Soweit ich sehen kann, zeigt es weder eine NP-Härte noch einen "optimalsten" Algorithmus oder sogar einen effizienten Algorithmus.

Diskrete Eidechse

1

@ Discretelizard Okay. Ich dachte nicht, dass die Frage implizierte, dass ich nach einem P-Zeit-Algorithmus suche, insbesondere angesichts der Möglichkeit, dass dieses Problem NP-schwer ist. Aber ich kann diesen Punkt in der ursprünglichen Frage deutlicher machen. Ich werde diese Antwort als richtig markieren und eine Prämie von 100 Punkten hinzufügen (es stellt sich heraus, dass die zweite 100 sein muss, wenn dieselbe Frage gestellt wird, aber ich bin bereit, sie anzubieten, weil es sich nur um imaginäre Internetpunkte handelt, oder? :)) noch einmal an alle, die entweder zeigen können, dass dieses Problem NP-schwer ist, oder einen polynomiellen Zeitalgorithmus finden, der es löst.

Riley

0

Es ist die Art von Problem, bei dem ich mir große Sorgen machen würde, wenn mein Chef mich bitten würde, einen Algorithmus zu implementieren, der garantiert in angemessener Zeit eine optimale Lösung findet.

So finden Sie eine nicht unbedingt optimale Lösung: Bei einer bestimmten Anzahl von Personen und Geschenken können wir zählen, wie viele Geschenke eine Gruppe von Personen auf einem Einkaufsbummel kaufen kann. Beginnen Sie also mit einer leeren Gruppe (die 0 Geschenke kaufen kann). Bestimmen Sie für jede Person, die nicht zur Gruppe gehört, wie viele Geschenke gekauft werden können, wenn diese Person der Gruppe hinzugefügt wird. Wenn es eine Person gibt, die wir hinzufügen können, ohne die Anzahl der Geschenke zu verringern, wählen Sie nach dem Zufallsprinzip eine aus, die die Anzahl der gekauften Geschenke um den Höchstbetrag erhöht, bis durch Hinzufügen einer Person die Anzahl der gekauften Geschenke verringert wird. Machen Sie dann diesen Einkaufsbummel und beginnen Sie von vorne, bis alle Geschenke gekauft sind.

Ich würde es ein paar Mal wiederholen und "zufällig" verschiedene Leute auswählen, falls dies eine bessere Lösung findet.

In dem Beispiel, in dem fünf Personen ein Geschenk für einander kaufen müssen, findet dies in vier Fahrten eine optimale Lösung. Wenn wir einer Reise keine Personen hinzufügen würden, bei denen die Anzahl der Geschenke unverändert bleibt, ohne sie zu verbessern, hätten wir fünf Reisen. Und 6 Personen benötigen 5 Fahrten.

gnasher729
quelle

Mit anderen Worten, Sie wählen gierig Einkaufstouren entsprechend der Anzahl der gekauften Geschenke aus. Können Sie nachweisen, dass dieses Verfahren zwangsläufig zu einer möglichst geringen Anzahl von Einkaufstouren führt? Wenn ja, haben Sie das Beispiel von 6 Personen falsch durchgearbeitet. 6 Personen benötigen nur 4 Einkaufstouren: .

{{1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6}}

$\{\{1,2,3\},\{1,4,5\},\{2,4,6\},\{3,5,6\}\}$

Riley

Absolut kein Beweis. Gieriger Algorithmus + verschiedene zufällige Entscheidungen zu treffen würde Ihre Chancen ein wenig verbessern, würde aber nicht 4 Fahrten machen.

Gnasher729

Ich habe die Behauptung getestet, dass das Problem gierig ist und fehlschlägt. Selbst wenn Sie jeden möglichen Einkaufsbummel testen, anstatt nacheinander Personen hinzuzufügen, erhalten Sie dennoch 5 Reisen: . Der gierige Ansatz möchte, dass der zweite Einkaufsbummel 9 Geschenke kauft, aber in der optimalen Lösung kauft der zweite Einkaufsbummel 8 Geschenke (vorausgesetzt, er erfolgt in der oben angegebenen Reihenfolge).

{{1, 2, 3}, {4, 5, 6}, {1, 4}, {2, 5}, {3, 6}}

$\{\{1,2,3\},\{4,5,6\},\{1,4\},\{2,5\},\{3,6\}\}$

Riley

Tatsächlich löst der gierige Ansatz nicht einmal den Fall von 5 Personen in 4 Einkaufstouren: .

{{1, 2}, {3, 4}, {5}, {1, 3}, {2, 4}}

$\{\{1,2\},\{3,4\},\{5\},\{1,3\},\{2,4\}\}$

Riley

-1

Angenommen, Sie bestellen die Personen basierend darauf, von wem sie (Eltern) empfangen und wem sie (Kind) geben. Da jeder ein Geschenk gibt und ein Geschenk erhält, ist die Eltern-Kind-Funktion eins zu eins.

Sie möchten niemals Eltern und Kind in dieselbe Gruppe einordnen. Sie beginnen mit einer zufälligen Person und ordnen alle entsprechend an, also usw. Sie ordnen alle in eine Gruppe und alle in eine andere Gruppe ein. Für die letzte Person ist , Sie möchten also nicht, dass diese Person mit in derselben Gruppe ist . Wenn ist, ist dies kein Problem. Andernfalls benötigen Sie eine zusätzliche Gruppe, die im einfachsten Fall nur kann. $p_1$ $child(p_1)=p_2$ $p_{odd}$ $p_{even}$ $p_n=parent(p_1)$ $p_1$ $n$ $p_n$

Dieser Algorithmus setzt voraus, dass alle verbunden sind. Das muss aber nicht so sein. Wenn es mehrere getrennte Zyklen gibt, wenn irgendwann wobei , dann beenden Sie diesen Kreis und beginnen mit einem neuen, der demselben Algorithmus folgt. Solange Sie nicht die Chancen und Ereignisse desselben Zyklus zusammenführen, können Sie getrennte Zyklen zusammenführen. $p_k=parent(p_1)$ $k!=n$

Dieser Algorithmus endet mit höchstens 2 Runden (für gerade ) und 3 Runden (für ungerade ). $n$ $n$

ilke444
quelle

Es scheint, dass dieser Ansatz das Problem nur für den Fall löst, dass jeder ein Geschenk gibt und ein Geschenk erhält, dh wenn der Graph eine Permutation ist. Ich bin mir nicht sicher, ob die Frage nur zu diesem speziellen Fall gestellt werden sollte - mal sehen, was das OP dazu zu sagen hat.

DW

Das stimmt, meine Lösung ist für einen Unterfall des Problems, bei dem .

\forall i, f a n_i n (v_{i}) = f a n_o u t (v_{i}) = 1

$\forall i, fan\_in(v_i)=fan\_out(v_i)=1$

Ilke444

Ja, ich habe nicht speziell nach Permutationen gefragt. Bitte lesen Sie die aktualisierte Frage, in der ich einige Dinge kläre.

Riley

Mindestanzahl von Einkaufstouren für eine Gruppe von Personen, um Geschenke für einander zu kaufen

Antworten: