0

I am wondering if the one I came up with is non-trivial.

According to the project's website :

The trivial heuristics are the ones that return zero everywhere (UCS) and the heuristic which computes the true completion cost

The one I implemented calculates the cost of the Minimum Spanning Tree of the remaining food pellets using Kruskal's algorithm and the mazeDistance function of searchAgents.py and adds to it the mazeDistance of Pacman to it's closest pellet.

Is this a case of calculating the true completion cost? Furthermore what is the difference of an exact heuristic vs a trivial heuristic?

Here are 2 examples I thought of where the true completion cost might be different from the heuristic value produced.

MST cost of F1 - F2 - F3 - F4 is equal to 3 and the heuristic value I produce is equal to 4 as F1 is the closest neighbor to Pacman and in this case the true completion cost is 4 as well

However in the following case :

enter image description here

the MST cost of F1 - F2 - F3 - F4 is equal to 3 and the heuristic value I produce is equal to 4 as F2 is the closest neighbor to Pacman now and the true completion cost is equal to 5 as Pacman should go left then eat F1 -> F2 -> F3 -> F4 and the heuristic value is less than the true completion cost.

RookieCookie
  • 37
  • 4
  • `Is this a case of calculating the true completion cost?` No. Suppose that your minimum spanning tree contains a node which is connected to three other nodes. You can't turn that tree into a path without re-tracing some of your steps. Your solution may under-estimate the true cost of completion by a factor of 2. Which is fine! It's just a heuristic, and it's okay to underestimate (but not overestimate) the remaining cost. – Nick ODell Oct 26 '22 at 03:25
  • @NickODell `You can't turn that tree into a path without re-tracing some of your steps.` That's true but given that I know the minimum cost of going from Node1 to Node4 (which is the cost of the MST) but I also know the cost of going to the closest node from where Pacman currently is, isn't that the true completion cost? Unless you have the following example in mind where Node1 to Node4 are in a straight line : N1 - N2 - N3 - N4 and say Pacman is right above N2 which should be the closest Node to Pacman and then I underestimate the actual completion cost – RookieCookie Oct 26 '22 at 10:15
  • Sorry, I can't quite visualize your example. Perhaps you could draw a diagram and add it to your question? – Nick ODell Oct 26 '22 at 15:37
  • I would tell you to make the spanning tree from five elements: P, F1, F2, F3, and F4. If you start with a spanning tree from F1, F2, F3, and F4, and then add Pacman using a greedy nearest neighbor algorithm, that is potentially not an MST. See the counterexample from [this question](https://stackoverflow.com/questions/44092190/how-to-add-a-new-node-to-a-minimum-spanning-tree-created-via-kruskal-algorithm). (On the other hand, your problem obeys the triangle inequality, so I don't know if this is a problem in practice.) – Nick ODell Oct 26 '22 at 18:51

0 Answers0