동등성을 검사하는 똑똑한 알고리즘

일부 개체의 목록이 있다고 가정합니다.
우리는 어떤 물체가 같고 어떤 물체가 아닌지 말할 필요가 있습니다.
1이 2이고 2가 5와 같다고 가정하십시오.
그래서 1은 5와 같으므로 확인하지 않아도됩니다.

이 알고리즘이 있습니까?
모든 아이디어는 매우 훌륭합니다.

2011-12-22 Shikarn-O

그래서이 알고리즘의 입력은 무엇이며 출력은 무엇입니까? – NPE

정점이 객체이고 알려진 동일한 객체 사이에 모서리가있는 그래프가 있으면 다른 객체에 연결된 모든 객체도 같습니다. 따라서 객체 A가 객체 B와 같은지 테스트하려면 해당 그래프에서 A와 B 사이에 경로가 있는지 테스트하고 있습니다.

그래프 검색 알고리즘을 사용하여이를 수행 할 수 있습니다. Depth-first search이 좋은 시작일 것입니다.

연결된 모든 쌍을 찾으려면 Tarjan's algorithm을 사용하여 강력하게 연결된 모든 구성 요소를 찾을 수 있습니다. 각 구성 요소 내에서 모든 객체는 동일합니다.

출처

2011-12-22 15:59:32

Tarjan의 알고리즘은 강하게 연결된 구성 요소를위한 것으로 여기에서 그래프는 무 방향이고 정상적인 DFS는 연결된 구성 요소를 찾는데 충분합니다. – sdcvvc

@sdcvvc : 방향이 지정되지 않은 그래프가 방향성있는 그래프로 쉽게 변환됩니다 (방향이 지정되지 않은 각 가장자리에 대해 vu를 추가합니다. '). DFS는 충분하지만, 모든 등가 쌍을 찾기에는 비효율적이다 (V^2). –

Tarjan의 알고리즘은 O (V + E)가 더 복잡하지 않으며 DFS보다 구현하기가 조금 더 어렵지만 동일한 결과를 제공합니다. – sdcvvc

나는 이것이 동일한 요소 세트를 가지고 있다고 생각할 수 있다고 생각합니다. 그리고 IMO 분리 된 데이터 구조는 그러한 레코드 집합을 유지하는 데 매우 효율적입니다. 기본 아이디어는 우선 각 요소를 별도의 집합으로 두는 것입니다. 동등한 관계가 발생할 때마다 해당 요소가 속한 집합을 가져 와서 병합합니다. 경로 압축을 사용하면 병합 및 조회의 실행 시간이 부 로그입니다. http://en.wikipedia.org/wiki/Disjoint-set_data_structure

출처

2011-12-22 16:12:28 FUD

경로 압축을 사용하여 Disjoint Set strucutre을 원할 때. 구현이 매우 간단하며 성능은 O (1)에 가깝습니다.

출처

2011-12-22 16:16:14 japreiss

동등성을 검사하는 똑똑한 알고리즘

답변

관련 문제