Anordnung von Streckenzügen

Neue Frage »

akechi90 Auf diesen Beitrag antworten »
Anordnung von Streckenzügen
Ich bin auf ein spezielles Problem gestoßen, und habe bisher vergeblich versucht, dazu eine Lösung zu finden, deswegen frage ich hier mal nach:

Gegeben sei eine endliche Menge von Strecken mit jeweils bestimmter Länge. Ebenso existiert ein Basisstreckenzug AB.

Nun wird eine Strecke ausgewählt, und exakt orthogonal auf den Basisstreckenzug AB im Punkt B gesetzt. Der Endpunkt des hinzugefügten Streckenzugs soll C genannt werden.
Nun wählt man eine weitere Strecke und setzt diese orthogonal zu AC auf C. Das Ende dieser Strecke soll D genannt werden. Und so weiter. Bis jede Strecke aus der Menge der Strecken genau einmal verwendet wurde.
Sei N der letzte so konstruierte Punkt. Kann man auch ohne die Konstruktion eine Anordnung der Strecken finden, sodass der Winkel NAB möglichst groß wird?
Und wie sieht die Sache aus, wenn der Basisstreckenzug ebenfalls in der Menge liegt und genau einmal verwendet werden darf?

Würde mich über Antworten freuen
PK Auf diesen Beitrag antworten »

Hmm.. meiner Ansicht nach kann der Basisstreckenzug drinliegen, wenn ich alles richtig verstanden hab, aber natürlich nicht unbedingt jeder aus deiner Menge an Streckenzügen.
AD Auf diesen Beitrag antworten »
RE: Anordnung von Streckenzügen
Zunächst noch zur Klärung:

1) Wir sind in der Ebene, ja? Im Raum kann das nämlich ganz schön kompliziert werden.

2) Ich gehe jetzt mal von der Ebene aus. Zweckmäßig legt man dann das ganze achsenparallel in ein kartesisches Koordinatensystem. Dann hat man abwechselnd waagerechte und senkrechte Strecken. Deiner Beschreibung "orthogonal" nach hat man in jedem Punkt selbst bei fester Streckenlänge noch die Wahl zwischen zwei Richtungen, meinst du das so?

Dann sage ich mal ganz salopp, dass man bei großer Streckenanzahl und einigermaßen gleichmäßiger Streckenverteilung mit dem Winkel nahe an das Maximum von herankommt.

Zitat:
Original von akechi90
Kann man auch ohne die Konstruktion eine Anordnung der Strecken finden, sodass der Winkel NAB möglichst groß wird?

Diese Wortgruppe verstehe ich nicht und habe sie daher konsequent igoniert. Ohne diese Konstruktion (und wenn nur gedanklich) hast du hier nur einen Haufen Strecken vorliegen und damit gar kein
, für das du den Winkel betrachten kannst!!!
JochenX Auf diesen Beitrag antworten »

Ich sehe zwei mögliche Optimierungsnethoden (die Strecke liege parallel zur x-Achse in einem normalen Koordinatensystem, A liege rechts davon); es gebe n Strecken

1) minimieren der Strecke "nach oben/unten"
2) maximieren der Strecke "nach rechts"

1) wird dabei erreicht, indem man manche senkrechten Strecken nach oben, die anderen nach unten geht.
lässt sich dabei erreichen, dass sich aus der Hälfte (ggf. aufgerundet) der Streckenteile eine "Nullstrecke" basteln lässt, ist der Fall klar
2) wird ohne beachten von 1 erreicht, indem die n/2 (oder (n-1)/2) längsten Streckenteile dafür aufgewendet werden nach rechts zu gehen.

Im Allgemeinen könnte eine Mischung aus 1 und 2 zur Optimalität beitragen, vermute ich.
AD Auf diesen Beitrag antworten »

Meine Ideen gehen in eine ähnliche Richtung. Die optimale Lösung ist allerdings sehr rechenaufwändig, wenn ich das richtig überblicke:

Die Grundstrecke habe die Länge , o.B.d.A. sei und .

Die restlichen Strecken werden nun in drei disjunkte Mengen aufgeteilt (Mengen ist eigentlich das falsche Wort, wenn gleiche Streckenlängen mehrfach auftauchen - aber ich denke, du weißt, wie ich das meine) mit und . Dabei kennzeichnet die waagerechten, die senkrecht nach oben und die senkrecht nach unten verlaufenden Strecken des Streckenzuges. Bei brauchen wir keine derartige Unterscheidung: Hier verlaufen alle Strecken nach links, d.h. in negative Richtung, denn unser Ziel ist ja maximaler Winkel , der offensichtlich nur so zu erreichen ist. Insgesamt gelangen wir durch diese Prozedur zum Punkt



mit Winkel . Letztlich kommt es darauf an, sowie möglichst minimales zu erreichen. Und da sind wir beim kombinatorischen Problem der Aufteilung , so dass dieser Quotient minimal wird.
JochenX Auf diesen Beitrag antworten »

Vielleicht wären da auch mal "konkrete" Beispiele interessant (*), hier mal eine relativ einfache Aufgabe. Insbesondere zeigt die auch beide Punkte von oben und die Wahl von X, Y1 und Y2 ist (bis auf Vertauschen der Yi) eindeutig.
Ich denke, das hilft Akechi und anderen auch gut, Athurs Formalismus zu durchdenken (und zu verstehen) - wobei ich mir da bei Akechi eigentlich eher weniger Sorgen mache.


Sei a eine beliebige Streckenlänge >0.
Wir haben nun m Strecken der Längen , wie sind X und die Yi zu wählen, damit welcher maximale Winkel entsteht?
Spielt die Länge a eine Rolle?
(der Einfachheit halber beginne man mit m=2n gerade)



(*) einen (nicht BruteForce) Algorithmus für allgemeine Streckenverteilungen anzugeben ist nämlich wohl nicht möglich; warum also sollte man nicht mal von der Theorie in die Praxis übergehen?
 
 
AD Auf diesen Beitrag antworten »

Mal zur Aufwandsabschätzung, ich gehe dazu mal nur von geraden aus, sonst fliegen einem die Gaußklammern ständig um die Ohren und verdecken den Blick auf das Wesentliche...

Das Verfahren, so wie ich es vorgestellt habe, benötigt dann die Untersuchung von Mengenaufteilungen; mit der von Jochen erwähnten Vertauschbarkeit von und reduziert sich das gerademal auf die Hälfte, also . Das ist für größere eine ganze Menge Holz, also wird man sich ohne wirksame Eindämmung der zu untersuchenden Varianten (die ich momentan nicht sehe) vielleicht auch mit suboptimalen Lösungen zufrieden geben müssen.

In die Richtung geht sicherlich Vorschlag 2) aus dem ersten Posting von Jochen, wobei man sich aber im Klaren sein muss, dass man durch dieses Verfahren die optimale Lösung sehr wahrscheinlich verpasst. Dafür kommt man aber in diesem Teilfall auch viel schneller zu Rande, denn das "Herausfischen" der längsten Strecken für hat nur Größenordnung , unbedeutend gegenüber denn dann zu addierenden für die Aufteilung der restlichen Strecken.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »