一尘不染

网格中非相交路径的近似算法

algorithm

我最近遇到了这个问题,并认为我可以在这里分享,因为我无法得到它。

我们给定了一个5 * 5的网格(编号为1-25)和一组5对点,它们是网格上路径的起点和终点。

现在我们需要为5对点找到5条对应的路径,这样就不会有两条路径重叠。另请注意,仅允许垂直和水平移动。 同样,合并的5条路径应覆盖整个网格。

例如,我们给了这对点:

P={1,22},{4,17},{5,18},{9,13},{20,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

到目前为止,我想到的是:也许我可以为所有成对的点计算从源到目的地的所有路径,然后检查路径中是否没有公共点。但是,这似乎具有较高的时间复杂度。

谁能提出更好的算法?如果有人能通过伪代码解释我会很高兴。


阅读 275

收藏
2020-07-28

共1个答案

一尘不染

这是一个用Python编写的程序,它可以走所有可能的路径。它使用递归和回溯来查找路径,并标记一个网格以查看已使用的位置。

一种关键的优化方法是,它在网格上标记起点和终点(25个点中的10个)。

另一个优化是在跨网格开始“行走”之前,它会生成每个点的所有移动。例如,从点1移动到点2和6;然后从点1移动到点2。从第7点移到第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)
2020-07-28