Minimaler Abstand bei mehreren Kreisen |
11.05.2016, 09:50 | HoschiJones | Auf diesen Beitrag antworten » | ||||
Minimaler Abstand bei mehreren Kreisen 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 für eine Bedeutung für das Problem haben sollen. Ist es etwa so, dass die Kreismittelpunkte nur auf diesen Linien liegen dürfen? 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
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
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 von minimiere man unter den Nebenbedingungen a) für alle , b) für alle . 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 » | ||||
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 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 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 oder zu finden, sondern es muss auch die richtige Reihenfolge/Anordnung gegeben werden. |
||||||
11.05.2016, 13:50 | HoschiJones | Auf diesen Beitrag antworten » | ||||
Brutforce, Permutation Ich dachte, dass ich ein geometrisches Problem angerissen habe 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 » | ||||
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. |
||||||
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) |
||||||
11.05.2016, 16:06 | HoschiJones | Auf diesen Beitrag antworten » | ||||
Das kann man aber sicherlich im Excel oder ähnlich hinbekommen |
||||||
11.05.2016, 16:11 | HoschiJones | Auf diesen Beitrag antworten » | ||||
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 |
||||||
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 » | ||||
Du hast dafür ein Programm geschrieben, mit den Bedingungen und ? |
||||||
12.05.2016, 10:43 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Ja, allerdings ein "dummes" Bruteforce-Programm, welches für unbrauchbar wird wegen unsäglichen Zeitverbrauchs.
Kann ich so nicht deuten und deswegen auch nicht bestätigen. Wie ich die Nebenbedingungen gemeint habe, steht oben unter a),b) nachzulesen, mit . |
|