Günstige Online-Auswahl mit gewichteten Vergleichen

Angenommen, wir möchten das kleinste Element einer Menge , deren Elemente von bis indiziert sind . Wir haben keinen Zugriff auf die Werte dieser Elemente, aber wir können zwei beliebige Elemente von um festzustellen, welches kleiner ist. Für alle Indizes und sind Kosten , um das te und das te Element von zu vergleichen . Die vollständige Kostenmatrix wird uns vorab mitgeteilt. $S$ $1$ $n$ $S$ $i$ $j$ $C_{i,j}$ $i$ $j$ $S$ $C_{i,j}$

Es ist bekannt, dass Vergleiche notwendig und ausreichend sind, um das kleinste Element von . Da jedoch jeder Vergleich unterschiedliche Kosten verursachen kann, möchten wir auch die Gesamtkosten der Vergleiche so gering wie möglich halten. $n-1$ $S$

Gibt es einen Online-Algorithmus, der eine Folge von Vergleichen kleiner Gesamtkosten findet, die das kleinste Element von ? $S$ Es gibt keinen Online-Algorithmus, der die Menge der Vergleiche mit minimalen Gesamtkosten findet, selbst wenn $n=3$ , aber vielleicht gibt es einen Online-Algorithmus mit einem kleinen Wettbewerbsverhältnis.

Hilft es insbesondere, dem Online-Algorithmus zu erlauben, mehr als $n-1$ Vergleiche durchzuführen ? Ist es besser, mehrere "extra" billige Vergleiche anzustellen, als ein paar teure Vergleiche?

Ich interessiere mich besonders für den Fall $C_{i,j} = 4^{d(i,j)}$ , wobei $d$ eine diskrete Metrik über die Menge $S$ ist und $0 \le d(i,j) \le k$ für alle . Ein optimaler Online-Algorithmus ist in dieser Einstellung noch nicht möglich. $i,j$

Hinweise auf ähnliche Probleme sind willkommen. Ich suche nicht jemanden, der mein Problem löst (obwohl einige Ideen helfen können und geschätzt werden). Ich möchte nur wissen, ob dieses Problem bekannt ist. (Ich konnte nichts finden.)

cc.complexity-theory ds.algorithms reference-request online-algorithms George
quelle

Warten Sie, jetzt bin ich verwirrt. Wenn Sie sowohl die Werte als auch die paarweisen Vergleichskosten im Voraus kennen, entspricht die Minimierung der Gesamtvergleichskosten der Berechnung einer Arboreszenz mit minimalen Kosten in einem vollständigen azyklisch gerichteten Diagramm. Wenn Sie die Werte jedoch nicht kennen, sondern ihre Reihenfolge nur durch tatsächliche Vergleiche ermitteln, gibt es keine Online-Strategie, bei der anhand von Vergleichen der minimalen Gesamtkosten immer das kleinste Element gefunden wird. Ein kluger Gegner kann Sie zwingen, Geld zu verschwenden. Für welche Version interessieren Sie sich?

Jeffs

Ok, vielleicht habe ich meine Frage nicht klar genug gestellt. Die Werte sind unbekannt und werden durch Vergleiche "aufgedeckt" (nicht wirklich, sagen Vergleiche geben nur zurück, wenn ein Objekt größer, gleich oder kleiner als ein anderes ist). Ich interessiere mich also für die zweite Version. Übrigens hat noch nie von der kostengünstigen Arboreszenz gehört. Zumindest habe ich etwas Neues gelernt.

George

Sie sollten Ihre Frage bearbeiten, um diesen Punkt explizit zu machen. Um Ihre kurzen Fragen zu beantworten: Ich weiß nicht, ob das Problem bereits bekannt ist, aber die Durchführung der optimalen Online-Vergleiche ist nicht NP-vollständig, da dies unmöglich ist (es sei denn,

). Das Beste, auf das Sie hoffen können, ist ein kleines Wettbewerbsverhältnis.

n = 2

$n=2$

Jeffs

Aus Gründen der Klarheit bearbeitet (ich hoffe) und um zu betonen, dass dies eine Frage zu Online- Algorithmen ist. Bitte überprüfen Sie, ob ich die Problemstellung nicht zu sehr vermasselt habe!

Jeffs

Das ist viel besser! Vielen Dank. Ich habe auch hinzugefügt, dass der Abstand zwischen zwei beliebigen Objekten oben durch eine ganze Zahl k begrenzt ist.

George

Antworten:

Die Brute-Force-Fallanalyse zeigt, dass das optimale Wettbewerbsverhältnis für den Sonderfall ohne weitere Einschränkungen der Kostenmatrix der Goldene Schnitt $n=3$ . Somit kann kein Online-Algorithmus ein besseres Wettbewerbsverhältnis alserzielen. $\phi = (\sqrt{5}+1)/2$ $\phi$

Angenommen, , und . $C_{1,2}=0$ $C_{1,3}=1$ $C_{2,3}=\phi$

Ohne Verlust der Allgemeinheit beginnt der Algorithmus mit dem Vergleich von mit zu Kosten Null. $S_1$ $S_2$
Der Gegner erklärt . $S_1 > S_2$
Wenn der Algorithmus mit : $S_1$ $S_3$
- Der Gegner erklärt . $S_1 > S_3$
- Der Algorithmus muss und . $S_2$ $S_3$
- Der Gegner erklärt , also ist das Minimum. $S_2 < S_3$ $S_2$
- Die Gesamtkosten der Vergleiche des Algorithmus betragen . $1+\phi$
- Der Gegner enthüllt die Gesamtordnung . $S_2 < S_3 < S_1$
- Die Gesamtkosten der optimalen Vergleiche ( und ) . $S_1>S_2$ $S_2<S_3$ $\phi$
Wenn der Algorithmus mit : $S_2$ $S_3$
- Der Gegner erklärt , also ist das Minimum. $S_3 > S_2$ $S_2$
- Die Gesamtkosten der Vergleiche des Algorithmus betragen . $\phi$
- Der Gegner offenbart die Gesamtordnung . $S_2 < S_1 < S_3$
- Die Gesamtkosten der optimalen Vergleiche ( und ) betragen . $S_1>S_2$ $S_1<S_3$ $1$
In beiden Fällen kosten die Vergleiche des Algorithmus einen Faktor von mehr als der optimale Satz von Vergleichen für die offenbarte Gesamtreihenfolge. $\frac{1+\phi}{\phi} = \frac{\phi}{1} = \phi$

Im Allgemeinen beträgt das Wettbewerbsverhältnis , wobeidie drei Vergleichskosten sind. (Hier sind weitere Fälle zu berücksichtigen, da es optimale Algorithmen gibt, die nicht zuerst den billigsten Vergleich durchführen, die Fallanalyse jedoch immer noch elementar ist.) Mühsame Berechnungen implizieren, dass der Ausdruck $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ $a\le b\le c$ wird maximiert, wenn,und. $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ $a=0$ $b=1$ $c=\phi$

Insbesondere wenn kann der bestmögliche Algorithmus gezwungen werden, alle drei Vergleiche durchzuführen. $\frac{a+c}{a+b} > \frac{a+b+c}{a+c}$

Jeffε
quelle

Das ist ein sehr guter erster Schritt! Vielen Dank für Ihr Interesse an meinem Problem (es scheint, dass Sie noch mehr interessiert sind als ich :))

George

Schöne Beobachtung. Zu beachten ist, dass diese Analyse einen deterministischen Algorithmus voraussetzt, sofern ich mich nicht irre.

Tsuyoshi Ito

Ja, das ist richtig. Ein randomisierter Algorithmus könnte besser abschneiden (erwartungsgemäß gegen einen ahnungslosen Gegner).

Jeffs

-3

Ein Anfang ist:

Sortieren Sie alle Elemente Ihrer Kostenmatrix C.
Führen Sie zuerst den Vergleich der niedrigsten Kosten durch und setzen Sie den Verlierer in den festgelegten NOPE
Führen Sie den Vergleich für jeden nachfolgenden Kostenvergleich nicht durch, wenn sich eines der beiden Elemente in NOPE befindet
Sie müssen weitermachen, bis alle bis auf ein Element in NOPE sind, dh n-1-Vergleiche.

Ist das ein anständiger Algorithmus? Hängt von den relativen Kosten für das Sortieren von C im Vergleich zu den Vergleichen in S ab:

Wenn für einen Artikel, den Sie bewerten, ein Vergleich billiger als der aktuell durchgeführte war, wurde er bereits durchgeführt, und der aktuelle Artikel hat diesen Vergleich gewonnen
Kosten == n ^ 2 numerische Vergleiche zur Sortierung C plus n-1 Vergleiche von S.

-t.

Tristan Reid
quelle

Ja, dies ist ein offensichtlicher gieriger Algorithmus. Nein, die Kosten sind die Summe der Kosten der einzelnen Vergleiche, die vom Algorithmus durchgeführt werden, wie durch die Matrix

C_{i, j}

$C_{i,j}$

Jeffs

Vielen Dank! Ich habe bereits über diesen offensichtlichen gierigen Ansatz nachgedacht (den ich verwenden werde, wenn nichts Besseres herauskommt). Das Problem ist, ob es irgendwelche Garantien für das Wettbewerbsverhältnis gibt.

George

@ JeffE - ja, die Kosten sind die n-1 Vergleiche mit den damit verbundenen Kosten, aber auch die Kosten für das Sortieren der Kostenmatrix

Tristan Reid

@ George B. - Wenn die Kosten für das Sortieren von C relativ günstig sind, gibt es meines Erachtens keinen besseren Algorithmus dafür. Dieser Algorithmus führt immer genau n-1 Vergleiche durch, niemals 1 mehr oder 1 weniger. Die Vergleiche, die es durchführt, werden immer die n-1 billigsten sein. Ich denke, Gier ist gut ...

Tristan Reid

Nein, es werden nicht immer die billigsten sein. Zum Beispiel sei A> B> C und

= 1,

= 2 und

= 1. Wenn Sie zuerst

und

vergleichen und dann

mit

vergleichen Die Gesamtkosten betragen 4 ^ 1 + 4 ^ 2 = 20, während Sie zuerst

mit

und dann

mit

d_{(} A, B)

$d_(A,B)$

d_{(} A, C)

$d_(A,C)$

d_{(} B, C)

$d_(B,C)$

A

$A$

B

$B$

A

$A$

C

$C$

B

$B$

C

$C$

A

$A$

B

$B$ Die Kosten betragen 4 ^ 1 + 4 ^ 1 = 8, daher funktioniert ein solcher gieriger Algorithmus hier nicht. Und ja, das Sortieren von C ist kein Problem.

George