Motywacja : Opracowując narzędzia do wersjonowania danych, zaczęliśmy szukać algorytmów do „różnicowania” dwóch zestawów liczb całkowitych, wymyślając sekwencję przekształceń, które przenoszą jeden zestaw liczb całkowitych na drugi. Udało nam się zredukować ten problem do następującego bardzo naturalnego problemu, który wydaje się mieć połączenia do edycji odległości, grupowania przez zamianę i minimalnej wspólnej partycji ciągów .
Problem : Otrzymujemy ciąg znaków, tzn. Ciąg liter, a naszym celem jest ujednolicenie go przy minimalnych kosztach. Oznacza to, że chcemy zmienić kolejność sekwencji, tak aby wszystkie podobne litery były obok siebie.
Jedyną dozwoloną operacją jest pobranie podsekwencji podobnych liter i przeniesienie tej podsekcji w dowolne miejsce, co kosztuje mnie 1 jednostkę.
Będziemy wdzięczni za wszelką pomoc charakteryzującą złożoność tego problemu!
Przykład :
- aabcdab: Input
- bcd aa ab: Po przeniesieniu pierwszego aa do pozycji tuż po „d”
- b bcdaaa: Po przesunięciu trailing b do pierwszej pozycji
Ponieważ powstały ciąg jest jednorodny, mamy koszt 2.
Zauważ, że nie jesteśmy w żaden sposób ograniczeni w odniesieniu do wyniku: dopóki jest on jednorodny, nie musimy zapewniać żadnej konkretnej kolejności.
źródło
Spójrz na liczbę zmian z jednej litery na drugą w swoim ciągu, które możesz postrzegać jako miarę niejednorodności łańcucha. Z każdym (użytecznym) ruchem podsekwencji zmniejszasz tę liczbę o jeden, jeśli podsekwencja, którą przenosisz, jest poprzedzona dwiema odrębnymi literami. W przeciwnym razie zmniejszysz niejednorodność o dwa.
Tak więc dla łańcucha ze zmianami k potrzebujesz najwyżej k - l + 1 ruchów, gdzie l jest liczbą różnych liter w łańcuchu, ponieważ na końcu pozostaną zmiany - 1 . Ponieważ ciąg długości n może mieć co najwyżej n-1 zmiany liter, może potrzebować co najwyżej n-l ruchów. Najmniejsza możliwa liczba to połowa tego.
Najlepsza strategia wydaje się zatem szukać podciągów postaci abbba i stamtąd odsunąć bbb. Jeśli nie ma już nic, przesuń cokolwiek. Nadal możesz próbować wykonywać te operacje, które tworzą nowe sytuacje abbba, ale myślę, że zysk będzie bardzo niewielki. Ponieważ najgorsza możliwa strategia (bez głupich ruchów, które zwiększają niejednorodność) wykorzystuje najwyżej dwa razy więcej ruchów niż optymalna, wydaje się, że niewiele, które możesz zyskać, nie ma żadnego uzasadnionego związku z wysiłkiem, jak odpowiedź Isaacga z charakterystyką jako NP-hard sugeruje. Chyba że tak naprawdę liczy się tylko liczba operacji ruchu i nie przejmujesz się czasem, aby zdecydować, które ruchy wykonać.
Najgorszym przypadkiem jest zatem ciąg znaków, w którym każda litera różni się od swojego poprzednika (i nie dostajesz żadnych premii abbba). Tutaj potrzebujesz wielu operacji liniowych na długości łańcucha i prawie równych tej długości.
W twoim przykładzie masz 5 -> 4 -> 3 zmiany, a 3 równa się liczbie liter (4) minus 1.
Uwaga dodatkowa: Dla alfabetu wielkości tylko dwóch każdy ruch, który nie przesuwa prefiksu lub sufiksu łańcucha, zmniejsza niejednorodność o dwa, a zatem każda sekwencja rozsądnych ruchów jest optymalna.
źródło