1
하자 E G 문제는 그래프에서 모든 에지의 집합 조건을 만족 G에서 정점의 작은 서브 세트 S 찾는 것이다 : S = E의 각 정점에서 나가는 모든 에지 합을 다른쪽에정점의 최소 서브 세트 찾기 - 백 트래킹? -
단어 : 가장자리는 거리이며 우리는 정점에 가로등을 배치 할 수 있습니다. 정점에 가로등을 배치하면이 정점에있는 모든 나가는 거리가 밝아집니다. 모든 거리를 밝게하는 방법을 찾는 방법은 무엇입니까?
역 추적보다 나은 점이 있습니까?
예, [정점 덮개] (http://en.wikipedia.org/wiki/Vertex_cover)를 해결하는 더 나은 방법이 있습니다. –
감사합니다. 문제의 이름을 지정할 수 없습니다. – Pavel