rekursives program

rekursives program (14 Beiträge, 552 Mal gelesen)

Du bist nicht angemeldet. [ Login/Registrieren ]

Hi,

ich stehe im Moment ein bisschen bei einem rekursiven Problem an und wäre dankbar für jede Hilfe.

Die Ausgangslage:
ich habe N Variablen die sich zwischen festgelegten Grenzen befinden, jedoch sind die Grenzen von den vorherigen Variablen abhängig (d.h Variable 2 ist von Variable 1 abhängig, Variable 3 ist von Variable 2 und Variable 1 abhängig).

In einem ersten Schritt wurde jede Variable in Brackets unterteilt und das Minimum und das Maximum empirisch gemessen (unabhängig von allen anderen).

Um es zu verdeutlichen, heisst dass (für zwei Variablen) als Beispiel:
Variable 1: min: 0, max: 1 (diese ist unabhängig) und liegt (zB) in 3 Stufen vor:
(1) Variable 1 = 0.33: Variable 2: min: 0, max: 0.25
(2) Variable 1 = 0.66: Variable 2: min: 0.1, max: 0.4
(3) Variable 1 = 1: Variable 2: min 0.2, max: 1

als Ausgabe hiervon sollen dann X Schritte (zB 6) für Variable 2, zwischen deren min/max ausgegeben werden (also in (1) von oben: 0, 0.05, 0.1, 0.15, 0.2, 0.25).

Aus dem obigen Beispiel werden also schon 18 Kombinationen erstellt:
Nr, Variable 1, Variable 2
1, 0, 0
2, 0, 0.05
3, 0, 0.1
...
6, 0, 0.25
7, 0.33, 0.1
8, 0.33, 0.16
...

soweit einfach, bei 3 Variablen wird es schon komplizierter, hier soll dann gelten:
das Minimum/Maximum für Variable 3 ist das jeweilige Maximum der Minima (Minimum der Maxima) der vorherigen Variablen.

Wiederum als Beispiel:
(1) Variable 1 = 0.33: Variable 2: min: 0, max: 0.25, Variable 3: min: 0, max: 0.25
   (1b) Variable 2 = 0: Variable 3: min: 0, max: 0.05 --> Min für Variable 3 ist 0, Max=0.05 (min aus 0.25 und 0.05)
   (1c) Variable 2 = 0.05: Variable 3: min: 0.02, max: 0.15 --> Min für Variable 3 ist 0.02 (max aus 0 und 0.02), Max=0.15 (min aus 0.25 und 0.15)
   (1d) Variable 2 = 0.01: Variable 3: min: 0.05, max: 0.35 --> Min für Variable 3 ist 0.05 (max aus 0 und 0.05), Max=0.25 (min aus 0.25 und 0.35)
...

Die Grenzen in den Szenarien 1b, 1c usw. werden aus den empirischen Angaben interpoliert (d.h. wenn die ursprünglichen Bracekts für Variable 2 zb 0 und 0.05 (usw.) waren und jetzt für 0.02 ein Szenario erstellt wird, wird aus den Minimas/Maximas von 0 und 0.05 auf 0.02 interpoliert). Es sollen für Variable 3 wieder 6 Szenarien erstellt werden

Als Ausgabe würde ich hier auf:
Nr, Variable 1, Variable 2, Variable 3
1, 0, 0, 0
2, 0, 0, 0.01
3, 0, 0, 0.02
...
7, 0, 0.05, 0.02
8, 0, 0.05, 0.046
...

Ich hoffe das Problem ist verständlich, in Wahrheit brauche ich "einfach" nur eine Liste der möglichen Verteilungsräume der Variablen unter Vorbedingungen.

Für Hilfe bin ich sehr dankbar!

mfg

Penguin

moment, irgendwo hakts bei mir.

Ich ermittle empirisch minima und maxima für jede Variable, aber eigentlich leg ichs dann auf Math.Min(vorhergehende, jetzige) und Math.Max(vorhergehende, jetzige) fest?

private class myVar
{
  float minValue;
  float maxValue;
  float value;
}

private myVar [] myVariables = new myVar[number of values];

myVariables befüllen blabla;

//ich fang deswegen mit 0 an, falls du in der schleife gleich die limits printen willst
for {int i = 0; i < myVar.Length;i++}
{
  if (i > 0)
  {
    myVariables[i].minValue = (float)Math.Max(myVariables[i-1], myVariables[i]);
    myVariables[i].maxValue = (float)Math.Min(myVariables[i-1], myVariables[i]);
  }

  //jetzt kannst die limits ausgeben
  .. ausgabe der limits von myVariables[i] hier
}

und jetzt hast in allen Elementen von myVariables die neuen Limita drin stehen. So gemeint?

09.09.2014, 14:32 Uhr - Editiert von zeddicus, alte Version: hier

Zuerst die Minima/Maxima je Variable (matlab-code):

------------------------

for i=1:size(mySurpriseModelInputs,2)
    % bin the data
    myVarBin{i} = unique(quantile(mySurpriseModelInputs(:, i),(0:0.10:1)'));
    % map to bins
    [myBinCount,myBinPos] = histc(mySurpriseModelInputs(:,i),myVarBin{i});
    % cut off edges
    if myBinCount(end) == 1, myBinPos(myBinPos==max(myBinPos))=max(myBinPos)-1;end
    if myBinCount(1) == 1, myBinPos(myBinPos==min(myBinPos))=min(myBinPos)+1;end

    % determine the extreme's per bracket
    [myTempMax,myTempMin] = deal(zeros(size(unique(myBinPos),1),1));
    for j=1:length(unique(myBinPos))
        myTempMin(j,1) = min(mySurpriseModelInputs(myBinPos==j,setdiff(1:size(mySurpriseModelInputs,2),i)));
        myTempMax(j,1) = max(mySurpriseModelInputs(myBinPos==j,setdiff(1:size(mySurpriseModelInputs,2),i)));
    end

    if size(myVarBin{i},1)>10
        myInputMin{i} = horzcat(myInputMin{i}(:,1:i-1),myVarBin{i}(1:end-1),myInputMin{i}(:,i:end));
        myInputMax{i} = horzcat(myInputMax{i}(:,1:i-1),myVarBin{i}(1:end-1),myInputMax{i}(:,i:end));
    else
        myInputMin{i} = horzcat(myInputMin{i}(:,1:i-1),myVarBin{i},myInputMin{i}(:,i:end));
        myInputMax{i} = horzcat(myInputMax{i}(:,1:i-1),myVarBin{i},myInputMax{i}(:,i:end));
    end
end
mySimulationBoundaries = struct('min',{myInputMin},'max',{myInputMax});

------------------------

der output ist also ein set von min/max je variable (aller anderen Variablen), wenn die gegebene Variable einen bestimmten wert hat. Der Grund für das nicht in einer Matrix zu haben ist, das eine der Variablen der Wochentag ist und daher nur 5 Mapping-Punkte hat (die anderen 11).

Als Anforderung hätte ich jetzt gerne für jede Variable, die anderen Variablen in möglichen Kombinationen, so dass aber die Bedingungen noch erfüllt sind (also die erste Variable darf alle Werte zwischen deren Min und Max annehmen, je nachdem welchen Wert die erste Variable hat, darf die zweite Variable nur Werte annehmen, die zwischen der jeweiligen Einträge für diese Gruppe liegt).

mfg

Penguin

09.09.2014, 15:00 Uhr - Editiert von Penguin, alte Version: hier

mySimulationBoundaries.min =
    [10x4 double]    [10x4 double]    [10x4 double]    [5x4 double]

d.h. ich hab jede der 4 Variablen in 10 Brackets gebinned (ausser die 4. Variable --> Wochentag, daher nur 5 Bins).

mySimulationBoundaries.min{1} =
untere
Grenze        min           min               min
Bracket       für            für                 für
Variable 1   Variable 2  Variable 3      Variable 4
-0.09           0.1           -0.01               2
-0.01           0.09          -0.01              2
...
0.01           0.11           -0.01              2

mySimulationBoundaries.max{1} =
untere
Grenze        max           max               max
Bracket       für              für                 für
Variable 1   Variable 2   Variable 3      Variable 4
-0.09           0.69          0.01               6
-0.01           0.6            0.01               6
...
0.01           0.75           0.01               6

mySimulationBoundaries.min{2} =
                 untere
min           Grenze        min           min
für             Bracket       für            für
Variable 1   Variable 2  Variable 3   Variable 4
-0.04           0.08          0.001         2
-0.02           0.1            0.005         2
...
-0.09           0.29          -0.01         2

mySimulationBoundaries.max{2} =
                 untere
max           Grenze        max          max
für             Bracket       für            für
Variable 1   Variable 2  Variable 3   Variable 4
0.01           0.08          0.006          6
0.02           0.1            0.008          6
...
0.1           0.29          0.01            6

Zusammengefasst:
Schritt 1:
wenn Variable 1 -0.01 ist, muss Variable 2 zwischen 0.09 und 0.6 liegen
Schritt 2:
wir erstellen 10 Brackets zwischen 0.09 und 0.6, erster Step: 0.09
Schritt 3:
wenn Variable 2 0.09 ist, muss Variable 3 zwischen max(-0.01, 0.001) = 0.001 und min(0.01,0.006) =0.006 liegen
Schritt 4:
wir erstellen 10 Brackets zwischen 0.001 und 0.006, erster Step 0.001
Schritt 5:
wenn Variable 3 0.001 ist, muss Variable 4 zwischen max(2,2,2) = 2 und min(6,6,6) liegen

mfg

Penguin

Das hier könnte dir weiterhelfen wenn du Java (List durch ArrayList ersetzen) oder C# kannst:
http://pastebin.com/e2ZQE9gL

soweit einfach, bei 3 Variablen wird es schon komplizierter, hier soll dann
gelten:
das Minimum/Maximum für Variable 3 ist das jeweilige Maximum der Minima
(Minimum der Maxima) der vorherigen Variablen.
Wiederum als Beispiel:
(1) Variable 1 = 0.33: Variable 2: min: 0, max: 0.25, Variable 3: min: 0, max:
0.25
   (1b) Variable 2 = 0: Variable 3: min: 0, max: 0.05 --> Min für Variable 3
ist 0, Max=0.05 (min aus 0.25 und 0.05)
   (1c) Variable 2 = 0.05: Variable 3: min: 0.02, max: 0.15 --> Min für
Variable 3 ist 0.02 (max aus 0 und 0.02), Max=0.15 (min aus 0.25 und 0.15)
   (1d) Variable 2 = 0.01: Variable 3: min: 0.05, max: 0.35 --> Min für
Variable 3 ist 0.05 (max aus 0 und 0.05), Max=0.25 (min aus 0.25 und 0.35)
...

test

genauso wie in deinem Beispiel hatte ich es jetzt implementiert, sprich mit schleifen je Variable.

Der Grund für die Suche nach der rekursiven Lösung ist weil (wie die Limitierung der Inputs schon nahe legt) "unrealistische" Extremfälle ein Problem darstellen können.

Bei der Analyse des Problems wollte ich Variablen weglassen/hinzunehmen, was an sich zwar kein Problem ist, jedoch bei Verwendung einer solchen Lösung:

        for (double v1val = v1min; v1val <= v1max; v1val += v1granularity)
                for (double v2val = GetV2min(v1val); v2val <= GetV2max(v1val); v2val += v2granularity)
                        for (double v3val = GetV3min(v1val, v2val); v3val <= GetV3max(v1val, v2val); v3val += v3granularity)
                                returnee.Add(new GenericTuplev1val, v2val, v3val));

nach sich zieht, dass ich immer wieder den code anpassen muss (wenn es statt 3 plötzlich 4 Variablen gibt). Ich hätte daher von einer flexiblen Lösung geträumt, die das für alle übergebenen Parameter macht.

Der Grund warum ich frage ist genau dein Bild. Ich sitze hier und denke mir - es muss doch gehen. Aber irgendwie wills net.

mfg

Penguin

Kannst du noch einmal im Detail erklären wie man min/max-Werte in Abhängigkeit von "Tiefe" (Anzahl d. Vorwerte) und Vorwerten berechnet?

Wenn man eine min und eine max Funktion erzeugen kann die beliebig viele Vorwerte nehmen kann hat man den schwierigsten Teil des Problems bewältigt.

test

Ausgangslage: Es gibt eine Outputgrösse, 7 Inputgrössen (Variablen).

für jede Variable werden aus den empirischen Daten 10 Decile erzeugt und die Variable selbst wird dann den  Decilen zugeordnet (gemapped). Sprich wenn meine Decile zb 1,2,...10 sind, werden alle Werte zwischen 1 und 2 auf das erste Decile gemapped usw.

Im nächsten Schritt wird für jedes der Decile dieser einen Variable das Min/Max aller anderen Variablen empirisch überprüft. Also was ist das Minimum jeder einzelnen anderen Variable (nur auf diese eine Variable bezogen), je Decil der gerade observierten Variable.

Daraus ergibt sich eine Beispiel-Tabelle 1 für Variable 1 a la:
Decil             Min     Max       Min     Max
Variable 1      Variable 2        Variable 3
1                  0         1           0.05   1
2                  0.5      1.5        0.1     1.2
...
10                0.2      2           0.15    1.1

sowie als Beispiel-Tabelle 2 für Variable 2:
Min     Max     Decil                Min     Max
Variable 1      Variable 2         Variable 3
0.1     0.9      1                     0.01   0.9
0.2     0.7      2                     0.15   0.99
...
0.97   1.05     10                  0.2     1.4

In meinem konkreten Fall erhalte ich daher 7 Tabellen (1 je Variable) mit je 10x7 Einträgen (10 Decile, für 7 Variablen).

Nun möchte ich ein Zufalls-Set an Variablen erzeugen um die Sensitivität des Output-Modells (welches aus den Inputs geschätzt wurde) zu überprüfen. Dafür benötige ich eine realistische Kombination von allen Variablen.

Realistisch bedeutet dass ich, ausgehend von der ersten Variable, die zufällig geschätzt wird, diese einem Decil zuordnen will. also zB:
1) im ersten Schritt wird für Variable 1 der Wert 1.2 geschätzt, diese liegt also im Decil 1 von Variable 1.

2) Daraufhin muss im nächsten Schritt Variable 2 geschätzt werden. Ich möchte 10 Möglichkeiten für Variable 2 simulieren, muss jedoch sicherstellen, dass jede Zahl für Variable 2 zwischen 0 und 1 (siehe Min/Max für Variable 2 im Decil 1 von Variable 1 in der Beispiel-Tabelle 1) liegt.

3) Dann wird dieser simulierte Wert mit den Decilen von Variable 2 verglichen. Als Beispiel gehen wir davon aus dass die erste Simulation von Variable 2 im Decil 2 (von Variable 2) liegt.

4) Jetzt muss ich Variable 3 simulieren. Die Variable 3 muss die Bedingungen wie folgt erfüllen: Der Wert muss zwischen Min/Max für das aktuelle Decil von Variable 1 (also Decil 1) liegen (Beispieltabelle: zwischen 0.05 und 1) und gleichzeitig zwischen Min/Max für das aktuelle Decil von Variable 2 (also Decil 2) liegen (Beispieltabelle: zwischen 0.15 und 0.99). Daraus ergibt sich insgesamt, dass Variable 3 zwischen 0.15 (dem Maximum aus 0.05 und 0.15) und 0.99 (dem Minimum aus 1 und 0.99) liegen muss.

Das ganze wird nun bis zur letzten Variable wiederholt, sprich die Variablen sind hierarchisch geordnet (d.h. Variable 1 bestimmt Variable 2, aber nicht umgekehrt).

mfg

Penguin

10.09.2014, 09:01 Uhr - Editiert von Penguin, alte Version: hier

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung