najdłuższa lista słów z pasującymi literami początkowymi i końcowymi

Mój przyjaciel dał mi problem, który według niego jest łatwy, ale nie mogę wymyślić dobrego algorytmu, aby go użyć.

Otrzymujesz 100 losowych angielskich słów. Musisz znaleźć najdłuższy ciąg słów, w którym ostatnia litera w jednym słowie odpowiada pierwszej literze w następnym słowie. Możesz użyć każdego słowa tylko raz.

Na przykład, jeśli podano Ci słowa „kot”, „pies”, „tamto”, najdłuższym ciągiem, jaki możesz zrobić, byłoby „kot -> tamto”. Gdyby podano Ci słowa „mysz”, „łoś”, „jednorożec”, najdłuższym ciągiem, który możesz zrobić, byłoby tylko jedno słowo (ponieważ żadne z tych słów nie łączy się). Jeśli podano Ci słowa „ptak”, „danie”, „harb”, najdłuższym ciągiem, jaki możesz zrobić, byłoby „harb -> ptak -> danie” (lub „danie -> harb -> ptak” lub „ptak - > dish -> harb ").

Wpadłem na pomysł modelowania tego jako ukierunkowanego grafu cyklicznego. Każdy węzeł byłby tylko słowem, z wierzchołkami przechodzącymi do każdego słowa / węzła, które zaczynały się na literę tego słowa.

+-------+         \ +------+
|  cat  |-----------| that |
+-------+         / +------+
    |                  |
   \|/                 |
+-------+ /            |
|  the  |--------------+
+-------+ \

Ten problem wydaje się być najdłuższym wyszukiwaniem ścieżki , czyli NP-Hard.

Czy jest na to lepszy sposób? A może nawet jakiś algorytm aproksymacyjny, który można zastosować? Lub jakiś sposób na wykorzystanie cech języka angielskiego w celu zmniejszenia przestrzeni wyszukiwania?

Myślę, że jest to związane z problemem najdłuższej ścieżki (LP), o którym wspominałeś, ale jest nieco inny. Podstawowa różnica polega na tym, że problem LP ma wyższy stopień łączności niż sugerowany problem. Ograniczając połączenia do ostatniej i pierwszej litery, usuwasz dużą liczbę potencjalnych kombinacji.

Oto jak poleciłbym rozwiązanie tego problemu:

1. Dla każdego słowa na liście policz możliwe połączenia i połączenia.
2. Odrzuć wszystkie słowa, które mają 0 ins i 0 out.
3. Zidentyfikuj początkowy zestaw „słów początkowych” o najniższej liczbie wejść i wyjść, a wyjścia muszą być większe niż 0.
4. Każde słowo początkowe otrzymuje własną kopię roboczą liczby połączeń wejścia / wyjścia. To stanowi czoło łańcucha.
5. Dla każdego łańcucha określ listę „następnych słów” na podstawie:
   
   • ostatnia litera początkowego lub poprzedniego słowa
   • najmniejsza liczba połączeń wejściowych i wyjściowych (ponownie, wyjścia muszą być większe niż 0)
6. Dla każdego next wordpowtórz krok 5, aż łańcuch się zakończy.

Weź pod uwagę, że:

• Będziesz musiał śledzić długość łańcuchów i mieć jakiś globalny mechanizm identyfikujący najdłuższy łańcuch.

• Konieczne będzie również usunięcie każdego słowa z roboczej kopii liczników połączeń, aby uniknąć pętli rekurencyjnej.

• W pewnym momencie łańcuch się zakończy i musisz wybrać słowo z zerową liczbą połączeń.

• Konieczne może być ponowne obliczenie wejść / wyjść, gdy słowa są usuwane z list roboczych. Na pierwszy rzut oka nie sądzę, że będzie to konieczne, ponieważ ogólne zestawy będą stosunkowo niewielkie. Jeśli przeskalowałeś do 1000 słów, wówczas statyczne zliczanie może spowolnić konwergencję algorytmu.

Uważałem to za problem z pakowaniem. Dla mnie połączenia wejściowe i wyjściowe identyfikują kształt, który ma być zapakowany. Im niższe połączenia, tym bardziej dziwny kształt. Im bardziej dziwny kształt, tym szybciej chcę go spakować, ponieważ zauważyłem, że mam mniejsze szanse na spakowanie dziwnego kształtu, tym później dostałem się do łańcucha.

Jako przykład:

{dog, gopher, alpha, cube, elegant, this, that, bart}

dog     0, 1
gopher  1, 0
alpha   0, 0
cube    0, 1
elegant 1, 2
this    3, 0
that    2, 1
bart    0, 2

//alpha is dropped with 0 in and 0 out.
//two candidates found: dog, cube

//chain 1
dog => gopher
//chain 2
cube => elegant => that => this

//Note 1: the following chain won't occur due to selection rules
//that takes priority over this because of output count
cube => elegant => this

//Note 2: this chain won't occur either due to selection rules
bart => that => this

Jeśli utworzysz macierz 26X26 do reprezentowania ukierunkowanego wykresu wierzchołka jako każdego alfabetu i słów jako krawędzi. Na przykład słowo - APPLE łączy wierzchołek A i E z krawędzią skierowaną od A do E. Teraz problem sprowadza się do znalezienia największego szlaku Eulera (ścieżki, która obejmuje maksymalną liczbę krawędzi, odwiedzania każdej krawędzi po możliwym powtórzeniu wierzchołków) na wykresie. Jednym z algorytmów O (E) byłoby uruchamianie losowo z pary wierzchołków. Znajdź ścieżkę między nimi. Następnie rozluźnij ścieżkę, aż będzie to możliwe.

aktualizacja @ GlenH7 Niedawno rozwiązałem podobne pytanie na stronie www.hackerearth / jda, były względne oceny w odniesieniu do najlepszego rozwiązania i uzyskałem najwyższe oceny z następującym przybliżeniem-

Podana lista słów. Znajdź najdłuższy łańcuch, jaki mogą być przez nie uformowani. Łańcuch jest ważny, jeśli każde słowo zaczyna się od litery * kończącej się na końcu ostatniego słowa.

Approch =

1) wykonaj wykres alfabetów jako wierzchołki, a słowa jako krawędzie. Zamiast używania wielu krawędzi użyj jednej o wadze równej liczbie krawędzi.

2) znajdź mocno połączony składnik wykresu z maksymalnymi krawędziami. Tymczasowo odrzuć inne krawędzie.

3) Dla każdego wierzchołka wyrównaj jego niezależność do jego wierzchołka.

4) Teraz istnieje ich obwód eulerowski na wykresie. Znajdź to.

5) Teraz na pozostałym wykresie (wrt wykres orignalny znajdź najdłuższy szlak z pierwszym wierzchołkiem w wybranym silnie połączonym składniku. Myślę, że jest to NP trudne.

6) Uwzględnij powyższą ścieżkę w obwodzie elerskim, przekształcając obwód eulera w szlak.

Dlaczego - akceptuję, że to pytanie jest najprawdopodobniej trudne NP (zgadnij, nie mówiąc matematycznie). Ale powyższe podejście działa najlepiej, gdy istnieje długa lista (1000+) równomiernie rozłożonych słów (tj. Nie jest przeznaczona do wc dla powyższego podejścia). Załóżmy, że po przekonwertowaniu danej listy na wspomniany powyżej wykres, na szczęście okazuje się, że jest to wykres euleryjski ( warunki można znaleźć na stronie http://en.wikipedia.org/wiki/Eulerian_path ), a następnie bez wątpienia możemy powiedzieć tę odpowiedź powyższym pytaniem jest P i faktycznie jest to ścieżka eulera na wykresie (zobacz http://www.graph-magics.com/articles/euler.php, aby uzyskać bardzo prosty approch, aby to zrobić i zobacz to, aby sprawdzić, czy twój wykres ma singiel http://www.geeksforgeeks.org/strongly-connected-components/a jeśli nie, tymczasowo wyczyść inne małe scc, ponieważ istnieje ścieżka eulerowska dla pojedynczego scc). Dlatego w przypadku nieszczęśliwych przypadków (które są prawie wszystkimi przypadkami) próbuję przekonwertować je na szczęśliwe przypadki (tzn. Spełniony jest warunek śladu Eulera). Jak to zrobić? Próbowałem zwiększyć wyszukiwanie głębokości dla nieistotnych krawędzi (zestaw krawędzi na ścieżce patrząc od wierzchołka o stopniach większych niż stopniach i kończących się na wierzchołkach o stopniach większych niż stopni). Zwiększenie wyszukiwania głębokości oznacza, że ​​najpierw szukałem całego zestawu jednej krawędzi ścieżki, niż dwóch krawędzi ścieżki i tak dalej. Na pierwszy rzut oka może się wydawać, że i-sza głębokość zajmie O (węzły ^ i), a zatem całkowity czas złożoności O (węzły + węzły ^ 2 + węzły ^ 3 + ....), aż będzie to szczęśliwy przypadek. Ale amortyzowana analiza ujawni, że to O (krawędzie). Po zmniejszeniu szczęśliwy przypadek znajduje obwód Eulera.

Do tej pory był to czas wielomianowy. To dałoby prawie najlepsze rozwiązanie. Ale aby dalej zwiększyć swoje rozwiązanie (idealne rozwiązanie jest trudne NP), spróbuj chciwego podejścia na pozostałym wykresie, aby znaleźć długą ścieżkę, patrząc na jeden z wierzchołków w wybranym scc. Teraz dodaj to do znalezionego powyżej szlaku Eulera, aby dalej go zwiększyć.

Pomysł:

Najpierw utwórz dwie mapy (skróty), powiedzmy S i E, od liter alfabetu do słów; pierwsza, S, odwzorowuje litery początkowe na słowa, druga, E, robi to samo z literami końcowymi.

Np. Jeśli słownik składa się z:

ptak, danie, pies, harb

mamy:

S:

a -> [ ]
b -> [ bird ]
c -> [ ]
d -> [ dish, dog ]
...
h -> [ harb ]
...

i,

E:

a -> [ ]
b -> [ harb ]
c -> [ ]
d -> [ bird ]
...
g -> [ dog ]
h -> [ dish ]
...

Następnie, używając S i E do szybkiego wyszukiwania, utwórz las (zestaw drzew), o tym samym rozmiarze co słownik, z pierwiastkami przy każdym słowie i nie pozwalający na pojawienie się słowa więcej niż raz na drzewie - buforuj głębokości drzew podczas ich konstruowania:

bird (depth: 2)
   dish
      harb
   dog

dish (depth: 3)
   harb
      bird
         dog

dog (depth: 0)

harb (depth: 2)
   bird
      dish
      dog

Na koniec iteruj po lesie i znajdź drzewo (drzewa) o największej głębokości.

Rozwiązania będą znajdować się na osi potomnej tych drzew.

Na przykład,

dish / harb / bird / dog

powyżej.