For the column regarding if the plan is optimal, does that mean that it is asking if the set of actions is optimal for those words or for the general algorithm?

+3 votes

So the "plan" is the sequence of actions that the algorithm finds to solve a specific problem.

In this case, the specific problem is how to transform "SNAKE" to "BIRDS", and the "plan" is a sequence of actions that complete that transformation.

Thus, when I ask "is plan optimal?" in that table, I am just asking whether the specific sequence of actions that the algorithm found is as low-cost as possible -- I am NOT asking whether the overall algorithm will *always* find an optimal plan for every possible problem.

(Even DFS can sometimes find an optimal plan for some simple problems... even though DFS is not optimal in general.)