5 ms·
Isn't this overkill to verify that you don't have any invalid states? Consider the state machine as a directed graph, reverse each edge and run DFS from the end
by steventhedev 7y ago
Isn't this overkill to verify that you don't have any invalid states? Consider the state machine as a directed graph, reverse each edge and run DFS from the end state. if you have any vertices in the graph you didn't visit, they're dead ends. That should be more efficient than the O(n^3) way of finding eigenvectors.
- toxik 7y agoMore precisely, construct a graph with vertices (u, v) where u is a prior state and v a possible successor state, then there must not be a node of out-degree zero unless it is an end state. As far as complexity goes, this should be linear in number of vertices. In fact, you don't even really have to construct the graph, just count out degree.
- akrasuski1 7y agoThat is not enough, since you may still get stuck in a loop.
- toxik 7y agoFair point, but that is inevitable unless it's a game where the user cannot go back, very few games would fit that bill then.
- deleted 7y ago[deleted]