Eu tenho duas partições de e estou procurando a distância de edição entre elas.
Com isso, desejo encontrar o número mínimo de transições únicas de um nó em um grupo diferente necessário para passar da partição A para a partição B.
Por exemplo, a distância de {0 1} {2 3} {4}
dentro {0} {1} {2 3 4}
seria dois
Após a pesquisa, deparei-me com este documento, mas a) não tenho certeza se eles estão levando em consideração a ordem dos grupos (algo com o qual não me importo) à distância b) não tenho certeza de como ele funciona ec) Não há referências.
Qualquer ajuda apreciada
Respostas:
Esse problema pode ser transformado no problema de atribuição , também conhecido como problema de correspondência bipartida ponderada máxima.
Observe primeiro que a distância de edição é igual ao número de elementos que precisam ser alterados de um conjunto para outro. Isso é igual ao número total de elementos menos o número de elementos que não precisam ser alterados. Portanto, encontrar o número mínimo de elementos que não mudam é equivalente a encontrar o número máximo de vértices que não mudam.
Deixe e B = { B 1 , B 2 , . . . , B l } ser partições de [ 1 , 2 , . . . , n ] . Além disso, sem perda de generalidade, deixar k ≥ l (permitida porque e d i tA={A1,A2,...,Ak} B={B1,B2,...,Bl} [1,2,...,n] k≥l ). Então deixe B l + 1 , B l + 2 , ..., B k todos os conjuntos vazios. Então, o número máximo de vértices que não são alterados é:edit(A,B)=edit(B,A) Bl+1 Bl+2 Bk
onde é uma permutação de .[ 1 , 2 , . . . , K ]f [ 1 , 2 , . . . , K ]
Esse é exatamente o problema de atribuição em que os vértices são , ..., , , ..., e as arestas são pares com peso. Isso pode ser resolvido no tempo .A k B 1 B k ( A i , B j ) | A i ∩ B j | O ( | V | 2 log | V | + | V | | E | )UMA1 1 UMAk B1 1 Bk ( AEu, Bj) | UMAEu∩ Bj| O ( | V|2registro|V| + |V| |E| )
fonte
Veja o PDF deste artigo
http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.0030160
A definição da distância de edição é exatamente o que você precisa, eu acho. A partição 'referência' seria (arbitrária) uma das suas duas partições, a outra seria simplesmente a outra. Também contém citações relevantes.
Best, Rob
fonte
Ideia irritadiça da manhã de domingo que pode ou não estar correta:
Wlog, seja a partição com mais conjuntos, a outra. Primeiro, atribua nomes diferentes aos pares aos seus conjuntos . Em seguida, encontre a melhor nomenclatura para os conjuntos pelas seguintes regras:P 2 n 1 ( S ) ∈ Σ P 1 n 2 ( S ) P 2P1 1 P2 n1 1( S) ∈ Σ P1 1 n2( S) P2
Agora, você pode considerar as cadeias de bits de seus elementos em qualquer partição, ou seja, e ( com ). Então, a quantidade desejada é , ou seja, a distância de Hamming entre as seqüências de bits.w 2 = N 2 ( 1 ) ⋅ ⋯ ⋅ n 2 ( n ) n j ( i ) = n j ( S ) , i ∈ S ∈ P j d H ( w 1 , w 2 )W1 1= n1 1( 1 ) ⋅ ⋯ ⋅ n1 1( N ) W2= n2( 1 ) ⋅ ⋯ ⋅ n2( N ) nj( i ) = nj( S) , i ∈ S∈ Pj dH( w1 1, w2)
fonte