Create a gist now

Instantly share code, notes, and snippets.

@fmhr /chokudai_search.cs Secret
Last active May 7, 2016

What would you like to do?
State BeamSearch(State FirstState){
Heap<State> HNowStates = new Heap<State>();
HNowState.push(FirstState):
int k = 100; // ビーム幅
for (size_t t = 0; t < MaxTurn; t++) {
Heap<State> HNextStates = new Heap<State>();
for (size_t 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;
}
State ChokudaiSearch(State FirstState){
Heap<State>[] HState = new Heap<State>[MaxTurn + 1];
for (size_t i = 0; i <= MaxTurn; i++) HStates[i] = newHeap<State>();
HStates[0].push(FirstState); chokudai幅
int ChokudaiWidth = 1;
while (TimeCheck()){
for (size_t t = 0; t < MaxTurn; t++) {
for (size_t i = 0; i < ChokudaiWidth; i++) {
if (HStates[t].top == null) break;
var NowState = HStates[t].pop();
foreach(var NextState in NowState.GetAllNextState()){
HStates[t+1].push(NextState);
}
}
}
}
var BestState = HStates[MaxTurn].pop();
return BestState;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment