Algoritmo che mette il punto in quadrato con la distanza minima massima

Sono bloccato su questo: avere un quadrato. Metti n punti in questo quadrato in modo che la distanza minima (non necessaria la distanza media) sia la più alta possibile.Algoritmo che mette il punto in quadrato con la distanza minima massima

Sto cercando un algoritmo che sarebbe in grado di generare le coordinate di tutti i punti dato il numero di essi.

risultati di esempio per n = 4; 5; 6:

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

Si prega di non menzionano, roba di base di calcolo potenza come provare un sacco di combinazione e poi nitpicking quella giusta e idee simili .

fonte

2010-04-27 Mikulas Dite

È questo lo stesso di "Circles in piazza"? http://en.wikipedia.org/wiki/Packing_problem#Circles_in_square – zaf

Lascia che l'OP dichiari se è compito o no, per favore. –

@zaf io non credo che questo sia legato ai circoli nelle piazze, lì i circoli toccare, ecco i punti respingono, anche se si assume i punti per essere centri del cerchio dei cerchi si sovrappongono. :) –

Questo è il problema circles in square imballaggio.

Si è discusso come problema D1 in Unsolved problems in geometry, da Hallard T. Croft, Kenneth J. Falconer, e Richard K. Guy, pagina 108.

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

pagine 109 e 110 contengono una lista di referenze.

fonte

2010-04-27 18:09:20 zaf

Davvero bello! Ora, come generare le coordinate. –

Ragazzi volete la prossima pagina con la lista dei riferimenti? – zaf

@zaf, potresti darci il titolo e l'autore di quel libro, se ha più informazioni su questo argomento? (O forse altri enigmi?) –

Si potrebbe fare un N body simulation dove i punti si respingono a vicenda, magari con un 1/r^2 forza. Il movimento dei punti sarebbe ovviamente vincolato dal quadrato. Inizia con tutti i punti approssimativamente al centro del quadrato.

fonte

2010-04-27 17:54:51

Sì, "potresti". Ma andrebbe bene? (Quali garanzie puoi dare? Puoi dire che è entro un certo fattore di ottimale, ad esempio?(Vedi il commento dell'OP in questione: "Per favore non menzionare cose basate sulla potenza di calcolo come provare un sacco di combinazioni e poi snellire quella giusta e idee simili.") – ShreevatsaR

Posso vedere una simulazione del corpo N essere utile per approssimazioni, però. –

"La minima distanza minima" equivale a un potenziale 1/r^infinito. Se si volesse creare delle approssimazioni in questo modo - che mi sembra un buon metodo euristico - si dovrebbe iniziare con 1/r^2 ma poi passare a potenze superiori quando si è vicini a una soluzione. –

Mikulas, ho trovato una pagina piena di esempi di immagini di soluzioni possibilmente optiimal, o attualmente più noti. Non è mio, quindi usalo a tuo rischio.

Vedi

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

Fonte:

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

fonte

2010-04-27 18:20:38

+1. Sospetto che questi siano effettivamente ottimali (numericamente), per due ragioni: usano la parola "risolvere" nel descrivere i loro algoritmi, e n diversi hanno un numero diverso di prove, suggerendo che probabilmente hanno raggiunto presto l'ottimalità. (Per essere sicuri, sarebbe meglio guardare la fonte e vedere se si fermano solo quando il divario di dualità va a 0, o cosa.) – ShreevatsaR

@ShreevatsaR: l'ottimismo è un altro argomento da dimostrare. ;] Abbastanza buono è abbastanza buono, a volte. –

Sì, lo so, sto solo dicendo che non solo sono abbastanza buone, ma sembrano anche ottimali. – ShreevatsaR

Algoritmo che mette il punto in quadrato con la distanza minima massima

risposta

Problemi correlati