On this site http://algs4.cs.princeton.edu/25applications/ is described A* algothihm this way

The A* algorithm is a problem-solving process where we put the start configuration on the priority queue, then do the following until reaching the goal: remove the highest-priority configuration and add to the queue all configurations that can be reached from that with one move (excluding the one just removed).

But in the programming assignment specification (http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html) is written next

delete from the priority queue the search node with the minimum priority.

I don't understand why on the booksite is written to remove the highest-priority configuration but in the assignment is written to remove the lowest-priority configuration. Please could you explain me it? Maybe they thinks about "priority" or "configuration" in different meaning?


It's just two ways of saying the same thing. High priority means most urgent but is often represented by low numbers – my "number-one priority" is the most urgent thing on my to-do list. Perhaps it would be clearer if people used phrases like "lowest priority value" or even "highest priority (lowest priority value)". It's often inconvenient to reformulate the algorithm to make high priority correspond to big numbers. For example, if I decide that "priority 10" means the most important thing on my to-do list, that kind of limits my lists to ten items, unless I want to number them 10, 9, ..., 1, 0, -1, -2, ..., which seems a bit silly.

Similar confusion comes up in other settings where smaller numbers represent bigger or higher things. For example, in photography, aperture is measured in f-stops but a higher f-number means a smaller aperture.


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.