2
최근 나는 세트 커버 문제의 포크라고 생각되는 문제에 대해 작업하고 있습니다. 그러나 문제의 세트 수는 2^n만큼 큽니다. 그리고 내가 찾은 근사치는 너무 많은 세트가 없을 때만 효과가있는 것처럼 보입니다. 거기에 2^n 세트와 맞는 알로 그리가 존재하는지 궁금하네요?너무 많은 세트, 예를 들어 2^n 세트가있을 때 세트 커버에 appproximate 알고리즘이 있습니까?
답변 해 주셔서 감사합니다.
대략적인 비율은 ln (n)보다 작을 수 없습니다. 나는 set cover 문제에서 많은 수의 (2^n만큼 큰) 것을 처리 할 수있는 알고리즘이 있는지 알아 내야한다. –
입력 값이 너무 큽니다. 탐욕스러운 접근 방식을 사용할 수 있으며 원본 세트의 크기가 'n'인 경우 곧 대부분의 경우 표지를 찾을 수 있지만 더 나쁜 경우에는 좋은 결과를 기대할 수 없습니다. 너무 많은 시간이 걸리는 입력을 한 번 반복해야하지만 원래 문제 (새 스레드의 IMO)가 더 나을 것이라고 말하면 다른 방법을 제안 할 수 있습니다. –
내 문제의 n은 100보다 크고 더 커질 수 있으므로 반복 방법을 포기해야합니다. 나는 복잡성이 다항식이고 근사 비율이 적어도 하한 인 ln (n)에 도달 할 수있는 알고리즘을 작성하려고합니다. 나도 그래? –