Schneeschaufel-Optimierung

17/02/2009 - 17:00 von Helmut Richter | Report spam
Heute morgen beim Schneeschaufeln gedachte ich die Arbeit zu optimieren,
d.h. den kürzesten Weg freizuschaufeln, so dass alle Punkte (Haustür,
Gartentor, Terassentür, Briefkasten, Mülltonne, Komposthaufen) miteinander
verbunden sind. Dabei weiß ich nicht mal das Optimum für ein Dreieck. Rein
von der Anschauung sieht es gut aus, wenn man die Winkelhalbierenden
jeweils von der Ecke bis zum Inkreismittelpunkt freischaufelt, aber ist
das optimal? Und wie geht man vor, wenn man mehr als drei Punkte hat?

Ich denke gerne mit, habe aber diese Woche keine Muße dafür: vor Tau und
Tag Schneeschaufeln (einstweilen leider suboptimal), dann auch noch was
anderes zu tun.

Helmut Richter
 

Lesen sie die antworten

#1 gwoegi
17/02/2009 - 17:34 | Warnen spam
Helmut Richter wrote:
# Heute morgen beim Schneeschaufeln gedachte ich die Arbeit zu optimieren,
# d.h. den k??rzesten Weg freizuschaufeln, so dass alle Punkte (Haust??r,
# Gartentor, Terassent??r, Briefkasten, M??lltonne, Komposthaufen) miteinander
# verbunden sind. Dabei wei?? ich nicht mal das Optimum f??r ein Dreieck. Rein
# von der Anschauung sieht es gut aus, wenn man die Winkelhalbierenden
# jeweils von der Ecke bis zum Inkreismittelpunkt freischaufelt, aber ist
# das optimal?

Nein, im allgemeinen nicht.
Anstatt des Inkreismittelpunktes des Dreiecks ABC musst Du einen
Punkt P nehmen, sodass die drei Strecken AP, BP, CP bei P drei
120-Grad Winkel bilden.

#
# Und wie geht man vor, wenn man mehr als drei Punkte hat?

Das ein schwieriges (NP-vollstaendiges) Problem.
In der Literatur wird es Steinerbaumproblem genannt:
http://en.wikipedia.org/wiki/Steiner_tree



___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/

Ähnliche fragen