효과적인 풀이 알고리즘이 존재하지 않는다, NP 문제 중의 한 가지다라는 글들을 읽었는데
이게 정확히 어떤 의미인지 전문적인 수학 지식을 알지 못하는 일반인에게 잘 설명해 주실 분 없나요?
102회 98승 4패인데 실수로 패배한 회는 없고 100회까지만 해야 하는데 두 회 더 초과해서 해 버렸고 두 회 모두 승리했으니
100회까지의 기록은 96승 4패 승률 96%입니다.
100회 중 실수로(알고리즘대로 플레이 하지 못하고) 4회 패배해서 4회 더 시도했고 실수한 패배 4회의 기록을 제외하면
100회 85승 15패 승률 85%입니다.
100회 중 실수로 2회 패배해서 2회 더 시도했고 실수한 패배 2회의 기록을 제외하면
100회 48승 52패 승률 48%입니다.
승률이 높다고 생각하실 텐데 시간을 고려하지 않고 오직 실수 없이 추론하여
확실한 칸, 지뢰일 확률이 높거나 낮은 칸을 가려내서 승리하는 데에만 초점을 뒀습니다.
50 대 50 같아 보이는 상황이어도 모든 경우의 수를 따져 보면 그렇지 않은 경우가 제법 많더라고요.
운에 맡기는 것이 아니라 확률적으로 가장 안전한 선택을 하기 때문에
충분히 컴퓨터 알고리즘으로도 구현 가능하다고 생각하는데 어떻게 생각하세요?
글쓰기