모든 조합 트리 알고리즘

Question

나무와 관련된 질문이 있습니다. 나는 "자동차"같은 주제에 대해 약 100 문장을 가지고 있습니다. 그 문장은 기본적으로 자동차에 대해 이야기합니다. 사용자가 검색어를 제출하면 "엔진"과 "기름"이라는 단어 사이의 단어 링크 조합을 모두 찾습니다. " 나는 "엔진"과 "기름"이 문장에서 유사한 단어의 임의의 수만큼 연결되도록 가능한 모든 단어 링크를 찾고 싶다.

예를 들어.

1. 엔진이 뜨거울 때 실행 중입니다.
2. 자동차에 엔진이 있습니다.
3. 자동차 오일을 사용하십시오.

이 경우 대답은 엔진 -> 자동차 - 오일 (3 단어 조합)입니다. 그리고 나는 가능한 모든 조합을 찾아 결국 "엔진"과 "오일"이 서로 연결되도록하고 싶습니다. 최단 경로 또는 최장 경로는 아니지만 가능한 모든 경로가 모든 방향과 단어로 실행됩니다. 물론 경로가 유사하지 않은 한 "엔진"과 "오일"에 도달하는 단어 조합이 1,000 개일 수도 있습니다.

이렇게하는 방법이 있습니까? 나는 빵을 먼저 사용하려고했지만 조금 까다 롭습니다. 예를 들어 조합이 가능할 수 있습니다.

1. 엔진 -> 자동차 -> 실행 -> 스톱 -> 오일
2. 엔진 -> 자동차 -> 오일
3. 엔진 ->이 빠른> BRAKE-> 오일

사람이 수 이걸 도와주세요. 여기서 논리와 아이디어는 무엇입니까? 이미 방문한 단어는 무시할 수 없습니다. 알고리즘을 바로 멈추고 모든 링크를 제공하지 않기 때문입니다.

도와주세요.

감사합니다.

fa323

Answer 1

귀하의 질문은 그 심지어 예에서, ... 그래서 underspecified 인 대답은 engine->an->oil를 포함하지 않는 이유는 명확하지 않다.

또한 실제로 나무와 관련이 없으며 그래프로 처리됩니다.

먼저해야 할 일은 그래프를 작성하는 방법을 결정하는 것입니다. 이렇게하는 합리적인 방법은 둘 다 특정 문장에 나타나는 경우 두 단어 사이에 가장자리를 두는 것입니다.

그러면 출력 할 내용을 결정해야합니다. 나는 당신이 모든 경로를 원한다는 것을 매우 의심합니다. 왜? 글쎄, 내가 설명한 그래프를 만들면 첫 번째 문장을 사용하더라도 엔진에서 오일까지의 경로가 순환 경로를 포함하지 않는 24 개의 경로가 있습니다. 그러나 이것이 어쨌든 당신이 원한다면, 깊이 우선 검색을 통해 그래프의 모든 비순환 경로를 찾을 수 있습니다. 스택을 누를 때 방문한 노드를 표시하고 꺼낼 때 표시를 해제 할 수 있습니다.