1
개체를 두 세트로 나눈 프로그램에서 작업하고 있으며 각 개체가 다른 모든 개체와 얼마나 비슷한 지 측정하고 최적의 방법을 찾고 싶습니다. 그들을 함께 맞춰라.가중치가있는 부분과의 바이 패 타이트 일치
세트가 단어와 거리가 편집 거리로 정의 된 경우 세트 "this", "is", "a", "test"와 "and", "this" "is"(0 점), "is"(0 점), "a"및 "and"(0 점) "is"와 "this" 2 점), '최고'와 '시험'(점수 1 점)이 포함됩니다.
저는이 문제를 최대 2 부분 일치와 유사한 문제를 찾는 것으로 줄였습니다.
에지가 완전한 가중치를 갖는 2 부분 그래프가 주어지면 (a) 모든 꼭지점이 세트에서 하나의 에지만을 가지며 (b)이 세트에서 가중치의 합이되도록 가장자리 세트를 찾습니다. 최대 크기입니다.
이 문제는 NP 완료 (또는 그렇지 않더라도 알고리즘이 매우 느릴 수 있다고 생각합니다.)하다고 생각하지 않습니다. 몇 가지 좋은 방법으로 답을 추정 할 수있는 방법이 있습니까?
현재 최소 가중치 가장자리를 선택하고 연결된 노드를 제거한 후 반복합니다. 그러나 이것은 차선책으로 보입니다. 이 문제를 일종의 유동 문제 (일반적인 이항 일치와 마찬가지로)로 줄이는 것에 대해 생각해 보았습니다. 그러나이 경우에는 작동하지 않습니다.
최소 비용 - 최대 흐름으로 보입니다. – nhahtdh