修改文章
标题:
内容:
反复尝试了很久,但是就是做不出源程序来,然后我才发现,原来我对算法本身的理解就有问题。 我们最后讨论的那个算法实际上是不完整的。大家可以看到,程序的bound,也就是搜索的层数是不变的,那么也就决定了,如果渡河的步奏不可以在bound步内完成,那么程序就会认为这个问题误解,从而返回错误的答案。而如果程序在bound以内执行完的话,就跟backtrack搜索没有什么区别,也无从找到最短路经 for (int BOUND=1;;BOUND++){ 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 } 这样,程序多了一个大循环,使得程序搜索的层数在不断的变化,每一次都会向下多搜索1层,这样的话一旦找到一个解,那么我们可以确定这个解是最小解,因为比它小的所有可能都不是正确解。 当然,我现在对于这种搜索问题还有很多困扰,我仍然感觉对这个算法的精神没有完全掌握。老师说话太快了,根本没有给我反应的时间。所有的感觉都是在自学与完成作业的过程中找到的,包括我上面发现的算法错误,都是昨天在写作业的时候发现的。如果有人了解这个算法请帮我解释一边,我也学习学习 声明:由于在学《人工智能》,其中有很多算法都是和这种求解问题相关的,比如我们的作业就有华容道问题,还有命题逻辑的推理(我是指用程序解决)。还有魔方问题。都是求解的。我之所以选择这个问题发帖子是因为我想通过这样的方式可以 1。我可以复习老师所讲过的内容,并通过实际的编程让我有更多解决这种问题的经验(这样写作业可以快一点) 2。我也想把这些算法介绍给大家,因为我发现在国内我们很少系统地接受这种算法的介绍(至少我是如此),大部分的算法实在将数据结构的时候老师顺带讲的,而很多时候我们没有领会老师所讲的东西的实质。 很抱歉没有能够把源程序贴出来,但是我已经很努力的在做这件事了。希望下一次能够吧 对不起大家
表情:
返回