Dhyang's method (2.5) 이게 이미 있었네

안녕히 계세요 여러분! 전 이 세상의 모든 굴레와 속박을 벗어 던지고 제 행복을 찾아 떠납니다!

저는 지난 시간에 다음 시간을 예고한 다음, 잠적했습니다.

 

근데 오늘 찾아보니까 굳이 D-index(더러운 index)를 사용하지 않더라도 루프가 있는 게임의 winning strategy (if there is any) 를 찾는 방법이 존재하더라고요?

이게 이미 있었네

 

혹시 궁금하신 분은

https://www.sciencedirect.com/science/article/pii/0097316586900580 를 보시거나, 

대충 google scholar 같은 웹사이트에 generalized Sprague-Grundy theorem을 찾아보시면 나옵니다.

근데 많이 더럽긴 해요

 

대충 설명을 하자면, 

1. Generalized function G(x) 를 정의합니다.

2. G(x) 는 non-negative integer와 infinite ordinal 로 이루어진 set입니다.

3. 이렇게 해놓고 시작 지점 을 {0,∞} 로 정의한다면?

4. 와! 놀랍게도 루프가 있어도 Grundy-index가 정의됩니다!

5. 이렇게 하고 합칠때는 똑같이 정수부분만 xor하고 무한이 존재하면 계승시키는 방식으로 정의를 한다면?

6. 와 이기는지 지는지 비기는지도 판별할 수 있습니다!

 

이게 이미 있었네

 

하지만 저는 아직 한가지를 알지 못했습니다.

그건 바로, D-index를 사용해 non-losing strategy를 구하는것이 이 방식보다 유의미하게 빠른지인데요

사실 위에 설명한 방법이 시복은 O(|V|+|E|) 라서 빨라 보이기는 하지만... 실제로 계산하는걸 구현하는게 이상하게 생긴 그래프에서는 엄청나게 어려울거 같은 기분이 들어서 (일단 제 짧은 생각으로는 우선 사이클을 모두 찾아내야 하는데 이거 딱봐도 np-hard의 냄새가 나죠?)

 

뭐 조금 더 정리가 되고 나서 (3)으로 돌아오도록 하겠습니다.

 

아니 근데 이게 이미 있었다니 너무한거 아니에요 😢