다음은 로컬 최대 값을 찾을 수있는 위치를 제안하는 매우 추론적인 주장입니다. 를 풀기 위해 정확히 d 움직임 이 필요한 위치의 수라고 하자 . 이러한 위치에서 이동할 때마다 큐브는 거리 d – 1 , d 또는 d + 1로 이동합니다 . 따라서 액세스 가능한 총 N d – 1 + N d + N d + 1 위치가 있습니다. 각 위치에서 M 개의 이동 이있어 M 개의 새로운 위치로 이어집니다. 거리 d 에서의 위치엔디

$N_d$

$N_d$디

$d$

$d$디− 1

$d-1$

$d-1$디

$d$

$d$디+ 1

$d+1$

$d+1$Nd−1+Nd+Nd+1

$N_{d-1}+N_d+N_{d+1}$

$N_{d-1} + N_d + N_{d+1}$M

$M$

$M$M

$M$

$M$d

$d$

$d$이 위치 중 어느 것도 d + 1 거리에 있지 않은 경우 로컬 최대 값 입니다. 접근 가능한 위치 (물론, 그렇지 않습니다. 이것은 휴리스틱 부분 임)에서이 위치를 무작위로 균일하게 가져 오면 다음과 같습니다.M

$M$

$M$d+1

$d+1$

$d+1$

$$\begin{eqnarray} X_d &=& P\left[\text{ a given position at }d\text{ is a local max }\right] \\ &=& \left(\frac{N_{d-1} + N_d}{N_{d-1} + N_d + N_{d+1}}\right)^M \\ &=& \left(1 + \frac{N_{d+1}}{N_{d-1} + N_d}\right)^{-M}. \end{eqnarray}$$

거리 에서 예상되는 최대 극대값 은 N d X d 입니다.d

$d$

$d$NdXd

$N_d{X}_d$

$N_d X_d$

들어 큐브, 소정의 위치로부터 이동의 수는 M = 18 , 및 추정을위한 N의 D가 제공된다 20 신의 번호 . 이 값을 사용하여 예상되는 최대 극대값의 수는 N 16 X 16 = 0.2 , N 17 X 17 = 9 × 10 9 및 N 18 X 18 = 1.5 × 10 19 입니다. 따라서 지역 최대 값이 없을 것 같습니다3×3×3

$3\times 3\times 3$

$3 \times 3 \times 3$M=18

$M=18$

$M=18$Nd

$N_d$

$N_d$N16X16=0.2

$N_{16}{X}_{16}=0.2$

$N_{16} X_{16} = 0.2$N17X17=9×109

$N_{17}{X}_{17}=9\times {10}^9$

$N_{17} X_{17} = 9 \times 10^9$N18X18=1.5×1019

$N_{18}{X}_{18}=1.5\times {10}^{19}$

$N_{18} X_{18} = 1.5 \times 10^{19}$ . 에서 D = 17 , 위치의 총 수는 것으로 추정된다 12 × 10 (18)을 하나의 로컬 최대를 발견하기 전에 억 개 위치를 테스트하기 위해 예상 할 수 있도록. 마지막으로 d = 18 에서는 20 개의 위치마다 로컬 최대 값을 기대합니다.d≤16

$d\le 16$

$d \le 16$d=17

$d=17$

$d=17$12×1018

$12\times {10}^{18}$

$12 \times 10^{18}$d=18

$d=18$

$d=18$

---

답변