7
Je suis tombé sur a spreadsheet qui explique une méthode pour trier les lignes et les colonnes d'une matrice qui contient des données binaires afin que le nombre de changements entre les lignes consécutives et les cols est minimisé.Algorithme pour trier les lignes et les colonnes par similarité
Par exemple, en commençant par:
Après 15 étapes manuelles décrites dans les onglets de la spreadsheed, le tableau suivant est obtenu:
Je voudrais connaître:
- quel est le nom commun de cet algorithme ou de cette méthode? Comment l'appliquer à une table plus grande (où 2^n déborderait ...)
- comment le généraliser à des données non binaires, par exemple en utilisant la distance de Levenshtein?
- s'il y a un lien vers le code (Excel VBA, Python, ...) applique déjà cette (sinon je vais l'écrire ...)
Merci!
C'est le chemin hamiltonien euclidien dans {0,1}^n; Je pense qu'il pourrait y avoir des algorithmes d'approximation à facteur constant puisque hampath est étroitement lié au TSP (les deux HMPath et TSP sont np-durs pour les graphes généraux), et nous avons des algorithmes d'approximation pour TSP, mais ne nous attendons pas à le résoudre Je ne suis pas entièrement sûr qu'une preuve de dureté existe pour cet espace spécifique, je serais surpris si c'était dans P. Je ne sais pas ce que VBA peut faire, donc je ne peux pas vous dire si vous pouvez mettre en œuvre une approximation algorithme là. –
Ayant un second regard, la distance n'est en fait pas euclidienne, mais la distance de Hamming; Je ne connais pas les preuves de dureté ni les algorithmes d'approximation pour celui-là, mais ils existent probablement. –
En relation: [Codes Gray] (https://en.wikipedia.org/wiki/Gray_code), également disponible en tant que variantes n-aire. – Norman