동적 계획법으로 "바이러스 검사의 최적화 문제"해결

뭘 풀어


아마도 일부만 한국군과 독일이 일관바이러스 샘플을 혼합해 검사한 것 같다.
  • 한국 국방부, 속성 일관검사법?훈련병을 4명씩 검사체에 섞어 검사가 적은 예산으로 신속히 신병을 검사하려 한다
  • [기쁜 소식] 독일이 PCR 검사 용량을 10배로 늘리는 방법을 발명했다(전 세계에서 사용할 수 있다)
  • 그렇다면 혼합 검사체를 전제로 할 때 얼마나 효율적인 검사가 가능할까.이번엔 내가 그거 알아볼게.또 수학적 취미에서 계산한 것일 뿐, 어느 정도 비현실적인 일을 가정했기 때문에 그런 형식은 실용적이지 않다.
    전제로 다음과 같이 가정해 필요한 PCR 검사 횟수의 평균 최소치를 구한다.
  • 모든 사람이 감염될 확률이 $p달러라는 것을 알기 위한 사전 정보가 있습니다.
  • 검사 결과의 동태에 따라 다음에 어떤 샘플을 검사할지 결정할 수 있다.
  • 혼합된 샘플을 테스트한 결과 양성자가 한 명만 있으면 양성이 있고 전혀 없으면 음성이 있다.중간치 등을 얻을 수 없다.
  • 여러 번 같은 사람에게서 샘플을 채취할 수 있으며 채집에 필요한 비용을 고려하지 않는다.
  • 가음성, 가양성이 생기지 않는다.
  • 동적 계획법의 해법


    모든 사람의 양성과 음성을 확인하기 전의 최소 평균 검사 횟수는 $f이다1달러 (n) 로 이것을 사고 싶습니다.보조 함수 $f2(n), r(n, x)달러를 제작하여 다음과 같은 값을 역귀적으로 구해 보았습니다.
    $f_사람의 감염 상황($p$이외)에 대한 정보가 없는 경우의 최소 평균 검사 횟수
    $f_사람 중 양성자가 발견되었을 때의 최소 평균 검사 횟수
    만약 사람 중 적어도 1명이 양성이라면, 그 중에서 선택한 $x$는 양성자가 없는 조건부 확률의 함수를 나타낸다
    $ f_1(n)=\min_{1\leq x\leq n} 1+\{ 1-(1-p)^x\} f_2(x)+f_1(n-x) $
    $f_2(n)=\min_{1\le x\le n-1}1+\{1-r(n,x)\}\{f_2(x)+f_1(n-x)\}+r(n,x)f_2(n-x)$
    $r(n,x)=\frac{(1-p)^x\{1-(1-p)^{n-x}\}}{1-(1-p)^n}$
    $f_1(n)달러 해설: "$x$$$$1을 섞은 검사는 양성 확률 $1-(1-p)^x$입니다. 양성인 경우에만 $f2(x)달러입니다. 나머지 $n-x는 누구든지 검사가 필요합니다. $f1(n-x)$f1(n-x)$f1(n-x)달러검사"→$x=1,\cdots,n달러의 최소값은 $f$입니다.1달러 (n).
    $f_2(n)달러의 해설: "$x$$$$1의 검사를 혼합하면 양성 확률 $1-r(n,x)$이다. 양성의 경우 $x$f2(x)달러와 나머지 $n-x달러의 검사 $f1(n-x)달러, 음성의 경우 남은 $n-x달러는 사람만 양성이며, $f2(n-x)달러의 검사"→$x=1,3\cdots, n-1달러는 이 최소치 f$f$2달러.
    사람은 모두 음성이고 사람 중에 양성자가 있을 확률; ($사람 중에 양성자가 있을 확률) = ($사람 모두가 음성일 확률)×(남은 $n-x$사람이 양성자가 있을 확률)/($사람 중 양성자가 있을 확률)
    또한, 분명히 $f1(0)=0, f_2(1)=0달러입니다.($f2(0)$0인 중에는 양성이 있을 수 없기 때문에 정의할 수 없습니다.)이 공식에 근거하여 $f1(1)$→$f_2(2)$→$f_1(2)$→$f_2(3)$→$f_1(3)$→$\cdots $→$f_1달러 순으로 누적 계산하면 됩니다.동적 기획법.Mathematica에서 값을 캐시하면 계산 순서를 고려하지 않아도 일반적으로 값을 구한다.(리베이트 함수 등도 쉽게 계산할 수 있음)
    또한, $f1(n), f_2 (n) 는 2 (n) 달러의 계산에서 어느 $x$가 가장 작은 값을 냈는지 표시하는 함수가 $s1(n), s_2달러 (n) 로 이것도 미리 요구합니다.각 단계에서 몇 개의 샘플을 혼합해서 검사해야 한다는 전략을 보여줄 것이다.

    Mathematica로 써요.


    Mathematica 프로그램은 이런 느낌입니다.
    ClearAll[f1,f2,s1,s2]
    $RecursionLimit = Infinity;
    r[n_,x_,p_] :=(1-p)^x(1-(1-p)^(n-x))/(1-(1-p)^n);
    f1[n_,p_]:=({f1[n, p],s1[n,p]}= MinimalBy[Table[{1+(1-(1-p)^x)f2[x,p]+f1[n-x,p],x},{x,1,n}],First][[1]])[[1]];
    f2[n_,p_]:=({f2[n,p],s2[n,p]}= MinimalBy[Table[{1+(1-r[n, x,p])(f2[x, p]+f1[n-x,p])+r[n,x,p]f2[n-x,p],x},{x,1,n-1}],First][[1]])[[1]];
    f1[0,p_]=0;
    f2[1,p_]=0;
    $p=0.001.0002,\cdots,0.01달러,$n=1000달러1 (n) $의 값을 그립니다.
    ListPlot[Table[f1[n,p],{p,.01,.001,-.001},{n,1,100}],Joined->True,PlotLegends->Table["p="<>ToString[p],{p,.01,.001,-.001}],AxesLabel->{Style["n",Medium],Style["f_1(n)",Medium]}]

    $n=100달러라도 $p$가 충분하면 검사 횟수가 많이 줄어든다.

    검사 횟수 분포


    최선의 전략을 취할 때 검사 횟수의 분포도 살펴봐야 한다.몬테카로에서 해보면 재미있는 형식이 될 거예요.
    m = 200000;(*モンテカルロ回数*)
    p = 0.001;
    n = 1000;
    f1[n,p];(*これをあらかじめ計算しておかないとs1,s2が計算されない。*)
    data = RandomVariate[BernoulliDistribution[p], {m, n}];
    (*0,1の数字を確率1-p,pでm×n個発生させる。*)
    k1[d_] := Module[{d1 = d[[1 ;; s1[Length[d], p]]], d2 = d[[s1[Length[d], p] + 1 ;;]]},
    1 + If[Plus @@ d1 > 0, k2[d1] + k1[d2], k1[d2]]];
    (*与えられた0,1の列をs1[Length[d]]以前とそれより後に分割。前者の試験で陽性が出るか否かで場合分け。*)
    k2[d_] := Module[{d1 = d[[1 ;; s2[Length[d], p]]], d2 = d[[s2[Length[d], p] + 1 ;;]]}, 1 + If[Plus @@ d1 > 0, k2[d1] + k1[d2], k2[d2]]];
    (*与えられた0,1の列をs2[Length[d]]以前とそれより後に分割。前者の試験で陽性が出るか否かで場合分け。*)
    k1[{}] = 0;
    k2[{1}] = 0;
    dist = ParallelMap[k1, data];
    Histogram[dist, {1}, "PDF"]
    $n=1000,p=0.001달러의 경우 이렇게 분포됩니다.
    ! 평론 204-25012637.png
    그럼, 이렇게 합시다.

    어떻게 검사해야 하나요?


    구체적인 $n과 $p$p의 검사 절차는 $s입니다1(n), s_2달러 보시면 됩니다.각 단계에서 다음에는 반드시 몇 개의 샘플을 혼합하여 검사를 진행해야 한다p=0.01달러로 도표를 만들면 모양이 상당히 복잡해진다.(파란색은 $f 1(n)$, 주황색은 $f이 도표는 실수화하지 않고 계산되었지만 기계의 정밀도 실수에 오차가 생겨 형상이 조금 다르다.
    p = 1/100;
    f1[500, p];
    DiscretePlot[{s1[n, p], s2[n, p]}, {n, 0, 500}]

    더 구체적인 테스트 프로그램을 찾아보세요.
    p = 0.2
    f1[5, p];
    d = Range[5];
    k1[d_] := Module[{d1 = d[[1 ;; s1[Length[d], p]]],
    d2 = d[[s1[Length[d], p] + 1 ;;]]},
    Style[test @@ d1, Red][pos[k2[d1], k1[d2]], neg[k1[d2]]]];
    k2[d_] := Module[{d1 = d[[1 ;; s2[Length[d], p]]],
    d2 = d[[s2[Length[d], p] + 1 ;;]]},
    Style[test @@ d1, Red][pos[k2[d1], k1[d2]], neg[k2[d2]]]];
    k1[{}] = Nothing;
    k2[{x_}] := Nothing;
    k1[d] //. {pos[Nothing, x_] | pos[x_, Nothing] -> pos[x],
    pos[Nothing, Nothing] | pos[Nothing] -> pos,
    neg[Nothing, x_] | neg[x_, Nothing] -> neg[x],
    neg[Nothing, Nothing] | neg[Nothing] | neg[{}] -> neg} // TreeForm

    이것은 $n=5,p=0.2달러의 상황이다.맨 위에 있는 $test[1,2]달러는 샘플 1달러와 $2달러를 혼합하여 테스트를 진행하는 것을 의미한다.이 결과가 양성(pos)이라면 검사 대상인 34,5달러를 혼합한 단독 테스트도 실시한다.이러한 결과에 근거하여 한층 더 다음 층으로 진입하다.첫 번째 테스트가 음성(neg)이라면 샘플을 3, 4, 5달러에 섞어 테스트한다.만약 이 결과가 음성이라면 전체 인원의 음성은 확정된다.

    기타 해법


    동태계획법을 사용하기 전에 각 단계에서 가장 큰 평균 정보량을 얻기 위해 혼합인원을 차례로 선택하여 양성, 음성을 5분의 1로 나누도록 한다.이런 상황에서
    $s_1(n)=\min(n,-\frac{\log(2)}{\log(1-p)})$
    $s_2(n)=\min(n-1,\frac{\log\{1+n(1-p)\}-\log 2} {\log 1-p})$
    되다(실제로는 정수여야 하기 때문에 양성률의 50%에 가까운 쪽을 위로 또는 아래로 반올림해야 한다.)아무래도 동적 계획법보다는 조금 낮은 것 같아요.일부 최적화는 전체적인 최적화가 아니라 다른 세부 사항에 의한 것일 수 있다.그러나 최적해와는 큰 차이가 없다.
    또 폴 제이 나렌의'조금 센 확률 퍼즐'에도 같은 문제가 있었다.단, $n$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$k$의 가장 좋은 해답은 $\rac{1} {sqrtp}이고 평균 검사 횟수는 $n\{1+\sqrtp-(1-p)^\rac{1} {sqrtp]\}$입니다.동적 계획법보다 시간이 더 걸린다.
    동적 계획법보다 더 좋은 방법이 있나요?나는 이것이 가장 적합한 해결 방안이라고 생각하지만, 만약 더 좋은 방법을 발견한 사람이 있다면 나에게 알려주십시오.또 이번 시험은 평균치가 가장 작았지만 현실적으로'PCR 시험은 10달러까지 가능하다. 10달러가 넘는 검사에 필요한 확률을 최소화하고 싶다','채집기구 사용 수와 모든 사람의 사용 시간을 포함한 시간을 최소화하고 싶다'는 등의 수요가 더 높을 수 있다.다른 전략이 필요할 것 같습니다.

    좋은 웹페이지 즐겨찾기