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 y
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).
O
whts complexity for this movegen()
On Fri, Jan 21, 2011 at 9:52 PM, nishaanth 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 o
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
@nishaanth can u give the outline?//
On 1/21/11, nishaanth wrote:
> Its a state space search. Solve it by using any of the known search
> algorithms.
>
> BFS, Best first search, DFS, A*
>
> On Fri, Jan 21, 2011 at 2:00 PM, snehal jain wrote:
>
>> You have a dictionary of N words each of 3 chars
Its a state space search. Solve it by using any of the known search
algorithms.
BFS, Best first search, DFS, A*
On Fri, Jan 21, 2011 at 2:00 PM, snehal jain wrote:
> You have a dictionary of N words each of 3 chars. Given 2 words you
> have to find the optimum path between the 2 words. The opti
You have a dictionary of N words each of 3 chars. Given 2 words you
have to find the optimum path between the 2 words. The optimum path
contains the words in the dictionary each word at a distance of 1 from
the previous word.
for eg source = cat , target = sun
path is
cat -> bat -> but -> bun -> su
