Path finding Algorithms, Stuck on basics_问答_开发者

This is a basic college puzzle question i have which i though i will nail, but when it comes to implementing it i got stuck right on the get go.

Background: a 4 digit path finding algorithm, so given for example a target number 1001 and target number 1040, find path using BFs,DFs...Etc.

Allowed moves: add or subtract 1 from any of the 4 digits in any order, you cannot add to 9, or subtract from 0. Yo开发者_StackOverflow中文版u cannot add or subtract from the same digit twice i.e. to get from 1000 to 3000, you cannot do 2000 ->3000 as you’ll be adding 1 twice to the first digit. So you'll have to do 2000->2100->3100->3000.

Where I am Stuck: I just cannot figure out how i will represent the problem programmatically, never mind the algorithms, but how i will represent 1001 and move towards 1004 .What data structure? How will I identify the neighbours?

Can someone please push me towards the right direction?

If I understand correctly, you're looking for a way to represent your problem. Perhaps you're having difficulties to find it, because the problem uses a 4 digit number. Try to reduce the dimensions, and consider the same problem with 2 digits numbers (see also this other answer). Suppose you want to move from 10 to 30 using the problem's rules. Now that you have two dimensions, you may easily represent your problem on a 10x10 matrix (each digit can have 10 different values):

Path finding Algorithms, Stuck on basics

In the picture above S is your source position (10), and T is your target position (30). Now you can apply the rules of the problem. I don't know what you want to find: how many paths? just a path? the shortest path?

Anyway, a sketch of algorithm for handling moves is:

if you look at T you see that according to the rules of your problem, the only possible neighbours from which you can reach (30) are (20), (31), and (40).
now, let's assume you choose (20), then the only possible neighbour from which you can reach (20) is (21).
now, you're forced to choose (21), and the only possible neighbours from which you can reach (21) are (11) and (31).
finally, if you choose (11), then the only possible neighbours from which you can reach (11) are (10) and (12) ... and (10) is your source S, so you're done.

This is just a sketch for the algorithm (it doesn't say anything on how to choose from the list of possible neighbours), but I hope it gives you an idea.

Finally, when you've solved the problem in the two-dimensional space, you can extend it to a three-dimensional space, and to a four-dimensional space (your original problem), where you have a 10x10x10x10 matrix. Each dimension has always 10 slots/positions.

I hope this helps.

I would start with a directed graph where each node represents your number plus an additional degree of freedom (because of the constraint). E.g. you can think of this as another digit added to your number which represents the "digit changed last". E.g. you start with 1001[0] and this node connects to

1001[0] -> 2001[1]
1001[0] -> 0001[1]
1001[0] -> 1101[2]
1001[0] -> 1011[3]
1001[0] -> 1002[4]
1001[0] -> 0000[4]

or 2001[1] to

2001[1] -> 2101[2]
2001[1] -> 2011[3]
2001[1] -> 2002[4]
2001[1] -> 2000[4]

Please note: the ????[0] nodes are only allowed as starting nodes. And each edge always connects numbers with different last digit.

So for each number xyzw[d] the outgoing edges are given by

xyzw[d] -> (x+1)yzw[1]   if x<9 && d!=1
xyzw[d] -> (x-1)yzw[1]   if x>0 && d!=1
xyzw[d] -> x(y+1)zw[2]   if y<9 && d!=2
xyzw[d] -> x(y-1)zw[2]   if y>0 && d!=2
xyzw[d] -> xy(z+1)w[3]   if z<9 && d!=3
xyzw[d] -> xy(z-1)w[3]   if z>0 && d!=3
xyzw[d] -> xyz(w+1)[4]   if w<9 && d!=4
xyzw[d] -> xyz(w-1)[4]   if w>0 && d!=4

Your targets are now the four nodes 1004[1] .. 1004[4]. If your algorithm requires a single target node you may add an artificial edge ????[?] -> ????[0] for each number and then have 1004[0] as final.

The first thing that came to my mind is that this is just a point with extra dimensions. That is, rather than [x,y] to represent a point on a 2-D grid, you have [w,x,y,z] to represent a point in a 4-D space.

The one thing I'm not sure in your problem is what happens when you add a 1 to a 9. Is there a remainder that get's carried over, or does the number just get rolled over to zero? Or does this represent an edge that can't be crossed?

In any case, I'd start with thinking of this as a type of point with extra dimensionality, and apply your algorithms appropriately.

You can represent each state as an integer array of length 4. Then have a graph structure to connect the states (I would not advice on building the graph fully, as this alone will require O(10^4) memory).

Then use A* algorithm for traversing the graph and reaching the destination node.

Or simply use a BFS traversal routine where you generate the neighbouring states as you process a state. You'll have to keep a track of the states already visited (some sort of a set like data structure).

When visit a node you need to iterate through all children of the node and visit some of them, so you should only implement children generator function getting one parameter - current number like 1001. It's the "core" of the algorithm, then you need to use recoursion to traverse a tree. The following is code that DOES NOT WORK and goes into infinite recoursion, but is a sketch explaining my idea:

from random import random

def shouldVisit(digits):
    #very smart function defining search strategy
    return random() > 0.5

def traverse(source, target, prev):
    if source == target:
        print 'wow!'
        return
    for i in range(len(source)):
        if i == prev:
            continue
        d = source[i]
        if d > 0:
            res = list(source)
            res[i] = d - 1
            if shouldVisit(res):
                traverse(res, target, i)
        if d < 9:
            res = list(source)
            res[i] = d + 1
            if shouldVisit(res):
                traverse(res, target, i)

def traverse0(source, target):
    def tolist(num):
        digits = []
        while num:
            digits.append(num % 10)
            num /= 10
        return digits
    traverse(tolist(source), tolist(target), -1)

traverse0(1001, 1040)

very smart stub function shouldVisit may check for example if given node has been already visited