Jak znaleźć najkrótszą reprezentację dla podzbioru zestawu energetycznego?

Szukam wydajnego algorytmu dla następującego problemu lub dowodu twardości NP.

Niech będzie zbiorem, a A ⊆ P ( Σ ) zbiorem podzbiorów Σ . Znaleźć sekwencję wagowo ∈ Ď * o najmniejszej długości tak, że dla każdego L ∈ A , jest k ∈ N w taki sposób, { w k + I | 0 ≤ i < | L | } = L .$\Sigma$$A\subseteq\mathcal{P}(\Sigma)$$\Sigma$$w\in \Sigma^*$$L\in A$$k\in\mathbb{N}$$\{ w_{k+i} \mid 0\leq i < |L| \} = L$

Na przykład dla słowo w = b a c jest rozwiązaniem problemu, ponieważ dla { a , b } jest k = 0 , dla { a , c } jest k = 1 .$A = \{\{a,b\},\{a,c\}\}$$w = bac$$\{a,b\}$$k=0$$\{a,c\}$$k=1$

Jeśli chodzi o moją motywację, staram się przedstawić zestaw krawędzi skończonego automatu, gdzie każda krawędź może być oznaczona zestawem liter z alfabetu wejściowego. Chciałbym zapisać pojedynczy ciąg, a następnie zachować parę wskaźników do tego ciągu na każdej krawędzi. Moim celem jest zminimalizowanie długości tego ciągu.

Wydaje mi się, że znalazłem redukcję ze ścieżki hamiltonowskiej , co dowodzi, że problem NP jest trudny.

Nazwij słowo świadkiem dla A , jeśli spełnia warunek z pytania (dla każdego L ∈ A , jest m ≥ 1 taki, że { w m + i ∣ 0 ≤ i < | L | } = L ) .$w\in\Sigma^*$$A$$L\in A$$m\geq 1$$\{w_{m+i}\mid 0\leq i<|L|\} = L$

Rozważ wersję decyzyjną pierwotnego problemu, tj. Zdecyduj, czy dla niektórych i k ≥ 0 istnieje świadek dla A o długości co najwyżej k . Problem ten można rozwiązać, używając pierwotnego problemu jako wyroczni w czasie wielomianowym (znajdź najkrótszego świadka, a następnie porównaj jego długość z k ).$A$$k\geq 0$$A$$k$$k$

Teraz rdzeń redukcji. Niech będzie prostym, niekierowanym, połączonym wykresem. Dla każdego v ∈ V niech L v = { v } ∪ { e ∈ E ∣ v ∈ e } będzie zbiorem zawierającym wierzchołek v i wszystkie jego przyległe krawędzie. Ustaw Σ = E i A = { L v ∣ v ∈ V } . Następnie $G=(V,E)$$v\in V$$L_v=\{v\}\cup\{e\in E\mid v\in e\}$$v$$\Sigma=E$$A=\{L_v\mid v\in V\}$$G$ma ścieżkę hamiltonowską wtedy i tylko wtedy, gdy jest świadek długości co najwyżej 2 | E | + 1 .$A$$2|E|+1$

Dowód. Niech będzie ścieżką hamiltonowską w G, a H = { e 1 , e 2 , … , e n - 1 } zbiorem wszystkich krawędzi ścieżki. Dla każdego wierzchołka v , określa zestaw U v = l v ∖ H . Wybierz dowolną kolejność a v dla każdego U V . Słowo$v_1e_1v_2\ldots e_{n-1}v_n$$G$$H=\{e_1, e_2, \ldots, e_{n-1}\}$$v$$U_v=L_v\setminus H$$\alpha_v$$U_v$ jest świadkiem dla A , ponieważ L v 1 jest reprezentowany przez podłańcuch α 1 e 1 , L v n przez e n - 1 α n i dla każdego v i , i ∉ { 1 , n } , L $w=\alpha_{v_1}e_1\alpha_{v_2}e_2\ldots e_{n-1}\alpha_{v_n}$$A$$L_{v_1}$$\alpha_1e_1$$L_{v_n}$$e_{n-1}\alpha_n$$v_i$$i\notin\{1, n\}$ jest reprezentowany przeze i - 1 u v i ei. Ponadto każda krawędź wEwystępuje dwa razyww,z wyjątkiem| V| -1krawędzie wH, które występują raz, a każdy wierzchołek wVwystępuje raz, dając| w| =2| E| +1.$L_{v_i}$$e_{i-1}u_{v_i}e_i$$E$$w$$|V|-1$$H$$V$$|w|=2|E|+1$

Na innym kierunku, niech będzie dowolnym świadka A o długości co najwyżej 2 | E | + 1 . Oczywiście, każdy e ∈ E i v ∈ V występuje w w co najmniej raz. Bez straty ogólności załóżmy, że każdy e ∈ E występuje w co najwyżej dwa razy i za każdym v ∈ V zachodzi dokładnie jeden raz; w przeciwnym razie można znaleźć krótszego świadka, usuwając elementy z w . Niech H ⊆ E będzie zbiorem wszystkich krawędzi występujących w$w$$A$$2|E|+1$$e\in E$$v\in V$$w$$e\in E$$w$$v\in V$$w$$H\subseteq E$ dokładnie raz. Biorąc pod uwagę powyższe założenia, utrzymuje, że | w | = 2 | E | - | H | + | V | .$w$$|w|=2|E|-|H|+|V|$

Rozważmy ciągły podciąg postaci u e 1 e 2 ... e k v , gdzie u , v ∈ V , e ja ∈ E . Mówimy, że u , v sąsiadują ze sobą. Należy zauważyć, że jeśli e I ∈ H , a następnie e I = { u , v } , ponieważ e I występuje tylko raz, lecz przylega do dwóch wierzchołków G . Dlatego co najwyżej jeden$w$$ue_1e_2\ldots e_kv$$u,v\in V$$e_i\in E$$u,v$$e_i\in H$$e_i=\{u,v\}$$e_i$$G$ mogą być H . Podobnie żadna krawędź w H nie może wystąpić w w przed pierwszym wierzchołkiem ani po ostatnim wierzchołku.$e_i$$H$$H$$w$

Teraz są zatem wierzchołki | H | ≤ | V | - 1 . Stąd wynika, że | w | ≥ 2 | E | + 1 . Ponieważ zakładamy | w | ≤ 2 | E | + 1 , otrzymujemy równość. Stamtąd dostajemy | H | = | V | - 1 . Zgodnie z zasadą szuflady istnieje krawędź od $|V|$$|H|\leq |V|-1$$|w|\geq 2|E|+1$$|w|\leq 2|E|+1$$|H|=|V|-1$$H$między każdą parą wierzchołków sąsiadujących w . Oznaczają H 1 H 2 ... H n - 1 wszystkie elementy z H, w których się znajdują wag . Wynika stąd, że v 1 H 1 V 2 h 2 ... h n - 1 v n jest ścieżki Hamiltona w G . $w$$h_1h_2\ldots h_{n-1}$$H$$w$$v_1h_1v_2h_2\ldots h_{n-1}v_n$$G$$\square$

Ponieważ problem decydowania o istnieniu ścieżki hamiltonowskiej jest trudny dla NP, a powyższa redukcja jest wielomianowa, pierwotny problem jest również trudny dla NP.