Minimaler Abstand bei mehreren Kreisen

11.05.2016, 09:50

HoschiJones

Auf diesen Beitrag antworten »

Minimaler Abstand bei mehreren Kreisen

Hallo zusammen.

Ich habe einen, immer gleichen, Abstand a und Durchmesser D sowie eine Anzahl von n Kreisen.
Die Durchmesser dürfen sich nicht überschneiden.
Je nach Anordnung der Kreise erhalte ich eine unterschiedliche Gesamtlänge L, die minimal sein soll.

Zur Frage - gibt es eine rechnerische Lösung um L bei gegebenen a, D und n zu minimieren?

Ich zeichne z.Zt. die Abstände auf und teste dann durch zusammenschieben.

Zum besseren Verständnis habe ich eine Skizze angehängt. In dieser Skizze ist der Durchmesser D=70, der Abstand a=10 und die Anzahl n=6.

[attach]41590[/attach]

11.05.2016, 10:22

HAL 9000

Auf diesen Beitrag antworten »

Mir ist nicht klar, was die Linien mit Abstand $\begin{align*} a \end{align*}$ für eine Bedeutung für das Problem haben sollen. Ist es etwa so, dass die Kreismittelpunkte nur auf diesen Linien liegen dürfen? verwirrt

verwirrt

Was mir ebenfalls noch unklar ist: Gibt es keine Begrenzung für die "Breite" deines Schlauchs? Denn ohne Begrenzung würde man doch hinsichtlich der Längenminimierung die Kreise im (nahezu) Zickzack-Muster anordnen, so dass jeder Kreis (fast) seinen übernächsten Nachbarn berührt...

11.05.2016, 10:25

Steffen Bühler

Auf diesen Beitrag antworten »

RE: Minimaler Abstand bei mehreren Kreisen
Sollen die Kreismittelpunkte alle auf verschiedenen Höhen liegen? Sechs Kreise also auf sechs verschiedenen Höhen, die jeweils ein ganzzahliges Vielfaches von a auseinanderliegen?

Viele Grüße
Steffen...zu spät

11.05.2016, 10:56

HoschiJones

Auf diesen Beitrag antworten »

RE: Minimaler Abstand bei mehreren Kreisen

Zitat:

Original von HAL 9000
Mir ist nicht klar, was die Linien mit Abstand $\begin{align*} a \end{align*}$ für eine Bedeutung für das Problem haben sollen. Ist es etwa so, dass die Kreismittelpunkte nur auf diesen Linien liegen dürfen? verwirrt

verwirrt

Was mir ebenfalls noch unklar ist: Gibt es keine Begrenzung für die "Breite" deines Schlauchs? Denn ohne Begrenzung würde man doch hinsichtlich der Längenminimierung die Kreise im (nahezu) Zickzack-Muster anordnen, so dass jeder Kreis (fast) seinen übernächsten Nachbarn berührt...

Zitat:

Original von Steffen Bühler
Sollen die Kreismittelpunkte alle auf verschiedenen Höhen liegen? Sechs Kreise also auf sechs verschiedenen Höhen, die jeweils ein ganzzahliges Vielfaches von a auseinanderliegen?

Viele Grüße
Steffen...zu spät

Entschuldigung, das hatte ich nicht geschrieben.

Jeder Kreismittelpunkt liegt nur 1x auf der Linie. Die Breite ist durch die Anzahl der Kreise auf (n-1)*a begrenzt.

11.05.2016, 10:59

willyengland

Auf diesen Beitrag antworten »

RE: Minimaler Abstand bei mehreren Kreisen
Wenn ich das recht verstehe, sind die Kreise doch irrelevant.
Es reicht, eine Zickzacklinie mit immer gleicher "Zick"-Länge zu zeichnen, so dass ein Endpunkt immer auf einer a-Linie endet.
Spontane Idee wäre, dass die Summe der Winkel zur a-Linie maximal ist?

11.05.2016, 11:16

HoschiJones

Auf diesen Beitrag antworten »

RE: Minimaler Abstand bei mehreren Kreisen

Zitat:

Original von willyengland
Wenn ich das recht verstehe, sind die Kreise doch irrelevant.
Es reicht, eine Zickzacklinie mit immer gleicher "Zick"-Länge zu zeichnen, so dass ein Endpunkt immer auf einer a-Linie endet.
Spontane Idee wäre, dass die Summe der Winkel zur a-Linie maximal ist?

Die Kreise sind insofern relevant, als dass sie den Durchmesser, also den Abstand zwischen den einzelnen Objekten anzeigen. Es sind Metallscheiben, die zwar zusammenstoßen, aber nicht überlappen dürfen.
Bei 6 Kreisen habe ich also eine Gesamtlänge von L bei einer Gesamtbreite von, in diesem Fall, 50 mm.
Die Gesamtlänge L soll so klein wie möglich sein. Es sind also im Endeffekt immer Dreiecke mit Hypotenuse D und den Katheten a bzw den Abstand in L-Richtung von Kreismittelpunkt zu Kreismittelpunkt.
L ist somit die Summe aller Katheten zwischen den Kreisen und dieses L soll Minimal sein.

Anzeige

11.05.2016, 11:28

HAL 9000

Auf diesen Beitrag antworten »

Ok, wenn ich richtig alles erfasst habe, wäre das folgendes Optimierungsproblem:

Über alle Permutationen $\begin{align*} \pi \end{align*}$ von $\begin{align*} \{1,\ldots,n\} \end{align*}$ minimiere man $\begin{align*} \sum_{k=1}^{n-1} \sqrt{4R^2 - ((\pi(k+1)-\pi(k))a)^2} \end{align*}$ unter den Nebenbedingungen

a) $\begin{align*} \left| \pi(k+1)-\pi(k) \right| \leq \frac{2R}{a} \end{align*}$ für alle $\begin{align*} k=1,\ldots,n-1 \end{align*}$ ,

b) $\begin{align*} \left( \sqrt{4R^2 - ((\pi(k+1)-\pi(k))a)^2} + \sqrt{4R^2 - ((\pi(k+2)-\pi(k+1))a)^2} \right)^2 + ((\pi(k+2)-\pi(k))a)^2 > 4R^2 \end{align*}$ für alle $\begin{align*} k=1,\ldots,n-2 \end{align*}$ .

Anmerkung: a) ist die Forderung, dass sich benachbarte Kreise auch berühren. b) ist die Forderung, dass ein Kreis den übernächsten Kreis nicht schneidet.

11.05.2016, 11:48

HoschiJones

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Ok, wenn ich richtig alles erfasst habe, wäre das folgendes Optimierungsproblem:

Über alle Permutationen $\begin{align*} \pi \end{align*}$ von $\begin{align*} \{1,\ldots,n\} \end{align*}$ minimiere man $\begin{align*} \sum_{k=1}^{n-1} \sqrt{4R^2 - ((\pi(k+1)-\pi(k))a)^2} \end{align*}$ unter den Nebenbedingungen

a) $\begin{align*} \left| \pi(k+1)-\pi(k) \right| \leq \frac{2R}{a} \end{align*}$ für alle $\begin{align*} k=1,\ldots,n-1 \end{align*}$ ,

b) $\begin{align*} \left( \sqrt{4R^2 - ((\pi(k+1)-\pi(k))a)^2} + \sqrt{4R^2 - ((\pi(k+2)-\pi(k+1))a)^2} \right)^2 + ((\pi(k+2)-\pi(k))a)^2 > 4R^2 \end{align*}$ für alle $\begin{align*} k=1,\ldots,n-2 \end{align*}$ .

Anmerkung: a) ist die Forderung, dass sich benachbarte Kreise auch berühren. b) ist die Forderung, dass ein Kreis den übernächsten Kreis nicht schneidet.

verwirrt

Ich muss gestehen, dass ich das nicht nachvollziehen kann, allerdings hört sich das nach der richtigen mathematischen Erklärung der Aufgabenstellung an.
Du wendest für die einzelnen Abstände Pythagoras an, soweit komme ich mit.

Ich suche "nur" eine Lösung, wie ich die Kreise anordnen muss, um eine möglichst kleine Platte zu bekommen, auf der alle Kreise ohne Überstand drauf passen.

11.05.2016, 12:53

HAL 9000

Auf diesen Beitrag antworten »

Ich hab das ganze genannt, weil es zumindest so für $\begin{align*} n\leq 12 \end{align*}$ noch problemlos möglich ist, das Problem durch Bruteforce über alle möglichen Permutationen zu erledigen. Allein bei Berücksichtigung von a) kann man zudem den Permutationsbaum schon mächtig beschneiden, so dass man sogar für leicht höhere $\begin{align*} n \end{align*}$ noch mit Bruteforce auskommt.

11.05.2016, 13:47

willyengland

Auf diesen Beitrag antworten »

Ist denn die Frage nur, wie die Minimallänge ist, oder auch, wie die Kreise dazu angeordnet werden müssen.
Wenn letzteres, dann reicht es ja nicht, eine Formel für $\begin{eqnarray*} L_{min} \end{eqnarray*}$ oder $\begin{eqnarray*} \Delta a_{max} \end{eqnarray*}$ zu finden, sondern es muss auch die richtige Reihenfolge/Anordnung gegeben werden.

11.05.2016, 13:50

HoschiJones

Auf diesen Beitrag antworten »

verwirrt

Brutforce, Permutation Wink

Wink

Ich dachte, dass ich ein geometrisches Problem angerissen habe Erstaunt2

Erstaunt2

Ich merke schon, dass ich mathematisch nicht mehr so ganz auf der Höhe bin.

11.05.2016, 13:51

HoschiJones

Auf diesen Beitrag antworten »

Zitat:

Original von willyengland
Ist denn die Frage nur, wie die Minimallänge ist, oder auch, wie die Kreise dazu angeordnet werden müssen.
Wenn letzteres, dann reicht es ja nicht, eine Formel für $\begin{eqnarray*} L_{min} \end{eqnarray*}$ oder $\begin{eqnarray*} \Delta a_{max} \end{eqnarray*}$ zu finden, sondern es muss auch die richtige Reihenfolge/Anordnung gegeben werden.

Da hast Du allerdings Recht, ohne die Reihenfolge macht das Ganze wenig Sinn.

11.05.2016, 15:14

Schnappschildkröte

Auf diesen Beitrag antworten »

Bruteforce bedeutet einfach nur, (mit einem Computer) alle Möglichkeiten auszuprobieren. Alle Permutationen von
{1,2} sind (1,2) und (2,1), von {1,2,3} (1,2,3),(1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Also quasi einfach alle möglichen Reihenfolgen der gegebenen Zahlen. Die Optimerungsaufgabe klingt allerdings ziemlich kompliziert. Augenzwinkern

Augenzwinkern

11.05.2016, 15:50

willyengland

Auf diesen Beitrag antworten »

Ich sage mal folgendes voraus:

Die kürzeste Strecke ist die:
1. Von der untersten zur obersten Linie.
2. von der obersten zur zweituntersten Linie
3. von der zweituntersten Linie zur zweitobersten Linie
usw.

Ein Beitrag von: Willys gesunder Menschenverstand(tm) Big Laugh

Big Laugh

11.05.2016, 16:06

HoschiJones

Auf diesen Beitrag antworten »

Zitat:

Original von Schnappschildkröte
Bruteforce bedeutet einfach nur, (mit einem Computer) alle Möglichkeiten auszuprobieren. Alle Permutationen von
{1,2} sind (1,2) und (2,1), von {1,2,3} (1,2,3),(1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Also quasi einfach alle möglichen Reihenfolgen der gegebenen Zahlen. Die Optimerungsaufgabe klingt allerdings ziemlich kompliziert. Augenzwinkern

Augenzwinkern

Das kann man aber sicherlich im Excel oder ähnlich hinbekommen Big Laugh

Big Laugh

11.05.2016, 16:11

HoschiJones

Auf diesen Beitrag antworten »

Zitat:

Original von willyengland
Ich sage mal folgendes voraus:

Die kürzeste Strecke ist die:
1. Von der untersten zur obersten Linie.
2. von der obersten zur zweituntersten Linie
3. von der zweituntersten Linie zur zweitobersten Linie
usw.

Ein Beitrag von: Willys gesunder Menschenverstand(tm) Big Laugh

Big Laugh

Nicht zwangsläufig. Was passiert z.B. wenn der Abstand a größer wird, sagen wir mal so groß wie D/2 oder gar D?
In diesem Fall habe ich alle Kreise übereinander bzw. 2 Spalten, die leicht versetzt sind.
Was machst Du bei einer anderen Anzahl - z.B. einer ungeraden?

Ich wollte mein Wissen an einen Nachfolger weitergeben, dass der sich leichter tut. Allerdings scheint es eben doch nicht so einfach zu sein Augenzwinkern

Augenzwinkern

11.05.2016, 17:04

HAL 9000

Auf diesen Beitrag antworten »

Bruteforce findet deine obige Lösung mit L=298.05 für n=5

Interessant wird es mit deinen Parametern D=70,a=10 ab n=8 Linien bzw. Kreisen:

Dann können die Kreise nämlich auch direkt übereinander platziert werden - so geschehen fünfmal in der optimalen Konfiguration für n=12:

L=379.47 mit den Kreisen in der Reihenfolge auf den Linien 1,8,11,4,7,10,3,6,9,2,5,12

[attach]41597[/attach]

12.05.2016, 09:41

HoschiJones

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Bruteforce findet deine obige Lösung mit L=298.05 für n=5

Interessant wird es mit deinen Parametern D=70,a=10 ab n=8 Linien bzw. Kreisen:

Dann können die Kreise nämlich auch direkt übereinander platziert werden - so geschehen fünfmal in der optimalen Konfiguration für n=12:

L=379.47 mit den Kreisen in der Reihenfolge auf den Linien 1,8,11,4,7,10,3,6,9,2,5,12

[attach]41597[/attach]

Respekt

Du hast dafür ein Programm geschrieben, mit den Bedingungen

$\begin{eqnarray*} Kreis_{n} \Rightarrow Kreis_{n+1} \leq \frac{D}{a} \end{eqnarray*}$

und

$\begin{eqnarray*} Kreis_{n} \Rightarrow Kreis_{n+2} \geq 2 \cdot D \end{eqnarray*}$ ?

12.05.2016, 10:43

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HoschiJones
Du hast dafür ein Programm geschrieben

Ja, allerdings ein "dummes" Bruteforce-Programm, welches für $\begin{align*} n\geq 13 \end{align*}$ unbrauchbar wird wegen unsäglichen Zeitverbrauchs.

Zitat:

Original von HoschiJones
mit den Bedingungen

$\begin{eqnarray*} Kreis_{n} \Rightarrow Kreis_{n+1} \leq \frac{D}{a} \end{eqnarray*}$

und

$\begin{eqnarray*} Kreis_{n} \Rightarrow Kreis_{n+2} \geq 2 \cdot D \end{eqnarray*}$ ?

Kann ich so nicht deuten und deswegen auch nicht bestätigen. Wie ich die Nebenbedingungen gemeint habe, steht oben unter a),b) nachzulesen, mit $\begin{eqnarray*} D=2R \end{eqnarray*}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »