7
Mi sono imbattuto in a spreadsheet che spiega un metodo per ordinare sia le righe che le colonne di una matrice che contiene dati binari in modo che il numero di modifiche tra righe consecutive e colonne sia ridotto al minimo.Algoritmo per ordinare righe e colonne per somiglianza
Ad esempio, iniziando con:
Dopo 15 operazioni manuali descritte nelle schede della spreadsheed, la seguente tabella si ottiene:
desidero know:
- qual è il nome comune di questo algoritmo o metodo?
- come applicarlo alla tabella più grande (dove 2^n traboccherebbe ...)
- come generalizzare a dati non binari, ad esempio utilizzando la distanza di Levenshtein?
- se c'è qualche link per il codice (Excel VBA, Python, ...) già l'applicazione del presente (altrimenti lo scrivo ...)
Grazie!
Questo è il percorso hamiltoniano euclideo in {0,1}^n; Penso che potrebbero esserci algoritmi di approssimazione a fattore costante dal momento che hampath è strettamente correlato a TSP (sia Hapath che TSP sono np-hard per i grafici generali), e abbiamo algoritmi di approssimazione per TSP, ma non aspettatevi di risolverlo in modo ottimale - sebbene Non sono del tutto sicuro che esista una prova di durezza per questo specifico spazio, sarei sorpreso se fosse in P. Non so cosa può fare VBA, quindi non posso dirvi se è possibile implementare un'approssimazione algoritmo lì. –
Avendo un secondo sguardo, la distanza non è in realtà euclidea, ma la distanza di Hamming; Non conosco prove di durezza o algoritmi di approssimazione per quello, ma probabilmente esistono. –
Correlati: [Codici grigi] (https://en.wikipedia.org/wiki/Gray_code), disponibili anche come varianti n-ari. – Norman