Massimizza il numero di triangoli nidificati

Per prima cosa, crea una lista di tutti i triangoli (sottoinsiemi di 3 punti). Quindi fai un confronto a coppie di ciascuno dei due triangoli T_i e T_j: o T_i è dentro T_j, T_j è dentro T_i o nessuna delle due bugie all'interno dell'altro.

Interpretalo come un grafico diretto, aciclico : i triangoli sono i vertici del grafico e ogni relazione "T_i è dentro T_j" definisce un bordo diretto da T_i a T_j. Ora trovare una sequenza massima di triangoli è solo il problema del percorso più lungo per questo tipo di grafici. E come puoi leggere nell'articolo di Wikipedia, esistono algoritmi di tempo lineare per risolvere questo problema.

"Tempo lineare" qui significa "lineare al numero di bordi" (il numero di coppie di triangoli in cui uno è all'interno dell'altro). Per n punti, devi considerare

t := C(n,3)=n*(n-1)*(n-2)/6

triangoli (vedi coefficiente binomiale ), e quindi un massimo di

C(t,2) = t*(t-1)/2 

coppie di triangoli, che possono essere un numero enorme con n crescente - è un polinomio di ordine O (n ^ 6). Ma poiché non ci si aspetta che la maggior parte delle coppie di triangoli del tipo "dove uno è dentro l'altro", mi aspetto che lo sforzo computazionale del mondo reale sia molto più piccolo. Per n sotto 100 non dovrebbe essere un problema trovare una soluzione direttamente.

Per n > = 1.000, questo approccio molto probabilmente non sarà abbastanza veloce da darti un risultato in un ragionevole lasso di tempo. Quindi, meglio provare a risolverlo con un algoritmo approssimativo come quello suggerito da @KonradMorawski, o (più facile da implementare) ricottura simulata . La "ricottura simulata" richiederà una fase di "piccola modifica", che può essere implementata rimuovendo uno o due triangoli scelti casualmente dalla "soluzione corrente", e quindi aggiungere nuovamente i triangoli con una sorta di "algoritmo greedy" con un po 'di casualità. Avrai sicuramente bisogno di sperimentare questi dettagli per vedere cosa funziona meglio per il tuo problema specifico. Come risorsa gratuita su questi argomenti, qui trovi un e-book che si occupa di diverse tecniche di ottimizzazione globale.

Se stai bene con una soluzione approssimata (non necessariamente la migliore possibile), potresti provare l'approccio genetico.

Trova una soluzione così così come punto di partenza - utilizzando un semplice algoritmo come quello suggerito da @Carra - quindi crea, per esempio, 1000 copie di questa soluzione iniziale e continua a modificarle casualmente. Cambiare punto, provare ad aggiungere più triangoli ecc.

Premia il miglior esemplare e getta via copie scadenti, ad es. dopo ogni generazione è possibile sovrascrivere l'intero pool genico con cloni del miglior 5%. Per ottenere i migliori risultati, diminuire la temperatura con il tempo - significa utilizzare una mutazione aggressiva all'inizio, ma una velocità di mutazione più lenta verso la fine per ottimizzare i risultati una volta raggiunto un livello di qualità elevato.

Dopo alcune iterazioni dovresti finire con una soluzione abbastanza buona.

Il mio istinto mi dice che questo è un problema NP-completo. Puoi provare a trovare una buona soluzione ma non la migliore.

Quindi sì, un inizio sarebbe prendere tre punti nel mezzo, iniziare da lì e creare un triangolo. Trova i punti più vicini a ciascuno di questi tre punti e prova a creare un nuovo rettangolo. Dovrebbe dare una soluzione decente nella maggior parte dei casi.

Per migliorare questo, puoi eseguirlo più volte con un numero di triangoli di partenza diversi. O aggiungi un po 'di casualità alla presa dei punti più vicini. Eseguilo alcune volte e mantieni la soluzione migliore che hai trovato.