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=