How can this algorithm be improved by removing unnecessary steps?
I have a project that consists of a group of numbers, increasing or decreasing one of its values. Imagine the following 3x2 grid:
1 1 1
2 2 2
We can only increase or decrease the value of any number by 2, which will increase / decrease the adjacent (top, bottom, left and right) digits by 1. For example, if we increase the value of the first number, the result is:
3 2 1
3 2 2
The goal is to find a way to make all numbers equal in value in the smallest possible steps. To analyze all possible combinations of "moves", an algorithm was created that goes through all possible combinations from the lowest value (ie 0) to the highest. In this case, the highest value is seven (7) . The algorithm stops the moment it finds a solution.
However, this results in the program picking out unnecessary analytical steps that it has already gone through, for example increasing its value and then decreasing it again, since both increasing and decreasing are steps that can be repeated as often as necessary. The pseudo code below takes 18 853 802 steps at a maximum depth of 7 values per cell to find the solution. Moreover, there are cells that can be empty and thus create more useless steps since nothing will be read from them. For example:
1 X 1
2 3 4
How can this be done so that the algorithm skips steps that would lead to a state that has already been verified? The requirements are that it can also return the steps it used to find the answer, with any grid size.
The pseudocode of the algorithm is as follows:
function solve : x, y, direction, depth, currentSolution
//CurrentSolution is a copy
currentSolution.addTurn x, y, direction
//If move is not possible, return, all following turns are not necessary
if doTurn x, y, direction == false:
return
depth++;
if maxDepth > MAX_DEPTH:
return
if isSolved == true:
solution.add(currentSolution)
foreach cell in gridCells:
//If the previous turn was the same, just reversed, don't do anything
if x != newX && y != newY && direction != Direction.DECREASE:
//Do nothing
else:
solve newX, newY, Direction.INCREASE, depth
if x != newX && y != newY && direction != Direction.INCREASE:
//Do nothing
else:
solve newX, newY, Direction.DECREASE, depth
source to share
One optimization is to treat this issue as the shortest path on the graph.
Chart G=(V,E)
- a state graph, where the top is possible state: V = {all possible matrices}
and rib - a possible movement from one state to another in a single operation: E= { (u,v) | can change matrix u to v in one op}
.
You can now use the shortest path algorithm on an unweighted chart. BFS is one possible solution, which is very similar to your approach, but thanks to visited
BFS support being supported, t repeat the same state twice.
Another approach is to use A * Search Algorithm with some heuristic function.
Pay attention . The graph is symbolic, you do not need to calculate it before starting. You can simply have a function next(v)
that returns a set of "next" vertices that can be reached v
in one step, and then use that function next()
to simulate edges and create only the portion of your graph that you want on the fly.
source to share
Instead of thinking of it as a collection of steps, think of it as a linear algebra problem. Operations commute, so it only matters how much you increment / decrement each node.
You have a starting vector b. You want to create a vector in space where all values are equal. You can add or subtract vectors v1, v2, v3, ..., vk. Make a matrix M whose column vectors are v1, v2, ..., vk. You want to find a vector of coefficients a = {a1, a2, ..., ak} so that Ma + b = constant vector. This is something you can solve with linear algebra, but there can be 0 solutions or infinitely many.
Here's an example with 0 solutions:
1 4
2 6
Whatever you do, the evenness of the sum will remain odd, so you cannot make all values equal. But this is worse than that. Even if you allow fractional moves, the alternating sum of numbers (e.g. 1-4 + 6-2) will remain the same, 1, so you cannot get to positions with the same numbers and alternating the sum of 0p>
Since the following move pattern creates a 0 net change,
+ -
- +
then everything that has a solution has an infinite number. This pattern matches a vector in zero space.
If the matrix M is invertible over actions, then you get one real solution for each final vector. Perhaps not all of them can be achieved with an integer number of steps. In general, when there is at least one solution, there is a solution space, and you can find this space by calculating the zero space M and the solutions M a = all 1s vector. You want to find an integer vector of minimal norm L1 in this subspace. There may be better solutions, but you can solve this with linear programming. Even if you take an inefficient, exhaustive approach to looking for possibilities, you can do it in a space of dimension greater than 1 than the null space of M, not n, and I think you will see that there is little empty space for M.
source to share