One more thing is that you cannot stop if you reach the goal state as you still do not know if its the optimal path or not (heuristic does not help in that). So, you need to search in a Breadth First manner anyway regardless of reaching goal states in some places to determine the optimal path (as you may later encounter a shorter path). In fact, a heuristic is not even necessary. Its a simple BFS.
On Sat, Jan 22, 2011 at 1:20 PM, Algoose chase <[email protected]> wrote: > To add to what nishaanth mentioned, I think we should also track all the > state transitions so that we can back track and make alternate transitions > if the path that was already taken was later found to be incorrect one which > will not help to reach the given target (with the given set of words). > > > On Fri, Jan 21, 2011 at 10:09 PM, Manmeet Singh <[email protected]>wrote: > >> whts complexity for this movegen() >> >> >> On Fri, Jan 21, 2011 at 9:52 PM, nishaanth <[email protected]> wrote: >> >>> Ok lets define the following functions. >>> >>> movegen()- gives the list of next move given the state. This is basically >>> all the 1 distance words given the current word. >>> >>> heuristic()- this gives the number of non-matching characters of the >>> given word with the goal word. >>> >>> Start from start state and expand. >>> Now always choose the move which gives a lesser heuristic valued state. >>> Stop if you reach the goal. >>> >>> You can refer to Russel Norvig book on AI for detailed explanation. >>> >>> >>> >>> Regards, >>> >>> S.Nishaanth, >>> Computer Science and engineering, >>> IIT Madras. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
