Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Hans-Peter Diettrich Newsgroups: de.sci.electronics Subject: Re: Kleines mathematisches Problem Date: Mon, 15 Feb 2016 18:33:03 +0100 Lines: 37 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: individual.net jPWqct2MLNwx5nDgAJSEZQ7iYcCELlngO3TyRrHTksP3KB+pmR Cancel-Lock: sha1:qYHixD/Kvs/hMFErc5HpxdtsW/A= User-Agent: Thunderbird 2.0.0.21 (Windows/20090302) In-Reply-To: Xref: csiph.com de.sci.electronics:202226 Thomas Heger schrieb: > Meiner Ansicht nach beziehen sich die bisherigen Vorschläge auf sowas > wie das 'travelling sales man Problem'. Das ist die Frage nach der > Reihenfolge, in der zu besuchende Punkte angefahren werden sollen. > > Du suchst aber nach der kürzesten Strecke, die der Roboter von A (x1,y1) > nach Punkt B (x2, y2) auf einer Ebene fahren soll, ohne gegen > Hindernisse zu stoßen. > > Ich nehme nun den einfachsten Fall und es gibt genau ein Hindernis. Der > weg von A nach B auf einer Geraden durch beide Punkte wäre der kürzeste, > sollte dort kein Hindernis sein. > > Ist dort aber eines, dann muß der Roboter ausweichen und zwar zu der > Seite, wo er weniger von dieser Geraden abweichen muß. Er muß dann > soweit ausweichen, daß er an dem Hindernis gerade vorbeikommt. > > Jetzt kann man diesen Punkt bestimmen ( C an (x3, y3) ) und die Strecke > in zwei Teile Teilen und das ganze wiederholen für A->C und C->B. > > Das macht man dann solange, bis kein Hindernis mehr auf dem Fahrweg ist. Was mich zu der Frage führt, ob bei Deinem Vorschlag sichergestellt ist, daß für eine optimale Lösung jeder Schritt optimal sein muß. IMO ist nicht absehbar, ob ein Weg mit einmaligem Abknicken mit größerer Abweichung nicht kürzer ist als einer, der nach dem ersten (optimalen) Schritt öfters abknickt. Jetzt mal ganz abgesehen von den Kosten für jeden Richtungswechsel, aber unter Beachtung der Abstände, die das Fahrzeug von jedem Hindernis einhalten muß. Ich weiß nicht, ob das irgendwie zum konkreten Fall paßt, aber ein Blick auf "Roman Chariots" könnte eventuell hilfreich sein. DoDi