1
$\begingroup$

I read somewhere that DFS is a special case of Best first search algorithm if f(n)=-depth(n). please justify this i am not getting it.:/

$\endgroup$
1
$\begingroup$

Consider a node $u$ such that $depth(u)=l$.

In Best first Search when you evaluate $u$ with the evaluation function you defined, you have $f(u)=−l$.

queue

╔═══╤═══╤═════╤═══╗
║ r │ a │ ... │ u ║
╚═══╧═══╧═════╧═══╝

When you expand $u$ and you evaluate the first child of $u$ (suppose it is Node $v$) you have $f(v)=−(l+1)<−l=f(u)$ so now you expand $v$ (that means that you put $v$ in the front of the queue) and you continue.

queue

╔═══╤═══╤═════╤═══╤═══╗
║ r │ a │ ... │ u │ v ║
╚═══╧═══╧═════╧═══╧═══╝

This corresponds to what you do when you use Depth First Search.

$\endgroup$
  • $\begingroup$ is minus sign here showing the very first position of the queue? i.e the node with the least cost? $\endgroup$ – mehru Apr 2 '17 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.