修改文章
标题:
内容:
OK, let's go on with what we talked about..... As we have already said, the biggest problem of the algorithm above is, we are not sure if he can find an answer. And all the problems because of the sentence ' list=prepend(newstate, list)'. we could see, if we always put a serial of new states at the head of the list, and pick the first one to choose what next action will be. So, if we change that into 'list=APPend(newstate, list)', OK, problem sloved.(This is the Breadth-First search) The difference between the two algorithms is the first one is continue trying the First Action of NEXT step after he tried the first action of This step, but the latter one is try every possible actions in This step, and then, every actions in NEXT. It is important to make clear understanding on the difference, because we'll see later, this difference is a way which we could speed up our algorithm. But, we find the new algorithm's running time is O(m^n)(where m is the number of choices and n is the number of actions which should be exectued). And if we conbine the two algorithm together, we'll found, the running time is still O(m^n). OK, let's first see the new algorithm........... (We'll also do some more speed up, no revisiting states) list<-{A,B,C(state)}; while (list!=empty){ //not necessarily being null DO s<-Head(list); if (s==SpecialState) State<-Pop(State); Until (s!=SpecialState) //SpecialState is not a real state, but a mark to pop a state in State. list<-Rest(list); State<-s; //we save this state into a state list if (s is goal) return State; else if (State.length<= BOUND){ //BOUND is a value we set to determin we must solve the problem in how many steps. That is also, how many levels we could search. list<-prepend(SpecialState,list); // make a note that search in a new level begin while (Action!=empty ){ //Action is a set in which there are all the actions could apply on this state act<-Head(Action); Action<-Rest(Action); newstate<-apply(act); if (newstate NOT IN State) list<-prepend(newstate, list); } } else //If when we reach the max steps we have setted, and there is still no solution State<-Pop(State); //Last action we exectued is wrong, no more considering about that, and back to the last state, try next action. } return SORRY OK, later, we'll try to give a program in Java to solve this problem........... Note: This is still not the best algorithm, I'm still trying to learn... /////////////////////////////////////////////////////////////////////////////// Any mistake please be put up once you find............(Kan tie yao hui tie
) (more contents should be put up in several days) To be continued................
表情:
返回