CODEWITHSUNDEEP
algorithmforeachpseudocode
user3818448
user3818448

Reputation: 35

How to Improve this Algorithm by removing unnecessary steps?

I a have project which consists on a group of numbers by increasing or decreasing one of their 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 adjacent (top, down, left and right) numbers by 1. For example, if we increase the value of the first number, the result would be:

3 2 1
3 2 2

The goal of this is to find the way to make all numbers equal in value in the fewest steps. To analyze all possible combinations of "moves", an algorithm has been created which goes through all the possible combinations from the lowest value (i.e. 0) to the highest. In this case, seven (7) is the highest value. The algorithm stops the moment it finds the solution.

However, this results in the program wastefuly analizing steps that it has already been through, for example, increasing its value and then decreasing it again, since both increasing and decreasing are steps which can be repeated as often as necessary. The pseudocode below takes 18,853,802 steps on a max depth of 7 values per cell to find the solution. Moreover, there are cells which can be empty, and thus generate more useless steps, since there would be nothing to read from them. For example:

1 X 1
2 3 4

How could it be done so that the algorithm skips the steps which would cause a state that has already been tried? The requirements are that it can also return the steps it used to find the answer, with any grid size.

The algorithm's pseudocode is the following:

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

Upvotes: 3

Views: 119

Answers (2)

Douglas Zare
Douglas Zare

Reputation: 3316

Instead of thinking about this as a set of steps to take, think of this as a linear algebra problem. The operations commute, so the only thing that matters is how much you increase/decrease each node.

You have an initial vector b. You want to produce a vector in the space where all of the 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 M.a+b = constant vector. This is something you can solve using linear algebra, but there can be 0 solutions or infinitely many.

Here is an example where there are 0 solutions:

1  4  
2  6

Whatever you do, the parity of the sum will stay odd, so you can't make all of the values equal. But it's worse than that. Even if you allow fractional moves, the alternating sum of the numbers (e.g. 1-4+6-2) will stay the same, 1, so you can't get to a position with equal numbers and alternating sum 0.

Since the following pattern of moves produces a 0 net change,

+ -
- +

then anything that does have a solution has infinitely many. This pattern corresponds to a vector in the null space.

If the matrix M is invertible over the reals, then you will get one real solution for each final vector. Perhaps not all of these can be reached with an integer number of steps. In general, when there is at least one solution, there is a space of solutions, and you can find this space by computing the null space of M and the solutions to M a = all 1s vector. You want to find an integer vector of minimal L1 norm in this subspace. Perhaps there are better solutions, but you can solve this using linear programming. Even if you take an inefficient, exhaustive approach to searching the possibilities, you can do this in a space of dimension 1 more than the null space of M, rather than n, and I think that you will find that the null space of M is small.

Upvotes: 1

amit
amit

Reputation: 178481

One optimization is to look at this problem as a shortest path problem in a graph.

The graph G=(V,E) is a states graph, where a vertex is a possible state: V = {all possible matrices}, and an edge is a possible move from one state to the other using a single operation: E= { (u,v) | can change matrix u to v in one op}.

Now, you can use a shortest path algorithm on an unweighted graph. BFS is one possible solution, which is very similar to your approach - but thanks to the visited set BFS maintains, it is guaranteed you don't revisit the same state twice.

Another approach is using A* Search Algorithm, with some heuristic function.

Please Note: The graph is symbolic, you don't actually need to calculate it before you start. You can just have a next(v) function, that returns a set of "next" vertices - that can be reached from v in a single step, and then use this next() function to mimic edges, and create only the part of your graph you need, on the fly.

Upvotes: 1

Related Questions