I've been trying to find a good way of solving the following problem, but I'm not sure how to even frame it. I think there might be relatively well-known solutions I'm not familiar with, since I don't have much knowledge of algorithms. How could I approach this?
There's a known begin-state A and known end-state B. There is a known sequence of (a large amount of) points that lead from A to B. I would like to find a minimum/small number of points that will describe the path from A to B. I can test for any sequence of points whether it reaches B using that, but if it doesn't I don't have an estimation of how close it is to getting to B. I'm basically trying to find the points that are essential for getting to B, but I won't know whether they are sufficient until the path is complete.
What I found so far:
The problem appears a bit similar to polyline simplification, and one option would be the Ramer Douglas Peucker algorithm. I don't think it will work well for my problem though, because I don't necessarily want to follow the non-essential points on the path(which may be outliers or unnecessary circumventions).
The solution I came up with myself sounds a bit like greedy & binary search:
- Pick middle point C between A and B and discard all points between A and C.
- Check whether this path reaches B.
- If B cannot be reached, there is an essential point between A and C we missed, so pick middle point D between A and C and test path with points between A and D discarded.
If B can be reached, we might be able to discard point C and some subsequent points, so pick D between C and B and discard points until D.
- Do this until identified a point D furthest from A that still leads to B if all the points between A and D are discarded.
- Start this search over, now starting from D instead of A until all essential points have been identified
I might be able to give a "similarity" estimation for end-state B1 that is reached from some point C in comparison to the targeted end-state B. Would that provide a wider variety of applicable algorithms?