Suchen eines Satzes mit fester Größe, dessen Mitglieder in der größten Anzahl anderer Sätze enthalten sind

Ich habe über ein Problem nachgedacht, das durch das Treffen mit einem Fremdsprachenprofessor für Anfänger am Goethe-Institut inspiriert wurde, der die fünf häufigsten Sprachen gelernt hat, die von Studenten gesprochen werden, um mit so vielen Studenten wie möglich zu kommunizieren.

Stellen Sie sich eine begrenzte Anzahl von Menschen vor, von denen jeder eine beliebige Anzahl von Sprachen spricht. Für die Zwecke des Problems werden wir einige der Dinge ignorieren, die Sprachen im wirklichen Leben komplex machen (zum Beispiel, dass Menschen mehrere Sprachen sprechen, aber auf verschiedenen Ebenen, dass Menschen, die eine Sprache verstehen, möglicherweise in der Lage sind, eng verwandte Sprachen zu verstehen Sprachen usw.).

Also zum Beispiel:

P ₁ spricht {English, German}.
P ₂ spricht {Spanish, Italian, French}.
P ₃ spricht {Mandarin, English}.
P ₁₀₀₀₀ spricht {Afrikaans, Swahili, English}und so weiter.

Ich schreibe ein Dokument, das ich übersetzt haben möchte, damit es von möglichst vielen Menschen verstanden wird. Leider ist mein Budget begrenzt und ich kann mir nur eine Übersetzung in N verschiedene Sprachen leisten.

Wie berechne ich für einen bestimmten Wert von N den optimalen Satz von N Sprachen, um die größte Anzahl von Personen aus der beabsichtigten Bevölkerung zu erreichen?

Das Problem klingt so, als könnte es leicht als Problem der Mengenlehre / Kombinatorik verallgemeinert werden, und ich bin mir sicher, dass jemand zuvor an so etwas gearbeitet hat. Ich würde gerne einen Blick auf die vorhandene Literatur werfen, weiß aber nicht, wie ich sie finden soll.

Gibt es einen Namen für diese Art von Problem? Wenn nicht, könnte es auf ein anderes bekanntes Problem reduziert werden?

terminology reference-request optimization combinatorics sets Kaum bekannt
quelle

Ich glaube, dass dies unter die Klasse der Probleme fällt, die als Optimierungsprobleme bezeichnet werden

MatthewRock

@ MatthewRock Ja. Wenn Sie mir einen Apfel geben und mich fragen: "Was ist das für ein Apfel?" und ich sagte: "Es ist eine Art Frucht", wie würden Sie reagieren?

Raphael

"Gibt es einen Namen für das Problem, ein Set mit einer festen Anzahl anderer Sets abzudecken?" könnte sein? Nun, ich würde fragen: "Gibt es einen Namen für Set Cover mit fester Lösungsgröße?" aber da Sie anscheinend nichts über Set Cover wussten, würde das keinen Sinn ergeben.

Raphael

@ Raphael Ich glaube, dass es umgekehrt ist; Ich gebe dir eine Frucht und frage, was es ist. Sie sagen mir, dass es "eine Art Apfel" ist oder (wahrscheinlicher) "es wächst wahrscheinlich auf einem Baum". Sie haben meine Frage nicht beantwortet, aber vielleicht könnte es mir irgendwie helfen - also ein Kommentar, keine Antwort. Schlimmster Fall: Ich habe gerade einen nutzlosen Kommentar gepostet. Ein etwas realistischer Fall: Jemand lernt etwas Neues.

Matthew Rock

Antworten:

Ich glaube, Ihr Problem ist eine direkte Instanz des NP-harten Problems der maximalen Abdeckung, das mit Set Cover zusammenhängt.

Aus Wikipedia, Maximum Coverage Problem :

Als Eingabe erhalten Sie mehrere Sätze und eine Zahl k . Die Sets können einige Elemente gemeinsam haben. Sie müssen höchstens k dieser Sätze so auswählen, dass die maximale Anzahl von Elementen abgedeckt wird, dh die Vereinigung der ausgewählten Sätze hat die maximale Größe.

In Ihrem Fall gibt es also für jede Sprache einen Satz mit einer Kardinalität, die der Anzahl der Schüler entspricht, die diese Sprache sprechen. Die Eingabe ist die Anzahl N der maximalen Anzahl von Übersetzungen.

Soeholm
quelle

Geschafft. Willkommen auf der Seite!

David Richerby

Wenn wir die Anzahl der Muttersprachler im Moment ignorieren, ist Ihr Problem Set Cover - Sie fragen, ob es möglich ist, alle Sprachen mit höchstens Übersetzern abzudecken . $k$

Das Hinzufügen von Gewichten - die Anzahl der Muttersprachler jeder Sprache - fügt einen Optimierungsmodus hinzu. Wir decken möglicherweise nur einige Sprachen ab, möchten jedoch ein maximales Gesamtgewicht. Das ist sicherlich nicht einfacher; Die Reduzierung von Set Cover selbst ist trivial.

Ihr Problem ist also NP-schwer.

Da es auch einfach ist, es mit ganzzahliger Programmierung auszudrücken, können wir daraus schließen, dass es NP-vollständig ist.

Bezüglich der Namen kenne ich keinen. "Weighted Set Cover" wird bereits für die Variante verwendet, bei der Sets Kosten verursachen, aber ich würde etwas in dieser Richtung erfinden. Vielleicht "Maximum-Weight Set Cover".

Raphael
quelle

Sie müssen Muttersprachler nicht ignorieren: Jede interessierende Person hat eine Liste der Sprachen, die sie spricht, und eine davon ist vermutlich ihre Muttersprache. Außerdem scheinen Sie im entgegengesetzten Sinne zu optimieren, wie es die Frage stellt. Sie beantworten die Frage: "Was ist die kleinste Anzahl von Übersetzungen, die jeder verstehen kann?"; Die Frage lautet: "Ich habe ein festes Übersetzungsbudget: In welche Sprachen sollte ich übersetzen, um die Anzahl der Personen zu maximieren, die verstehen können?"

David Richerby

Tatsächlich liefert dies immer noch einen einfacheren Beweis für die NP- Härte als meine. Sie können die Deckungsmenge lösen, indem Sie die binäre Suche verwenden, um den Mindestwert von (die Anzahl der durchgeführten Übersetzungen) so zu ermitteln, dass alle Personen erreicht werden.

k

$k$

David Richerby

@ DavidRicherby Ich meinte Leser . Es bleibt implizit in der Frage, aber aus der Beschreibung, die ich zusammengestellt habe, geht hervor, dass wir Daten darüber haben, wie viele Menschen welche Sprache verstehen können, um genau zu optimieren, wie Sie sagen. Ich habe anscheinend leicht zu missverstehen formuliert?

Raphael

@ DavidRicherby Es kann sein, dass wir nicht alle innerhalb des Budgets erreichen können, was natürlich der interessante Fall ist. Hier weicht das Problem von der normalen Set-Abdeckung ab.

Raphael