算法在2行表蚂蚁运动

没有与以下约束的表：

a) it has 2 row only. 
    b) and n col. so basically its 2xN table but N is a power of two. 
    c) its short ends are joint together you can move from last element of the row to the first element of row if first element is not visited.

现在给出2初始位置i1和i2蚂蚁和最终目的地f1和f2 。现在蚂蚁必须达到f1和f2，但是任一个蚂蚁都可以达到任一点。例如，如果i1达到f2并且i2必须达到f1。允许的动作： -

1) Ant can move horizontally and vertically only no diagonal movement. 
2) each cell can be visited at most by one ant and all the cell must be visited in the end.

输出： - 路径由两个蚂蚁追踪，如果所有的细胞都标别的访问-1。该算法也需要复杂性。

来源

2014-09-02 YS.

通过“拜访”，你的意思是说，一旦蚂蚁进入了某个细胞，那么没有其他蚂蚁能够进入该细胞？或者你的意思是说在任何时候只有一只蚂蚁有空间吗？ – RockOnRockOut 2014-09-02 15:50:28

一旦任何蚂蚁访问了一个单元，那么任何其他蚂蚁都无法访问它。 – 2014-09-02 15:51:59

动态编程 - >线性时间（适用于所有具有有限树宽的图族）。 – 2014-09-02 16:00:53

最大流量可用于计算两条不相交的路径，但不可能用通用方式表示访问所有方块的约束条件（可能存在一次性技巧）。 这个动态编程解决方案并不是最薄的，但它背后的想法可以应用于许多类似的问题。

第一步是递归地分解实例，以小块落底。（对这些片断的限制很快就会显现出来。）对于这个问题，根片是整个2×n阵列。根的两个子部分是2乘n/2的数组。这些作品的四个孩子是2×n/4个阵列。我们以2乘1的数组为底。

现在，从一个角度考虑解决方案的外观。

+---+-- ... --+---+ 
A | B |   | C | D 
    +---+-- ... --+---+ 
E | F |   | G | H 
    +---+-- ... --+---+

正方形B, C, F, G在里面。正方形A, E是左边界。正方形D, H是正确的边界。如果一只蚂蚁进入这块，它会从四个边界正方形中的一个（或者它的初始位置，如果它位于该块内部）这样做。同样，如果一只蚂蚁离开了这件作品，它会这样做到四个边界正方形中的一个（或者它的最终位置，如果它位于该作品的内部）。由于每平方米最多可一次参观，有两种蚂蚁的来来往往少数可能的排列：

Ant 1: enters A->B, leaves C->D 
Ant 2: enters E->F, leaves G->H 

Ant 1: enters A->B, leaves G->H 
Ant 2: does not enter 

Ant 1: enters A->B, leaves C->D, enters H->G, leaves F->E 
Ant 2: does not enter 

Ant 1: enters A->B, leaves F->E, enters H->G, leaves C->D 
Ant 2: does not enter 

...

的关键事实是什么蚂蚁做这一块的严格外面有没有关注严格内部发生的事情。对于递归分解中的每一块，我们可以计算与被覆盖的块中的所有方块一致的一组到来和去向。对于2×1阵列，这可以用强力来实现。

+---+ 
A | B | C 
    +---+ 
D | E | F 
    +---+

一般来说，蚂蚁在这件作品中都没有开始或结束。然后将一些可能性是

Ant 1: A->B, B->E, E->F; Ant 2: none 
Ant 1: A->B, B->C, F->E, E->D; Ant 2: none 
Ant 1: A->B, B->C; Ant 2: D->E; E->F 
Ant 1: A->B, B->C, D->E, E->F; Ant 2: none .

现在，假设我们已计算出的集（DP表下文）为两个相邻的件是一个父件的孩子。

    1|2 
    +---+-- ... --+---+---+-- ... --+---+ 
A | B |   | C | D |   | E | F 
    +---+-- ... --+---+---+-- ... --+---+ 
G | H |   | I | J |   | K | L 
    +---+-- ... --+---+---+-- ... --+---+ 
        1|2

件1位于分界线的左侧。件2是在分界线的右侧。再一次，在指定的广场上有少量的交通可能性。父件的DP表由A, B, E, F, G, H, K, L的流量索引。对于每个条目，我们尝试所有可能的流量C, D, I, J，使用儿童DP表来确定组合出发和去程是否可行。

来源

2014-09-02 20:39:56

算法在2行表蚂蚁运动

回答

相关问题