State BeamSearch(State FirstState)
    {
        Heap<State> HNowStates = new Heap<State>();
        HNowStates.push(FirstState);
        int k = 100; //ビーム幅
 
        for (int t = 0; t < MaxTurn; t++)
        {
            Heap<State> HNextStates = new Heap<State>();
            for (int i = 0; i < k; i++)
            {
                if (HNowStates.top == null) break;
                var NowState = HNowStates.pop();
                foreach (var NextState in NowState.GetAllNextState())
                {
                    HNextStates.push(NextState);
                }
            }
            HNowStates = HNextStates;
 
        }
        var BestState = HNowStates.pop();
        return BestState;
    }

ICAgIFN0YXRlIEJlYW1TZWFyY2goU3RhdGUgRmlyc3RTdGF0ZSkKICAgIHsKICAgICAgICBIZWFwPFN0YXRlPiBITm93U3RhdGVzID0gbmV3IEhlYXA8U3RhdGU+KCk7CiAgICAgICAgSE5vd1N0YXRlcy5wdXNoKEZpcnN0U3RhdGUpOwogICAgICAgIGludCBrID0gMTAwOyAvL+ODk+ODvOODoOW5hQoKICAgICAgICBmb3IgKGludCB0ID0gMDsgdCA8IE1heFR1cm47IHQrKykKICAgICAgICB7CiAgICAgICAgICAgIEhlYXA8U3RhdGU+IEhOZXh0U3RhdGVzID0gbmV3IEhlYXA8U3RhdGU+KCk7CiAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgazsgaSsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZiAoSE5vd1N0YXRlcy50b3AgPT0gbnVsbCkgYnJlYWs7CiAgICAgICAgICAgICAgICB2YXIgTm93U3RhdGUgPSBITm93U3RhdGVzLnBvcCgpOwogICAgICAgICAgICAgICAgZm9yZWFjaCAodmFyIE5leHRTdGF0ZSBpbiBOb3dTdGF0ZS5HZXRBbGxOZXh0U3RhdGUoKSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBITmV4dFN0YXRlcy5wdXNoKE5leHRTdGF0ZSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgSE5vd1N0YXRlcyA9IEhOZXh0U3RhdGVzOwoKICAgICAgICB9CiAgICAgICAgdmFyIEJlc3RTdGF0ZSA9IEhOb3dTdGF0ZXMucG9wKCk7CiAgICAgICAgcmV0dXJuIEJlc3RTdGF0ZTsKICAgIH0=