UDTW&Textiling 一些记录

一、        Algorithm

l  Step 1:定义Synchronous Point

我用的是diagonal bands。对每个SP，置M[SP] =1。

l  Step 2:对每一个SP或possible path运用前向搜索算法

前向搜索算法：判断三个后继点是否满足约束条件。

若满足条件，则给D_g，S，M，矩阵赋值，并将此点看做possible path；

若所有后继点都不满足条件，则返回0，说明此SP或possible path不能再向前继续搜索，故terminate，并保存这条路径。

从而得到一些路径，再从中选出共享同一SP的最长路径。

l  Step 3:对Step2最后得到的每一条路径，运用后向搜索算法。

后向搜索算法：对于Step2中得到的每条路径，找出其SP，并入队。再对SP的三个前续点进行判断，满足条件的就入队。若所有前续点都不满足条件，说明后向搜索完毕，保存最长的路径即可。

l  Step 4:将前后向搜索得到的路径拼接到一起，若大于L_min则保存为最后结果，否则丢弃。

二、        Two Bugs

昨晚发现了两个关键的Bug

1.  在后向搜索算法中，只要某点被搜索到，且满足要求，就入queue。而某点的前续点可能不止一个，被搜索到的点可能已经被其它点搜索过，已经在queue里面。此情况下，不能使其入队。用Exist_inQueue解决

2.  在后向搜索结束后，要保存路径，以前的判断条件是if(M[P.x][P.y] == flagpath)。而在后向搜索时，M矩阵是前向搜索后遗留下来的，有很多非零值。若保存路径时，KeepPath函数中返回的A，B，C三点中可能有几个点并非是这次后向搜索过的点，而只是因为其在前向搜索之后，对应的M[P.x][P.y]刚好等于flagpath。从而使得保存了一个“非本次后向搜索过”的点。

本来是用了一个Label数组（与M一样大）来标记每一次后向搜索过的点，但是效率太低。就改用了Exist_inQueue,因为queue实际上是一个数组，从1到tail，就是所有搜索过的点，只要在if(M[P.x][P.y] == flagpath)加上Exist_inQueue判断就行。

三、        Result

1.  结果分为“分part”和“未分part”。“未分part”中“未分part_BUG用队列_速度快_L_min40_第二次.jpg”是最好的。

2.  “分part”大概要370秒左右，“未分part”只需90秒

四、        Problem

用queue代替Label解决BUG2后，“未分part”时速度是很快的，达到了预期的效果，只要90秒左右。但是“分part”后，速度没有本质区别。

五、        Postscript

1.  L_min ,tao_d,ForwardThr，Thr都是可以调的。

我一般设为L_min = 40 ,tao_d = 40,ForwardThr = 10，Thr = 0.6

2.  Determine Synchronous Point 时，我用的 Diagonal band ，用tao_d表示宽度，而UDTW那篇文章中还提到了Horizontal band，用tao_r控制。我都用的Diagonal band。