7
Wpadłem na a spreadsheet, który wyjaśnia metodę sortowania zarówno wierszy, jak i kolumn macierzy zawierającej dane binarne, tak aby liczba zmian między kolejnymi wierszami i kolkami była zminimalizowana.Algorytm sortowania wierszy i colów według podobieństwa
na przykład, wychodząc z:
po 15 ręcznych czynności opisane w zakładkach spreadsheed, w poniższej tabeli otrzymano:
Chciałbym know:
- Jaka jest popularna nazwa tego algorytmu lub metody?
- jak zastosować go do większej tabeli (gdzie 2^n byłoby przepełnione ...)
- jak uogólnić ją na dane inne niż binarne, na przykład za pomocą odległości Levenshteina?
- , czy istnieje powiązanie kodu (Excel VBA, Python, ...) już realizuje to (w przeciwnym razie będę go pisać ...)
Dzięki!
To jest euklidesowa ścieżka hammiltonowska w {0,1}^n; Myślę, że mogą istnieć algorytmy aproksymacji stałego czynnika, ponieważ hampath jest ściśle powiązany z TSP (zarówno hampath, jak i TSP są np. Trudne dla ogólnych wykresów) i mamy algorytmy aproksymacyjne dla TSP, ale nie spodziewamy się optymalnego rozwiązania - chociaż Nie jestem do końca pewny, czy istnieje dowód twardości dla tej konkretnej przestrzeni, byłbym zaskoczony, gdyby to było w P. Nie wiem, co potrafi VBA, więc nie mogę powiedzieć, czy można zaimplementować przybliżenie tam algorytm. –
Po drugim spojrzeniu odległość nie jest faktycznie euklidesowa, ale odległość Hamminga; Nie znam algorytmów twardości ani algorytmów aproksymacji dla tego, ale prawdopodobnie istnieją. –
Powiązane: [Kody Gray] (https://en.wikipedia.org/wiki/Gray_code), dostępne również w wariantach n-ary. – Norman