Algorithmus Putting Point in Quadrat mit maximalen Mindestabstand

Ich bin auf diesem fest: Haben Sie ein Quadrat. Setzen Sie n Punkte in dieses Quadrat, so dass die minimale Entfernung (nicht die durchschnittliche Entfernung) die höchstmögliche ist.Algorithmus Putting Point in Quadrat mit maximalen Mindestabstand

Ich bin auf der Suche nach einem Algorithmus, der in der Lage sein würde, die Koordinaten aller Punkte zu erhalten, wenn sie gezählt werden.

Beispiel Ergebnisse für n = 4; 5; 6:

Example results for n=4;5;6 http://i40.tinypic.com/ohrb44.png

Bitte die richtigen und ähnliche Ideen nicht Computing-Power-basierte Sachen erwähnen, wie viel Kombination versuchen, und dann Erbsenzählerei .

Quelle

2010-04-27 Mikulas Dite

Ist dies das gleiche wie "Circles in square"? http://en.wikipedia.org/wiki/Packing_problem#Circles_in_square – zaf

Lassen Sie das OP erklären, ob es Hausaufgaben ist oder nicht, bitte. –

@zaf ich denke nicht, dass dies mit den Kreisen in Quadraten zusammenhängen würde, da berühren sich die Kreise, hier stoßen die Punkte ab, selbst wenn man annimmt, dass die Punkte Zentren des Kreises sind, würden sich die Kreise überlappen. :) –

Dies ist das circles in square Verpackungsproblem.

Es wird als Problem D1 diskutiert in Unsolved problems in geometry, von Hallard T. Croft, Kenneth J. Falconer und Richard K. Guy, Seite 108.

alt text http://i41.tinypic.com/2s0z8gh.png

Seiten 109 und 110 enthalten ein Referenzenliste.

Quelle

2010-04-27 18:09:20 zaf

Wirklich schön! Jetzt, wie man die Koordinaten erzeugt. –

Sie wollen die nächste Seite mit der Referenzliste? – zaf

@zaf, könnten Sie uns den Titel und Autor dieses Buches geben, wenn es weitere Informationen zu diesem Thema gibt? (Oder möglicherweise andere Rätsel?) –

Sie könnten eine N body simulation, wo die Punkte sich abstoßen, vielleicht mit einer 1/r^2 Kraft. Die Bewegung der Punkte wäre offensichtlich durch das Quadrat eingeschränkt. Beginnen Sie mit allen Punkten ungefähr in der Mitte des Platzes.

Quelle

2010-04-27 17:54:51

Ja, du könntest "könnte". Aber wäre es gut? (Welche Garantien können Sie geben? Können Sie sagen, dass es innerhalb eines bestimmten optimalen Faktors liegt, sagen wir?) (Siehe den OP-Kommentar in Frage: "Bitte nicht Rechenleistung-basierte Sachen wie viel Kombination und dann picken die richtige und ähnliche Ideen.") – ShreevatsaR

Ich kann eine N-Körper-Simulation sehen, die für schnell hilfreich ist Näherungen. –

"Maximale minimale Entfernung" entspricht einem 1/r^unendlich Potential. Wenn man auf diese Weise Annäherungen erstellen möchte - was mir als eine gute heuristische Methode erscheint -, sollte man mit 1/r^2 beginnen, aber dann zu höheren Kräften übergehen, wenn man nahe an einer Lösung ist. –

Mikulas, ich fand eine Seite voller Bildbeispiele von möglicherweise optimalen oder derzeit bekanntesten Lösungen. Es gehört mir nicht, also benutze es mit deinem eigenen Risiko.

Siehe

http://www.ime.usp.br/~egbirgin/packing/packing_by_nlp/numerical.php?table=csq-mina&title=Packing%20of%20unitary-radius%20circles%20in%20a%20square

Quelle:

http://www.ime.usp.br/~egbirgin/packing/packing_by_nlp/

Quelle

2010-04-27 18:20:38

+1. Ich vermute, dass diese tatsächlich (numerisch) optimal sind, und zwar aus zwei Gründen: Sie verwenden das Wort "lösen", um ihre Algorithmen zu beschreiben, und verschiedene n haben unterschiedliche Anzahl von Versuchen, was vermuten lässt, dass sie möglicherweise schon früh Optimalität erreicht haben. (Um sicher zu sein, wäre es besser, auf die Quelle zu schauen und zu sehen, ob sie nur aufhören, wenn die Dualität auf 0 geht oder was.) – ShreevatsaR

@ShreevatsaR: Optimalismus ist ein anderes Thema, das man beweisen muss. ;] Gut genug ist manchmal gut genug. –

Ja, ich weiß, ich sage nur, dass diese nicht nur gut genug sind, sie scheinen auch wirklich optimal zu sein. – ShreevatsaR

Algorithmus Putting Point in Quadrat mit maximalen Mindestabstand

Antwort

Verwandte Themen