Problem mit Rekursion < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:21 Di 13.03.2007 | | Autor: | unixfan |
Hallo!
Ich untersuche gerade ein Würfelspiel und komme auf folgendes Problem, von dem ich glaube dass es in den Bereich diskrete dynamische Optimierung fällt.
Bis jetzt hatte in an der Uni nur lineare Optimierung und wenige andere Sachen.
Mein Problem ist, dass ich gerne folgendes x ausrechnen möchte:
[mm]
x = \sum_{i=1}^n p_i \min (x+1, a_i)
[/mm]
(Hinweis, 0 [mm] \leq p_i \leq [/mm] 1 und [mm] a_i \geq [/mm] 0, das macht die Sache minimal besser, aber auch nicht soooo viel)
Mein aktueller Ansatz ist, alle möglichen Summen auszurechnen und davon das Minimum zu suchen (nach x auflösen kann man bei jeder möglichen Summe). Das führt aber zu [mm] 2^n [/mm] Möglichkeiten, was zu dem Problem führt, dass ich es effektiv bei meinem speziellen Problem mit n>400 wohl nicht in einer sinnvollen Zeit ausrechnen kann....
Das Problem sieht für mich eigentlich verdammt einfach aus, scheint es aber nicht zu sein, gibt es eventuell irgendwelche Algorithmen mit denen man sowas berechnen kann.
Viele Dank im voraus,
Peter
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:59 Di 13.03.2007 | | Autor: | unixfan |
Ich glaube ich habe es mit dem Ansatz lösen können, x [mm] \geq [/mm] das zeug anzunehmen und mich dann x immer weiter zu nähern bis es passt.
Hierzu eine Funktion in C die das für mich macht
float findMinimum(float p[], float a[], int start, int size) {
static float x;
float [mm] new_x;
[/mm]
int i;
if (start) {
x = 0;
}
[mm] new_x [/mm] = 0;
for (i=0; i<size; i++) {
[mm] new_x [/mm] += p[i] * MIN(x+1, a[i]);
}
if [mm] (new_x [/mm] != x) {
x = [mm] new_x;
[/mm]
findMinimum(p, a, FALSE, size);
}
return(x);
}
Ich glaube die macht was ich will, ganz sicher bin ich mir allerdings nicht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:42 Mi 14.03.2007 | | Autor: | unknown |
Moin,
es ist spät und daher solltest Du folgendes gaaanz vorsichtig lesen :):
Transformiere als erstes
[mm]
x
= \sum_{j=1}^n p_j \min(x+1, a_j)
= \sum_{j=1}^n p_j \min(x, a_j - 1) + \sum_{j=1}^n p_j.
[/mm]
Seien OBdA [mm]p_1 \leq p_2 \leq \ldots \leq p_n[/mm], [mm]s_j = a_j - 1[/mm]und [mm]c
= \sum p_j[/mm].
[mm]
\begin{matrix}
&x = c + \sum_{j=1}^n p_j \min(x, s_j)
\\
\Leftrightarrow&
(x \leq s_1 \wedge x = \sum_{j=1}^n p_j x + c) \\
&\vee
\Bigl(
\bigvee_{k=2}^{n}
(s_{k-1} < x \leq s_k
\wedge x = \sum_{j=1}^k p_j x + \sum_{j=k+1}^n p_j s_j + c)
\Bigr) \\
&\vee
(s_n < x \wedge x = \sum_{j=1}^n p_j s_j + c)
\\
\Leftrightarrow
&(\frac{c}{1 - \sum_{j=1}^n p_j} \leq s_1
\wedge x = \frac{c}{1 - \sum_{j=1}^n p_j}) \\
&\vee
\Bigl(
\bigvee_{k=1}^{n-1}
(s_k < \frac{\sum_{j=k+1}^n p_j s_j + c}{1 - \sum_{j=1}^k p_j} \leq s_{k+1}
\wedge x = \frac{\sum_{j=k+1}^n p_j s_j + c}{1 - \sum_{j=1}^k p_j})
\Bigr) \\
&\vee
(s_n < \sum_{j=1}^n p_j s_j + c \wedge x = \sum_{j=1}^n p_j s_j + c)
\end{matrix}
[/mm]
Also
[mm]
x = \left\{\begin{array}{ll}
\frac{c}{1 - \sum_{j=1}^n p_j}
&\hbox{falls } \sum_{j=1}^n p_j s_j + c \leq s_1 \\
\frac{\sum_{j=k+1}^n p_j s_j + c}{1 - \sum_{j=1}^k p_j}
&\hbox{falls }
s_k < \frac{\sum_{j=k+1}^n p_j s_j + c}{1 - \sum_{j=1}^k p_j} \leq s_{k+1}
\hbox{ mit } 2 \leq k \leq n \\
\sum_{j=1}^n p_j s_j + c
&\hbox{falls }
s_n < \frac{c}{1 - \sum_{j=1}^n p_j}
\end{array}\right.
[/mm]
Wenn ich alles richtig habe, mußt Du nur die $n$ Summen jeweils mit Deinen [mm] $s_j$ [/mm] vergleichen, und kannst dann $x$ ablesen. Aber wie gesagt, es ist spät...
Hoffe, das hilft!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Do 15.03.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
