我最近遇到了这个问题,并认为我可以在这里分享,因为我无法得到它。
我们给定了一个5 * 5的网格(编号为1-25)和一组5对点,它们是网格上路径的起点和终点。
现在我们需要为5对点找到5条对应的路径,这样就不会有两条路径重叠。另请注意,仅允许垂直和水平移动。 同样,合并的5条路径应覆盖整个网格。
例如,我们给了这对点:
P={1,22},{4,17},{5,18},{9,13},{20,23}
然后相应的路径将是
1-6-11-16-21-22
4-3-2-7-12-17
5-10-15-14-19-18
9-8-13
20-25-24-23
到目前为止,我想到的是:也许我可以为所有成对的点计算从源到目的地的所有路径,然后检查路径中是否没有公共点。但是,这似乎具有较高的时间复杂度。
谁能提出更好的算法?如果有人能通过伪代码解释我会很高兴。
这是一个用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)