알고리즘은 사람이 그것을 해결하는 방법을 알고 있다면 나는 흥미로운 문제를 생각 간섭

Question

없이 켤 수 있습니다 및 궁금 얼마나 많은 레이더 타워 찾을 수 있습니다 : 도대체

가 많은 도시가 있습니다. 밥은 각 도시마다 레이더 타워를 만들었습니다. 각 도시는 지역 음악을 재생할 수 있어야합니다.

용의자는 모든 레이더 타워가 서로 간섭하므로 Bob 을 모두 꺼야합니다.

운 좋게도 밥은 그가 도시 사이에 놓은 방패를 발명했다. (일부는 일부는 도심 경계에 위치 함).

N 개 도시의 경우 N * (N-1)/2 개의 방패가 있습니다.

많은 쉴드가 파괴되었습니다.

당신은 그들 사이에 방패가없는 도시 쌍을 받았습니다. 어떤 간섭을 유발하지 않고 켤 수 있습니다 레이더 타워의 최대 수를 찾을 수에

작업입니다.

지금까지 나는 이것을 그래프로 표현하려고 시도했다. (도시 사이에는 방패가없는 경우 도시가 연결되어있다.) 가장 일반적인 색의 수를 최대화하는 그래프의 색을 찾는 것이다. 기본적으로 시작 노드를 선택하고 빨간색으로 만든 다음 모든 주변 노드가 파란색으로 이동 한 다음 빨간색으로 이동합니다. 더 빠른 방법이 있는지 궁금합니다.

Answer 1

http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29#Finding_maximum_independent_sets의 최대 독립 설정에 대한 질문이 아닙니까? (NP- 완전하지만 순진한 무차별 검색보다 지수 함수 알고리즘이 더 빠름)

Answer 2

2 개의 레이더 타워는 제공된 짝을 같이 사용하여 둘 사이에 차폐가없는 경우 동시에 켤 수 없습니다. 노드가 레이더 타워가 켜져 있음을 나타내는 나무의 가장 긴 깊이를 찾아 내면 가장 깊이가 긴 가지를 가져 와서 간섭없이 켜는 타워의 최대 수를 찾을 수 있습니다. 노드를 가져 가면 (예 : 타워 켜기) 해당 타워와 함께 방패가없는 다른 모든 타워를 비활성화해야합니다.