여행 판매원 문제의 변형입니까?

Question

두 단어 목록의 기능에 관심이 있습니다. 두 단어 목록 사이에 순서 불규칙 편집 거리가 반환됩니다.

즉, 인수는 단어의 두리스트 (공백으로 구분한다고 가정)와리스트의 단어 편집 (또는 Levenshtein) 거리의 최소 합계가됩니다. "cat rat bat" 및 "rat bat cat" 사이

가

거리가 목록에있는 단어의 수는 동일하지 않은 경우 "rat bat cat" 및 "had fat bad", (4) 사이의 거리와 동일 할 것이다 0 거리 "cat rat bat" 사이 "fat had bad" 될 것이며, 짧은 목록 것 길이가 0 인 단어로 채 웁니다.

무력 사용하는 것보다 다른 해결책을 찾을 수 없습니다 (컴퓨터 과학 수업으로 육성되지 않은) 내 직감 :

|had|fat|bad| a solution 
---+---+---+---+ +---+---+---+ 
cat| 2 | 1 | 2 | | | 1 | | 
---+---+---+---+ +---+---+---+ 
rat| 2 | 1 | 2 | | 3 | | | 
---+---+---+---+ +---+---+---+ 
bat| 2 | 1 | 1 | | | | 4 | 
---+---+---+---+ +---+---+---+ 

첫 번째 행에서 시작을 열을 선택하고 이동 다음 열은 이미 방문한 열을 다시 방문하지 않아도됩니다. 모든 조합을 시도 할 때까지 반복하십시오.

내게 이것은 여행 판매원 문제와 약간 비슷합니다. 그것, 그리고 당신은 나의 특별한 문제를 어떻게 해결할 것입니까?

Answer 1

왼쪽의 격자에서 이미 보았 듯이 모든 단어 쌍의 편집 거리를 계산하여 시작할 수 있습니다. 이것은 다항식 시간 (n^2 편집 거리 계산)에서 쉽게 수행됩니다.

그런 다음 문제는 "최소 가중 2 분 일치"또는 이와 동등하게 "최대 가중 2 분 일치"로 설명 할 수 있습니다. 이것은 다항식 시간 (여행 세일즈맨보다 빠름)에서도 수행 할 수 있습니다. http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs

Answer 2

이 내용은 Levenshtein distance algorithm을 알아낼 수있는 완벽한 기회입니다. 이 알고리즘은 당신이 찾고있는 것과 정확히 일치 할 것입니다 (두 문자열 간의 최소 거리). 또한 매우 효율적입니다. 늘어나는 세일즈맨의 변형이라면 이것은 문제의 구조 때문에 다항식 시간으로 풀릴 수 있기 때문에 no 일 것입니다. 희망이 도움이됩니다.