commit 22282840b74d434b79e87d82e4ea075baa82a51c parent 5355de2921126e2b75e24abd57e17556e22a6ed0 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu, 7 Aug 2025 15:53:08 +0200 Added notes on possible performance improvements for H48 Diffstat:
| M | doc/h48.md | | | 20 | ++++++++++++++++++++ |
1 file changed, 20 insertions(+), 0 deletions(-)
diff --git a/doc/h48.md b/doc/h48.md @@ -432,3 +432,23 @@ Moreover, in this case one can optimize it further by avoiding to repeat the search from a coordinate that has already been visited. (Work in progress - this method will be replaced in the future by a more efficient one) + +## Possible future improvements + +*This section should be considered more of a draft with personal +notes, unlike the rest of the document.* + +There are some areas where this implementation of the H48 optimal solver +can be improved: + +* Interwtining fallback tables to the main table. This is a trick that + nxopt uses to reduce the number of cache misses, but we have not + implemented in H48 yet. +* Faster pruning table generation for **h11** and **h0**. Since these + two coordinates are "real" coordinates, we can use a different technique + to generate their tables faster. This won't affect the solver speed. +* Use + [BPMX](https://webdocs.cs.ualberta.ca/~nathanst/papers/AStar_Inconsistent.pdf) + to improve pruning estimation. This optimization sped up + [vcube](https://github.com/Voltara/vcube/commit/a5b08f51793f81ac34c1d402f2627f6a0495c636). + by about 5%-10%. Suggested by Arhan Chaudhary pointed out.