Optimierungsproblem < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:54 Mo 23.05.2011 | | Autor: | bandchef |
| Aufgabe | Definition:
[mm] $\Sigma_{\text{in}}$ [/mm] ist ein Eingabealphabet
[mm] $\Sigma_{\text{out}}$ [/mm] ist ein Ausgabealphabet
$L [mm] \subseteq \Sigma_{\text{in}}^\star$ [/mm] ist die Sprach der zulässigen Eingaben. $x [mm] \in [/mm] L$ heißt Instanz von U.
$M:L [mm] \to P(\Sigma_{\text{out}})^\star$ [/mm] ist eine Funktion - für jedes $x [mm] \in [/mm] L$ ist $M(x)$ die Menge der zulässigen Lösungen für x.
[mm] $\text{cost}: \bigcup_{x\in L} [/mm] (M(x) [mm] \times \{x\}) \to {\mathbb R}^{+}:$ [/mm] ist eine Funktion, genannt Kostenfunktion
[mm] $\text{goal} \in \{\text{Minimun, Maximun}\}$ [/mm] ist das Optimierungsziel.
Eine zulässige Lösung $a [mm] \in [/mm] M(x)$ heißt optimal für die Instanz x des Optimierungsproblems $U$, falls:
[mm] $\text{Opt}_U(x) [/mm] = [mm] \text{cost}(a,x) [/mm] = [mm] \text{goal} \{\text{cost}(\beta,x) | \beta \in M(x)\} [/mm] |
Hi Leute!
Kann mir das oben mal jemand erklären?  Irgendwie verstehe ich das grad nicht so. Was die Ein- und Ausgabealphabete bzw. die Sprache der zulässigen Eingaben sind, verstehe ich noch. Auch mit der Menge zulässigen Lösungen für x, kann ich noch was anfange, aber dann weiß ich echt nicht mehr was das soll. Insbesondere die Kostenfunktion und das Optimierungsziel!
Könnt ihr mir helfen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:06 Mo 23.05.2011 | | Autor: | Loddar |
.
siehe mal hier ...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:13 Mo 23.05.2011 | | Autor: | bandchef |
Entschuldigung!
Wenn ich demnächst wieder zu "Nicht-Schulstoff" eine Frage stelle, dann werde ich das Uni-Subofrum auswählen! Kannst du nachträglich verschieben?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:09 Mi 25.05.2011 | | Autor: | meili |
Hallo,
> Definition:
>
> [mm]\Sigma_{\text{in}}[/mm] ist ein Eingabealphabet
> [mm]\Sigma_{\text{out}}[/mm] ist ein Ausgabealphabet
> [mm]L \subseteq \Sigma_{\text{in}}^\star[/mm] ist die Sprach der
> zulässigen Eingaben. [mm]x \in L[/mm] heißt Instanz von U.
> [mm]M:L \to P(\Sigma_{\text{out}})^\star[/mm] ist eine Funktion -
> für jedes [mm]x \in L[/mm] ist [mm]M(x)[/mm] die Menge der zulässigen
> Lösungen für x.
> [mm]\text{cost}: \bigcup_{x\in L} (M(x) \times \{x\}) \to {\mathbb R}^{+}:[/mm]
> ist eine Funktion, genannt Kostenfunktion
> [mm]\text{goal} \in \{\text{Minimun, Maximun}\}[/mm] ist das
> Optimierungsziel.
>
> Eine zulässige Lösung [mm]a \in M(x)[/mm] heißt optimal für die
> Instanz x des Optimierungsproblems [mm]U[/mm], falls:
>
> [mm]$\text{Opt}_U(x)[/mm] = [mm]\text{cost}(a,x)[/mm] = [mm]\text{goal} \{\text{cost}(\beta,x) | \beta \in M(x)\}[/mm]
>
> Hi Leute!
>
> Kann mir das oben mal jemand erklären? Irgendwie
> verstehe ich das grad nicht so. Was die Ein- und
> Ausgabealphabete bzw. die Sprache der zulässigen Eingaben
> sind, verstehe ich noch. Auch mit der Menge zulässigen
> Lösungen für x, kann ich noch was anfange, aber dann
> weiß ich echt nicht mehr was das soll. Insbesondere die
> Kostenfunktion und das Optimierungsziel!
>
> Könnt ihr mir helfen?
Es ist einfach die etwas formal aufgemotze Aussage,
dass es eine Kostenfunktion gibt. (Über ihre Eigenschaften
oder ihren Verlauf ist nichts ausgesagt, bis auf,
sie nimmt Werte aus [mm] $\IR^+$ [/mm] an.)
Diese Kostenfunktion soll dann minimiert oder maximiert werden.
(Das globale Minimum oder Maximum gesucht werden?)
Eine zulässige Lösung [mm]a \in M(x)[/mm] heißt optimal für die Instanz x
des Optimierungsproblems [mm]U[/mm], falls der Wert der Kostenfunktion
für dies a größer (oder kleiner) als jeder Werte der Kostenfunktion für alle
anderen zulässigen Lösungen [mm]\beta \in M(x)[/mm] für die Instanz x ist.
Gruß
meili
|
|
|
|
