From 22282840b74d434b79e87d82e4ea075baa82a51c Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 7 Aug 2025 15:53:08 +0200 Subject: Added notes on possible performance improvements for H48 --- doc/h48.md | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'doc') diff --git a/doc/h48.md b/doc/h48.md index 30b5171..3781863 100644 --- 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. -- cgit v1.3