Nehmen wir an, wir haben eine 5x5-Matrix, die mit Nullen gefüllt ist.
myMatrix <- matrix(rep(0, 25), ncol = 5)
Lassen Sie uns nun ein Triplett von ganzen Zahlen zwischen 1 und 5 auswählen.
triplet <- c(1,2,3)
Für alle Kombinationen dieses Tripletts fügen wir nun mit dieser Funktion 1 in die Matrix ein:
addCombinationsToMatrix <- function(.matrix, .triplet){
indexesToChange <- as.matrix(expand.grid(.triplet, .triplet))
.matrix[indexesToChange] <- .matrix[indexesToChange] + 1
.matrix
}
Mit der Funktion gehen wir von
myMatrix
[,1] [,2] [,3] [,4] [,5]
[1,] 0 0 0 0 0
[2,] 0 0 0 0 0
[3,] 0 0 0 0 0
[4,] 0 0 0 0 0
[5,] 0 0 0 0 0
zu
myMatrix <- addCombinationsToMatrix(myMatrix, triplet)
myMatrix
[,1] [,2] [,3] [,4] [,5]
[1,] 1 1 1 0 0
[2,] 1 1 1 0 0
[3,] 1 1 1 0 0
[4,] 0 0 0 0 0
[5,] 0 0 0 0 0
Wenn wir ein anderes Triplett auswählen, gehen wir weiter zu
nextTriplet <- 2:4
myMatrix <- addCombinationsToMatrix(myMatrix, nextTriplet)
myMatrix
[,1] [,2] [,3] [,4] [,5]
[1,] 1 1 1 0 0
[2,] 1 2 2 1 0
[3,] 1 2 2 1 0
[4,] 0 1 1 1 0
[5,] 0 0 0 0 0
Zeilen-Spalten-Kombinationen geben also an, wie oft zwei Ganzzahlen in einem Triplett zusammen gezeigt wurden: 3 und 4 wurden einmal zusammen gezeigt, 2 und 3 wurden zweimal zusammen gezeigt.
Frage : Wie kann man Drillinge auswählen, so dass jede Kombination (1-2, 1-3, 1-4 ...) mindestens einmal ausgewählt wurde und die Anzahl der Drillinge minimiert wird.
Ich suche hier nach einem Algorithmus, der das nächste Triplett auswählt.
Idealerweise kann es erweitert werden auf
- beliebig große Matrizen (10x10, 100x100 ...)
- beliebig große Vektoren (Quadruplets, Quintuplets, n-Tuplets)
- Es muss mindestens beliebig oft eine Kombination ausgewählt worden sein
Beispiel:
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, 1:3)
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, 3:5)
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, c(1,4,5))
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, c(2,4,5))
myMatrix
EDIT : Nur um sicher zu gehen: Die Antwort muss kein R
Code sein. Es kann auch eine andere Sprache oder sogar Pseudocode sein.
EDIT 2 : Mir ist jetzt aufgefallen, dass es verschiedene Möglichkeiten gibt, die Effizienz zu messen. Ich meinte eigentlich, der Algorithmus sollte so wenig Iterationen wie möglich dauern. Der schnelle Algorithmus ist auch sehr cool, aber nicht das Hauptziel hier.
quelle
Hier ist eine Option, mit
data.table
der Sie die Matrixanzahl verfolgen undRcppAlgos
die Kombinationen generieren können:Es ist ein gieriger Algorithmus, daher bin ich mir nicht sicher, ob dies zu einer minimalen Anzahl von Tupeln führt.
quelle
Error in eval(onsub, parent.frame(2L), parent.frame(2L)) : object '.NATURAL' not found
Da diese Frage nach algorithmischen Ansätzen zur Abdeckung von Entwürfen fragt, werde ich einen bereitstellen, der genaue Antworten (auch bekannt als das bestmögliche Design) unter Verwendung der Ganzzahlprogrammierung in R gibt. Für jedes einzelne k-Tupel, das Sie in Betracht ziehen (k = 3 für Sie, Da Sie Triplets auswählen, definieren Sie eine Entscheidungsvariable, die den Wert 1 annimmt, wenn Sie sie in Ihr Design aufnehmen, und 0, wenn nicht. In Ihrem Fall würden Sie also x_123 definieren, um anzugeben, ob Tupel (1,2,3) ausgewählt ist, x_345 für (3,4,5) und so weiter.
Das Ziel des Optimierungsmodells besteht darin, die Anzahl der ausgewählten Tupel, auch bekannt als die Summe aller Ihrer Entscheidungsvariablen, zu minimieren. Für jedes t-Tupel (in Ihrem Fall t = 2) müssen Sie jedoch eine Entscheidungsvariable einfügen, die dieses t-Tupel enthält. Dies ergibt eine Einschränkung für jedes t-Tupel. Als Beispiel hätten wir
x_123+x_124+x_125 >= 1
die Einschränkung, die erfordert, dass sich das Paar12
in einem ausgewählten Tupel befindet.Dies ergibt das folgende Optimierungsmodell:
Sie können dies dahingehend erweitern, dass r Wiederholungen jedes t-Tupels erforderlich sind, indem Sie die rechte Seite jeder Ungleichung in "r" ändern und alle Variablen ganzzahlig statt binär sein müssen.
Dies ist einfach mit einem Paket wie
lpSolve
in R zu lösen :Dies löst Ihr Problem zwar genau, lässt sich jedoch nicht gut auf große Problemgrößen skalieren. Dies liegt daran, dass das Problem NP-schwer ist - kein bekannter exakter Algorithmus lässt sich gut skalieren. Wenn Sie große Problemfälle lösen müssen, sind die in anderen Antworten hier empfohlenen Heuristiken die beste Wahl. Oder Sie können mit ganzzahliger Programmierung (wie hier) lösen und eine Zeitüberschreitung festlegen. Dann arbeiten Sie mit der besten Lösung, die Sie durch Ihr Timeout gefunden haben. Dies ist eine heuristische Lösung für das Problem insgesamt.
quelle