알고리즘은 유향 그래프의 문제에 대한

Question

는 다음과 같은 문제에 대한 알고리즘으로 저를 도와주세요 -

는 사실의 집합을 감안할 때, 우리는 가능한 한 많은 중복을 제거하고 싶습니다. 이 문제와 관련된 사실은 대문자 간의 전이 관계의 구성원입니다. 따라서 각각의 사실은 AB와 같은 대문자 짝입니다. A는 B와 관련이 있습니다. 편지는 그 자체와 관련이있을 수도 있고 아는 것도 아니지만 과도 성은 유지됩니다 : A가 B와 관련이 있고 B가 C와 관련이 있다면 A가 C와 관련되어 있다고 추론하십시오. 알려진 [] []이 주어지고 모든 것을 추론 할 수있는 가장 작은 집합의 크기를 반환하는 minFacts 클래스를 만듭니다. 알려진 사실에 포함 된 사실로부터 추론 할 수 있습니다.

알려진 각 요소는 하나 이상의 공백으로 구분 된 하나 이상의 사실을 포함합니다. 가장 작은 사실 집합에는 알려진 것으로부터 추론 할 수 있지만 사실에는 포함되어 있지 않은 사실이 포함될 수 있습니다.

예를 들어

:

{ "AB AC CA의 AA의 BC", "AD"}

결과 : 4

AB, CA, BC와 AD 우리 모두 AA를 추론 할 수 있습니다 (AB, BC, CA는 transitivity에 의해 AA를 부여 함), AC (AB, BC는 transitivity에 의해 AC를 제공함), 알려진 모든 사실을 추론 할 수있는 더 작은 하위 집합은 없습니다.

피씨 - 숙제가 아닙니다. 온라인에서 발견되어 몇 시간 동안 풀 수 없었던 문제 ...

Answer 1

그래프의 spanning tree을 찾고 있습니다. 극대가 더 사이클 또는 모든 정점을 연결 모서리의 최소 세트로 포함되지 G의 에지의 세트로

연결된 그래프 G 의 스패닝 트리

도 정의 될 수있다.

스패닝 트리에서 사용자는 그래프를 최소한으로 나타냅니다. 에지를 추가하면 사이클이 생성되므로 노드 간의 관계에 중복 정보가 생성됩니다.

알고리즘 끝에는 연결되지 않은 노드가 남아있는 경우 (즉, MST가 접촉하지 않는 그래프의 노드가 있음) 의미하는 것은 얻은 스패닝 트리가 독립적 인 엔티티이며, 스패닝 트리의 노드와 그 노드에없는 노드를 연결하는 관계 (에지)가 없습니다.

더 많은 수학적 용어로, 스패닝 트리에 속한 노드와이 노드에 속하지 않은 노드는 분리 된 집합이며 그 중 아무 것도 빈 집합이 아닙니다.

노드 세트를 모두 사용할 때까지 나머지 하위 집합에서 MST 검색을 다시 수행하여 스패닝 포리스트를 생성 할 수 있습니다.