Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Ap­pro­xi­ma­ti­ons­al­go­rith­men

Da Quan­ten­com­pu­ter noch nicht im All­tag ein­ge­setzt wer­den kön­nen und nie­mand einen ef­fi­zi­en­ten Al­go­rith­mus für die Pro­ble­me aus NP ge­fun­den hat (man geht auch davon aus, dass es ihn nicht gibt), müs­sen Al­go­rith­men ge­fun­den wer­den, die ef­fi­zi­ent eine Lö­sung die­ser Pro­ble­me be­rech­nen, die gut aber viel­leicht nicht per­fekt ist. Wenn es zu schwer ist, eine Ko­lo­rie­rung einer Land­kar­te mit 4 Far­ben zu fin­den (auch wenn man weiß, dass dies immer mög­lich ist), dann soll­te man ak­zep­tie­ren, eine Fär­bung zu fin­den, die mit 5 oder 6 Far­ben ar­bei­tet. Sol­che Lö­sun­gen wer­den als Nä­he­rungs­lö­sun­gen be­zeich­net. Es gibt ver­schie­de­ne An­sät­ze, sol­che Nä­he­rungs­lö­sun­gen zu fin­den15.

Bei mess­ba­rer Qua­li­tät der Lö­sung (z.B. Länge einer Rund­rei­se beim Tra­ve­ling Sa­les­man Pro­blem) gibt die Ap­pro­xi­ma­ti­ons­gü­te den Fak­tor an, um wie viel die Nä­he­rungs­lö­sung schlimms­ten­falls schlech­ter ist als die op­ti­ma­le Lö­sung. Eine Güte von 1,01 würde also be­deu­ten, dass der Ap­pro­xi­ma­ti­ons­al­go­rith­mus ma­xi­mal 1% schlech­ter ist als die op­ti­ma­le Lö­sung. In der Pra­xis ist eine Güte von 1,5 oder sogar 2 schon ein guter Wert.

Greedy-Algorithmus beim Problem des Handlungsreisenden, Start in Ulm, Zwischenstand nach 15 Schritten

Deutsch­land­kar­te_(Bunt).svg: Ste­fan-Xp [CC BY-SA 3.0], via Wi­ki­me­dia Com­mons

Gree­dy-Al­go­rith­mus beim Pro­blem des Hand­lungs­rei­sen­den, Start in Ulm, Zwi­schen­stand nach 15 Schrit­ten

In der Schu­le kann nur ein klei­ner Ein­blick in die Prin­zi­pi­en der Ap­pro­xi­ma­ti­ons­al­go­rith­men statt- fin­den. Der Bil­dungs­plan schlägt vor, z.B. Gree­dy-Ver­fah­ren zu be­han­deln16. Dabei steht die Idee und nicht die Ana­ly­se der Güte im Vor­der­grund. Diese kann höchs­tens ex­pe­ri­men­tell an ei­ni­gen Bei­spie­len er­mit­telt wer­den.

Gree­dy

Bei Gree­dy-Al­go­rith­men geht man so vor, dass man bei jeder Ent­schei­dung die mo­men­tan am bes­ten er­schei­nen­de Mög­lich­keit wählt. An­ders als beim Back­tracking nimmt man diese aber nicht zu­rück, um an­de­re Va­ri­an­ten aus­zu­pro- bie­ren, son­dern bleibt bei die­ser Ent­schei­dung, auch wenn sie nicht op­ti­mal war.

Bei­spiel 1: Pro­blem des Hand­lungs­rei­sen­den

Von der Start­stadt aus wird als nächs­tes die­je­ni­ge noch nicht be­such­te Stadt an­ge­fah­ren, die am nächs­ten liegt. Von dort aus geht man wie­der zur nächst­ge­le­ge­nen usw.

Das kann dazu füh­ren, dass ein­zel­ne Städ­te in einer Ecke des Lan­des zu­nächst aus­ge­las­sen wer­den (hier z.B. Re­gens­burg und Pas­sau) und dann nur noch mit einem sehr wei­ten Weg zu er­rei­chen sind.

Bei­spiel 2: Sitz­platz­ver­tei­lung in einem Bus

Wenn jeder Schü­ler fest­ge­legt hat, wie gerne er im Bus neben jedem an­de­ren sit­zen würde, dann könn­te ein Gree­dy-Al­go­rith­mus in jedem Schritt einen noch nicht zu­ge­teil­ten Schü­ler aus­wäh­len und den­je­ni­gen noch nicht plat­zier­ten Schü­ler da­zu­set­zen, der die höchs­te Be­wer­tung hat. Auch hier müs­sen even­tu­ell am Ende Schü­ler zu­sam­men­ge­setzt wer­den, die sich über­haupt nicht aus­ste­hen kön­nen.

Se­quen­ti­el­le Al­go­rith­men

Se­quen­ti­el­le Al­go­rith­men sind ge­eig­net, wenn man die Kno­ten des Gra­phen in Teil­men­gen auf­tei­len muss. Sie wer­den dann nach einer ge­wis­sen Rei­hen­fol­ge ab­ge­ar­bei­tet und wenn mög­lich einer be­ste­hen­den Teil­men­ge hin­zu­ge­fügt. Ist dies nicht mög­lich, be­ginnt man eine neue Teil­men­ge.

Man kann das Fär­be­pro­blem eines Gra­phen auf diese Art lösen: Alle Kno­ten einer Teil­men­ge wer­den in einer Farbe ge­färbt. Ein neuer Kno­ten darf die­ser Teil­men­ge nur dann hin­zu­ge­fügt wer­den, wenn er keine ge­mein­sa­men Kan­ten mit einem der Kno­ten die­ser Teil­men­ge hat. Sor­tiert man die Kno­ten zu­nächst ab­stei­gend nach ihrem Grad, dann wer­den bei der Fär­bung eines pla­na­ren Gra­phen (einer Karte) nie mehr als sechs Far­ben ver­wen­det.

Ran­do­mi­sier­te Al­go­rith­men

Bei ran­do­mi­sier­ten Al­go­rith­men ent­schei­det der Zu­fall, wie die Lö­sung aus­sieht. Muss eine Ent­schei­dung ge­trof­fen wer­den, wird sie per Zu­falls­ge­ne­ra­tor ent­schie­den.

Bei­spiel:

Sucht man z.B. einen ma­xi­ma­len Schnitt durch einen Graph, d.h. eine Auf­tei­lung der Kno­ten in zwei Teil­men­gen, so dass mög­lichst viele Kan­ten zwi­schen bei­den Teil­men­gen be­ste­hen, kann man z.B. jeden Kno­ten mit der Wahr­schein­lich­keit 1/2 einer der bei­den Teil­men­gen zu­ord­nen. Das Ver­fah­ren ist nicht sehr gut, lie­fert aber immer einen Schnitt, der im Durch­schnitt halb so viele Kan­ten zer­schnei­det wie der op­ti­ma­le Al­go­rith­mus.

Lo­ka­le Suche

Man kann eine zu­fäl­li­ge Lö­sung unter Um­stän­den noch schritt­wei­se op­ti­mie­ren. Dazu ver­än­dert man die ge­trof­fe­nen Ent­schei­dun­gen so, dass die Ver­bes­se­rung der Lö­sung mög­lichst groß ist (Me­tho­de des steils­ten Ab­stiegs). Man kommt aber auch hier nicht zwangs­läu­fig zur op­ti­ma­len Lö­sung ins­ge­samt, da es lo­ka­le Ex­tre­ma geben kann, in denen keine (ein­zel­ne) Ver­än­de­rung eine Ver­bes­se­rung bringt.

Üb­li­cher­wei­se wird die­ses Ver­fah­ren dann mehr­mals durch­ge­führt (z.B. 1000x). Das beste Er­geb­nis wird dann ge­nom­men. Dies hat den Vor­teil, dass die Chan­ce durch eine un­güns­ti­ge Wahl am An­fang ein sehr schlech­tes Er­geb­nis zu be­kom­men, er­heb­lich re­du­ziert wird.

Bei­spiel 1: Pro­blem des Hand­lungs­rei­sen­den

Die Rei­hen­fol­ge der Städ­te wird zu­nächst zu­fäl­lig fest­ge­legt. Nun kann man schritt­wei­se Ver­bes­se­run­gen vor­neh­men. Dabei könn­te man un­ter­schied­li­che Ver­fah­ren an­wen­den. Zum Bei­spiel:

  • Man än­dert die Po­si­ti­on einer Stadt in der Liste, so dass die Ge­samt­stre­cke dann mög­lichst kurz wird.
  • Man ver­tauscht die Po­si­tio­nen zwei­er Städ­te in der Liste, so dass die Ge­samt­stre­cke mög­lichst kurz wird.

Bei­spiel 2: Do­mi­nie­ren­de Menge

Man fügt am An­fang zu­fäl­lig so lange Kno­ten zur do­mi­nie­ren­den Menge hinzu, bis alle Kno­ten ab­ge­deckt sind (d.h. einer ihrer Nach­bar­kno­ten in der do­mi­nie­ren­den Menge ist). Da­nach ver­sucht man so lange, ein­zel­ne Kno­ten aus der do­mi­nie­ren­den Menge zu ent­fer­nen, wie immer noch alle Kno­ten ab­ge­deckt sind.

Ob dies eine gute Nä­he­rungs­lö­sung pro­du­ziert, müss­te man dann un­ter­su­chen.

Ge­ne­ti­sche Al­go­rith­men

Eine in­ter­es­san­te Va­ri­an­te der Ap­pro­xi­ma­ti­ons­al­go­rith­men stellt ein ge­ne­ti­scher Al­go­rith­mus dar. Man ver­sucht die Evo­lu­ti­on in der Natur nach­zu­emp­fin­den. Man star­tet mit meh­re­ren zu­fäl­li­gen Lö­sun­gen des Pro­blems (z.B. einer Po­pu­la­ti­on von 1000).

Se­lek­ti­on: Aus die­sen wählt man die bes­ten aus (z.B. 50), alle an­de­ren ver­wirft man.

Re­kom­bi­na­ti­on: Diese 50 bes­ten wer­den nun ge­kreuzt, d.h. es wird ein Teil der Ent­schei­dun­gen aus der Lö­sung A mit den rest­li­chen Ent­schei­dun­gen aus B kom­bi­niert. Da­durch ent­steht eine neue Lö­sung.

Mu­ta­ti­on: Man kann auch mit einer ge­wis­sen Wahr­schein­lich­keit noch Mu­ta­tio­nen ein­bau­en, d.h. zu­fäl­li­ge Ver­än­de­run­gen der Lö­sung.

Auf diese Weise er­zeugt man wie­der eine Po­pu­la­ti­on. Nun be­ginnt der Zy­klus der Se­lek­ti­on und Re­kom­bi­na­ti­on er­neut. Auf diese Weise wer­den meh­re­re Zy­klen durch­ge­führt. All­mäh­lich soll­ten die Lö­sun­gen so bes­ser wer­den (sur­vi­val of the fit­test).

Bei­spiel: Tra­ve­ling Sa­les­man

Die Städ­te wer­den in zu­fäl­li­ger Rei­hen­fol­ge an­ge­ord­net. Die 50 kür­zes­ten Rou­ten wer­den aus­ge­wählt. Für die Re­kom­bi­na­ti­on wer­den zwei Rund­rei­sen aus­ge­wählt und von der 1. Route die ers­ten x Städ­te über­nom­men, wobei die Zahl x zu­fäl­lig fest­ge­legt wird. Da­nach fügt man alle feh­len­den Städ­te in der Rei­hen­fol­ge der 2. Rund­rei­se hinzu. Mu­ta­tio­nen kann man ein­bau­en, indem man die Po­si­ti­on von zwei zu­fäl­li­gen Städ­ten tauscht.

Verlauf der Länge der kürzesten Rundreise

Bild­quel­le: Ver­lauf der Länge der kür­zes­ten Rund­rei­se der Po­pu­la­ti­on über die Ge­ne­ra­tio­nen 0-60 (die Länge der op­ti­ma­len Rund­rei­se liegt ver­mut­lich zwi­schen 5000 und 6000 km) von ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus 1_gra­phen_hin­ter­grund.odt

 

15 Liste von NP-voll­stän­di­gen Pro­ble­men in Wi­ki­pe­dia,URL: https://​en.​wi­ki­pe­dia.​org/​wiki/​List_​of_​NP-​com­ple­te_​pro­blems

16 Bil­dungs­plan In­for­ma­tik (Schul­ver­such), 3.​3.​2.​2 Al­go­rith­men auf Da­ten­struk­tu­ren (12) "Stra­te­gi­en (zum Bei­spiel Gree­dy) zur Be­stim­mung von Nä­he­rungs­lö­sun­gen in po­ly­no­mi­el­ler Lauf­zeit be­schrei­ben und an ge­eig­ne­ten Pro­blem­stel­lun­gen (zum Bei­spiel 4-Far­ben-Pro­blem, Do­mi­na­ting Sets) von Hand durch­füh­ren"
oder
Ap­pro­xi­ma­ti­ons­al­go­rith­men, Jan Jo­hann­sen (Vor­le­sung im Som­mer­se­mes­ter 2007) ab Folie 28, URL: http://​www2.​tcs.​ifi.​lmu.​de/~abel/lehre/SS07/Ap­prox/Fo­li­en.pdf (Dez. 2020)

 

Hin­ter­grund­in­for­ma­tio­nen: Her­un­ter­la­den [odt][990 KB]

 

Wei­ter zu Aus­ge­wähl­te Gra­phen-Al­go­rith­men