近似​​算法在网格不相交的路径 [英] Approximation Algorithm for non-intersecting paths in a grid

问题描述

我最近碰到了这个问题，我想我可以在这里分享一下，因为我是不是能够得到它。

I recently came across this question and thought I could share it here, since I wasn't able to get it.

我们给出一个5 * 5格从1-25编号，和一组5对点，即是对电网的路径的起点和终点。

We are given a 5*5 grid numbered from 1-25, and a set of 5 pairs of points,that are start and end points of a path on the grid.

现在我们需要找到的5对点，使得没有两个路径应重叠5相应的路径。另外请注意，只有垂直和水平移动是允许的。 同时合并5路径应覆盖整个电网。

Now we need to find 5 corresponding paths for the 5 pairs of points, such that no two paths should overlap. Also note that only vertical and horizontal moves are allowed. Also the combined 5 path should cover the entire grid.

例如，我们给该货币对点为：

For example we are given the pair of points as:

P={1,22},{4,17},{5,18},{9,13},{20,23}

然后，相应的路径将是

Then the corresponding paths will be

1. 1-6-11-16-21-22
2. 4-3-2-7-12-17
3. 5-10-15-14-19-18
4. 13年9月8日
5. 20-25-24-23

1. 1-6-11-16-21-22
2. 4-3-2-7-12-17
3. 5-10-15-14-19-18
4. 9-8-13
5. 20-25-24-23

我所想象的那么远： 也许我可以计算出从源代码的所有路径到目的地的所有的点对，然后检查是否有在路径没有公共点。然而，这好像是更高时间复杂度。

What I have thought of so far: Maybe i can compute all paths from source to destination for all pairs of points and then check if there's no common point in the paths. However this seems to be of higher time complexity.

任何人都可以提出一个更好的算法？我会很高兴，如果人们可以通过伪code.Thanks

Can anyone propose a better algorithm? I would be glad if one could explain through a pseudo code.Thanks

推荐答案

下面是用Python编写一个程序，将遍历所有可能的路径。它采用递归和回溯，找到路径，它标志着一个网格，看看已经被使用它的位置。

Here's a program written in Python that walks all potential paths. It uses recursion and backtracking to find the paths, and it marks a grid to see which locations are already being used.

一个关键优化是，它标志着对电网的开始和结束点（10的25分的）。

One key optimization is that it marks the start and end points on the grid (10 of the 25 points).

另一种优化是，它产生的每一个点的所有移动开始走在网格之前。例如，从点1的动作是要分2及6;从第7点，这些举措是为点2，6，8安培; 12。

Another optimization is that it generates all moves from each point before starting the "walk" across the grid. For example, from point 1 the moves are to points 2 & 6; from point 7, the moves are to points 2, 6, 8 & 12.

points = [(1,22), (4,17), (5,18), (9,13), (20,23)]
paths = []

# find all moves from each position 0-25
moves = [None]    # set position 0 with None
for i in range(1,26):
    m = []
    if i % 5 != 0:    # move right
        m.append(i+1)
    if i % 5 != 1:    # move left
        m.append(i-1)
    if i > 5:         # move up
        m.append(i-5)
    if i < 21:        # move down
        m.append(i+5)
    moves.append(m)

# Recursive function to walk path 'p' from 'start' to 'end'
def walk(p, start, end):
    for m in moves[start]:    # try all moves from this point
        paths[p].append(m)    # keep track of our path
        if m == end:          # reached the end point for this path?
            if p+1 == len(points):   # no more paths?
                if None not in grid[1:]:    # full coverage?
                    print
                    for i,path in enumerate(paths):
                        print "%d." % (i+1), '-'.join(map(str, path))
            else:
                _start, _end = points[p+1]  # now try to walk the next path
                walk(p+1, _start, _end)

        elif grid[m] is None:    # can we walk onto the next grid spot?
            grid[m] = p          # mark this spot as taken
            walk(p, m, end)
            grid[m] = None       # unmark this spot
        paths[p].pop()       # backtrack on this path

grid = [None for i in range(26)]   # initialize the grid as empty points
for p in range(len(points)):
    start, end = points[p]
    paths.append([start])          # initialize path with its starting point
    grid[start] = grid[end] = p    # optimization: pre-set the known points

start, end = points[0]
walk(0, start, end)

这篇关于近似​​算法在网格不相交的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！