Approximationsalgorithmus - Versionsgeschichte

Aka: Tippfehler entfernt

2021-11-15T19:14:11Z

← Nächstältere Version		Version vom 15. November 2021, 21:14 Uhr
Zeile 1:		Zeile 1:
	Ein '''Approximationsalgorithmus''' (oder auch '''Näherungsalgorithmus''') ist in der [[Informatik]] ein [[Algorithmus]], der ein [[Optimierungsproblem]] näherungsweise löst.		Ein '''Approximationsalgorithmus''' (oder auch '''Näherungsalgorithmus''') ist in der [[Informatik]] ein [[Algorithmus]], der ein [[Optimierungsproblem]] näherungsweise löst.

	Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst ~~nahe kommt~~.		Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahekommt.
	Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen\|Güte des Algorithmus]].		Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen\|Güte des Algorithmus]].

Biggerj1 am 18. März 2020 um 09:28 Uhr

2020-03-18T09:28:54Z

← Nächstältere Version		Version vom 18. März 2020, 11:28 Uhr
Zeile 1:		Zeile 1:
	Ein '''Approximationsalgorithmus''' ist in der [[Informatik]] ein [[Algorithmus]], der ein [[Optimierungsproblem]] näherungsweise löst.		Ein '''Approximationsalgorithmus''' (oder auch '''Näherungsalgorithmus''') ist in der [[Informatik]] ein [[Algorithmus]], der ein [[Optimierungsproblem]] näherungsweise löst.

	Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommt.		Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommt.

Biggerj1 am 17. März 2020 um 12:19 Uhr

2020-03-17T12:19:22Z

← Nächstältere Version		Version vom 17. März 2020, 14:19 Uhr
Zeile 30:		Zeile 30:
	== Siehe auch ==		== Siehe auch ==
	* [[Heuristik]]		* [[Heuristik]]
			* [[Iteration]]

	== Literatur ==		== Literatur ==

Biggerj1 am 17. März 2020 um 08:55 Uhr

2020-03-17T08:55:05Z

← Nächstältere Version		Version vom 17. März 2020, 10:55 Uhr
Zeile 3:		Zeile 3:
	Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommt.		Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommt.
	Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen\|Güte des Algorithmus]].		Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen\|Güte des Algorithmus]].


	== Klassen von Approximationsalgorithmen ==		== Klassen von Approximationsalgorithmen ==

Biggerj1: wiederherstellung der Überschrift

2020-03-17T08:50:47Z

wiederherstellung der Überschrift

← Nächstältere Version		Version vom 17. März 2020, 10:50 Uhr
Zeile 4:		Zeile 4:
	Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen\|Güte des Algorithmus]].		Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen\|Güte des Algorithmus]].


	==Einteilung ==
			== Klassen von Approximationsalgorithmen ==
			Optimierungsprobleme werden in der [[Theoretische Informatik\|Theoretischen Informatik]] in verschiedene Approximationsklassen unterschieden, je nachdem welcher Grad an Approximation möglich ist:

	=== APX ===		=== APX ===

Biggerj1 am 17. März 2020 um 08:49 Uhr

2020-03-17T08:49:33Z

← Nächstältere Version		Version vom 17. März 2020, 10:49 Uhr
Zeile 3:		Zeile 3:
	Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommt.		Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommt.
	Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen\|Güte des Algorithmus]].		Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen\|Güte des Algorithmus]].

			==Einteilung ==

	=== APX ===		=== APX ===

Biggerj1: Auslagerung

2020-03-17T08:48:41Z

Auslagerung

← Nächstältere Version		Version vom 17. März 2020, 10:48 Uhr
Zeile 2:		Zeile 2:

	Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommt.		Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem\|vermutlich]] nicht [[Effizienz (Informatik)\|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommt.
			Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen\|Güte des Algorithmus]].

	== Güte von Approximationsalgorithmen ==
	Es sei <math>S(I)</math> die zu einer Eingabe <math>I</math> gehörige Menge zulässiger Lösungen.
	Zu jeder möglichen Lösung <math>y \in S(I)</math> sei <math>v(y)</math> der Wert der Zielfunktion für <math>y</math>. Der Zielfunktionswert einer optimalen Lösung für Eingabe <math>I</math> sei <math>v^</math>. Ein Approximationsalgorithmus (oder Approximationsverfahren) gibt bei Eingabe <math>I</math> eine Lösung <math>y \in S(I)</math> aus, so dass <math>v(y)</math> relativ nah an <math>v^</math> liegt.

	Ist <math>y</math> die von einem Approximationsverfahren für die Eingabe <math>I</math> berechnete Lösung, so ist die ''Güte'' des Approximationsverfahrens bei der Eingabe <math>I</math>

	:bei Maximierungsaufgaben als <math>r_I = \frac{v^}{v(y)}</math> und bei Minimierungsaufgaben als <math>r_I = \frac{v(y)}{v^}</math> definiert.

	Es ist also immer <math>r_I \geq 1</math>. Gilt <math>r_I = 1</math>, liefert der Algorithmus eine optimale Lösung für <math>I</math>.

	Hat ein Approximationsverfahren für alle möglichen Eingaben <math>I</math> eine Güte <math>r_I</math> von höchstens <math>\alpha</math>, so spricht man von einer ''<math>\alpha</math>-Approximation''.
	Die garantierte Güte eines Algorithmus ist die '''Gütegarantie'''.

	== Klassen von Approximationsalgorithmen ==
	Optimierungsprobleme werden in der [[Theoretische Informatik\|Theoretischen Informatik]] in verschiedene Approximationsklassen unterschieden, je nachdem welcher Grad an Approximation möglich ist:

	=== APX ===		=== APX ===

Biggerj1: /* Güte von Approximationsalgorithmen */

2020-03-17T08:42:41Z

Güte von Approximationsalgorithmen

← Nächstältere Version		Version vom 17. März 2020, 10:42 Uhr
Zeile 14:		Zeile 14:

	Hat ein Approximationsverfahren für alle möglichen Eingaben <math>I</math> eine Güte <math>r_I</math> von höchstens <math>\alpha</math>, so spricht man von einer ''<math>\alpha</math>-Approximation''.		Hat ein Approximationsverfahren für alle möglichen Eingaben <math>I</math> eine Güte <math>r_I</math> von höchstens <math>\alpha</math>, so spricht man von einer ''<math>\alpha</math>-Approximation''.
			Die garantierte Güte eines Algorithmus ist die '''Gütegarantie'''.

	== Klassen von Approximationsalgorithmen ==		== Klassen von Approximationsalgorithmen ==

Aka: Halbgeviertstrich

2018-10-21T13:33:23Z

Halbgeviertstrich

← Nächstältere Version		Version vom 21. Oktober 2018, 15:33 Uhr
Zeile 7:		Zeile 7:
	Zu jeder möglichen Lösung <math>y \in S(I)</math> sei <math>v(y)</math> der Wert der Zielfunktion für <math>y</math>. Der Zielfunktionswert einer optimalen Lösung für Eingabe <math>I</math> sei <math>v^</math>. Ein Approximationsalgorithmus (oder Approximationsverfahren) gibt bei Eingabe <math>I</math> eine Lösung <math>y \in S(I)</math> aus, so dass <math>v(y)</math> relativ nah an <math>v^</math> liegt.		Zu jeder möglichen Lösung <math>y \in S(I)</math> sei <math>v(y)</math> der Wert der Zielfunktion für <math>y</math>. Der Zielfunktionswert einer optimalen Lösung für Eingabe <math>I</math> sei <math>v^</math>. Ein Approximationsalgorithmus (oder Approximationsverfahren) gibt bei Eingabe <math>I</math> eine Lösung <math>y \in S(I)</math> aus, so dass <math>v(y)</math> relativ nah an <math>v^</math> liegt.

	Ist <math>y</math> die von einem Approximationsverfahren für die Eingabe <math>I</math> berechnete Lösung, so ist die ''Güte'' des Approximationsverfahrens bei der Eingabe <math>I</math>		Ist <math>y</math> die von einem Approximationsverfahren für die Eingabe <math>I</math> berechnete Lösung, so ist die ''Güte'' des Approximationsverfahrens bei der Eingabe <math>I</math>

	:bei Maximierungsaufgaben als <math>r_I = \frac{v^}{v(y)}</math> und bei Minimierungsaufgaben als <math>r_I = \frac{v(y)}{v^}</math> definiert.		:bei Maximierungsaufgaben als <math>r_I = \frac{v^}{v(y)}</math> und bei Minimierungsaufgaben als <math>r_I = \frac{v(y)}{v^}</math> definiert.
Zeile 22:		Zeile 22:
	Ein Problem liegt in der Klasse ''APX'', wenn eine Zahl <math>r</math> und ein [[Polynomialzeit\|polynomieller]] Algorithmus, der bei jeder zulässigen Eingabe <math>I</math> eine Lösung mit einer Güte <math>\leq r</math> liefert, existieren.		Ein Problem liegt in der Klasse ''APX'', wenn eine Zahl <math>r</math> und ein [[Polynomialzeit\|polynomieller]] Algorithmus, der bei jeder zulässigen Eingabe <math>I</math> eine Lösung mit einer Güte <math>\leq r</math> liefert, existieren.

	=== PTAS/PAS ===		=== PTAS/PAS ===
	''PTAS'' oder ''PAS'' steht für '''''p'''olynomial '''t'''ime '''a'''pproximation '''s'''cheme''. Anders als bei der Klasse ''APX'' wird hier für jedes <math>\delta \in (0,1)</math> gefordert, dass ein polynomialer Algorithmus existiert, der bei jeder zulässigen Eingabe eine Lösung mit einer Güte <math>r \leq 1+\delta</math> liefert. Der Algorithmus muss also nicht nur für eine bestimmte Güte, sondern für jede Approximationsgüte effizient sein.		''PTAS'' oder ''PAS'' steht für '''''p'''olynomial '''t'''ime '''a'''pproximation '''s'''cheme''. Anders als bei der Klasse ''APX'' wird hier für jedes <math>\delta \in (0,1)</math> gefordert, dass ein polynomialer Algorithmus existiert, der bei jeder zulässigen Eingabe eine Lösung mit einer Güte <math>r \leq 1+\delta</math> liefert. Der Algorithmus muss also nicht nur für eine bestimmte Güte, sondern für jede Approximationsgüte effizient sein.

	=== FPTAS ===		=== FPTAS ===
	''FPTAS'' steht für '''''f'''ully '''p'''olynomial '''t'''ime '''a'''pproximation '''s'''cheme''. Hier wird gefordert, dass sich der Algorithmus nicht nur polynomiell zur Eingabe, sondern auch zur Güte der Approximation verhält; Dass er also zu jeder Eingabe <math>I</math> und jedem <math>k \in \mathbb{N}</math> eine Lösung mit der Güte <math>r \leq 1+1/k</math> ausgibt und seine Laufzeit polynomiell in <math>x</math> und <math>k</math> ist.		''FPTAS'' steht für '''''f'''ully '''p'''olynomial '''t'''ime '''a'''pproximation '''s'''cheme''. Hier wird gefordert, dass sich der Algorithmus nicht nur polynomiell zur Eingabe, sondern auch zur Güte der Approximation verhält; Dass er also zu jeder Eingabe <math>I</math> und jedem <math>k \in \mathbb{N}</math> eine Lösung mit der Güte <math>r \leq 1+1/k</math> ausgibt und seine Laufzeit polynomiell in <math>x</math> und <math>k</math> ist.

Zeile 43:		Zeile 43:

	== Literatur ==		== Literatur ==
	* Rolf Wanka: ''Approximationsalgorithmen - Eine Einführung'', Teubner, Wiesbaden, 2006, ISBN 3-519-00444-5		* Rolf Wanka: ''Approximationsalgorithmen – Eine Einführung'', Teubner, Wiesbaden, 2006, ISBN 3-519-00444-5
	* Klaus Jansen, Marian Margraf: ''Approximative Algorithmen und Nichtapproximierbarkeit'', de Gruyter, Berlin, New York, 2008, ISBN 978-3-11-020316-5		* Klaus Jansen, Marian Margraf: ''Approximative Algorithmen und Nichtapproximierbarkeit'', de Gruyter, Berlin, New York, 2008, ISBN 978-3-11-020316-5

84.63.73.156: /* FPTAS */ Latex

2018-06-13T12:37:51Z

FPTAS: Latex

← Nächstältere Version		Version vom 13. Juni 2018, 14:37 Uhr
Zeile 33:		Zeile 33:
	Unter der Annahme <math>P \neq NP</math> sind die obigen [[Inklusionsabbildung]]en echte Inklusionen. Das heißt, es gibt zum Beispiel mindestens ein Optimierungsproblem, das in der Klasse ''PTAS'' liegt, aber nicht in der Klasse ''FPTAS''. Unter dieser Annahme existiert auch mindestens ein Optimierungsproblem, das nicht in ''APX'' liegt. Dies lässt sich unter der Annahme <math>P \subsetneq NP</math> zum Beispiel für das [[Cliquenproblem]] zeigen.		Unter der Annahme <math>P \neq NP</math> sind die obigen [[Inklusionsabbildung]]en echte Inklusionen. Das heißt, es gibt zum Beispiel mindestens ein Optimierungsproblem, das in der Klasse ''PTAS'' liegt, aber nicht in der Klasse ''FPTAS''. Unter dieser Annahme existiert auch mindestens ein Optimierungsproblem, das nicht in ''APX'' liegt. Dies lässt sich unter der Annahme <math>P \subsetneq NP</math> zum Beispiel für das [[Cliquenproblem]] zeigen.

	Sei <math>\Pi</math> ein Optimierungsproblem, dessen Zielfunktion <math>v: S(I) \~~rightarrow~~ \mathbb{N}</math> für alle Instanzen <math>I</math> ganzzahlig ist.		Sei <math>\Pi</math> ein Optimierungsproblem, dessen Zielfunktion <math>v\colon S(I) \to \mathbb{N}</math> für alle Instanzen <math>I</math> ganzzahlig ist.
	Falls es ein Polynom <math>p</math> mit <math>opt(I)<p(\|I\|,maxnr(I))</math> für jede Instanz <math>I</math> gibt, dann folgt aus der Existenz eines FPTAS für <math>\Pi</math> die Existenz eines [[pseudopolynomiell]]en Algorithmus für <math>\Pi</math>.		Falls es ein Polynom <math>p</math> mit <math>opt(I)<p(\|I\|,maxnr(I))</math> für jede Instanz <math>I</math> gibt, dann folgt aus der Existenz eines FPTAS für <math>\Pi</math> die Existenz eines [[pseudopolynomiell]]en Algorithmus für <math>\Pi</math>.
	Hierbei ist <math>opt(I)</math> die optimale Lösung für die Instanz <math>I</math> und <math>maxnr(I)</math> der maximale Wert einer Variable von <math>I</math>.		Hierbei ist <math>opt(I)</math> die optimale Lösung für die Instanz <math>I</math> und <math>maxnr(I)</math> der maximale Wert einer Variable von <math>I</math>.