#Opened-Nodes benchmark

[felix91gr]

This is an idea that I think is worth pursuing. The explanation (copied from my question on the forums):

This technique consists on counting how many nodes a particular algorithm opens. The less nodes an algorithms opens, the faster it tends to be in general.

For example, if you count the nodes opened in A v/s Dijkstra (assuming your heuristic is admissible in A) you’ll find that A always opens less nodes. Similarly, when comparing different heuristics for A, you’ll find that between two admissible heuristics h₁ and h₂ such that h₁ ≤ h₂, the opened_node_count for A* will be always less when using h₂ than when using h₁. And these differences tend to show in the time of execution as well.

Not always however, because of cache and usage of heap v/s the stack in different algorithms, but in general it’s a good guiding measurement.

I'd like to have some sort of benchmark ran with the command cargo run --example node_count or so, which runs some example problems of differing structure against the available algorithms, and then displays the results.

I was also thinking that it could be useful for users of this crate to be able to pick an algorithm and run this "counting benchmark" against it, to see how well one algorithm behaves on their particular problem. But that might be out of scope for this idea atm.

[samueltardieu]

I'm in favour of including examples, as long as they are useful to demonstrate a point. Showing how to count calls to neighbours for example would be useful indeed.

[felix91gr]

I wasn't thinking originally of making it an example... although as you say it can be very useful to show how to do this (and it took me a while to figure out how, so I could've used it! ^^). I was thinking more along the lines of "Here's a common benchmark on different kinds of problems. Choose an algorithm that fares best on your kind of problem!".

That's why I asked that in the forums, as well. In an ideal world, the bench API would have ways to output custom metrics, like the opened node count, for kinds of crates that would benefit from it like this one. After all, the opened node count can be used to track regressions just like the current benchmarks do.

(While we're at it: can bench measure memory usage? That would be good for showing how A isn't always the best option (vs IDA) and to show the strengths of IDDFS against BFS)

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.