ADS 期中补天笔记

AVL Trees, Splay Trees, and Amortized Analysis

AVL Tree

定义

1. 空树是平衡的（空树的高度被定义为 -1）
2. 如果树 T 满足以下条件，那么 T 是平衡的

$$BF(T)=|T_L-T_R|\le1$$

旋转

AVL 树是自平衡的，因此需要旋转操作保持其平衡的性质

如果插入的节点在右子树的右子树，那么要做 RR 旋转

节点数 n 与高度 h 的关系

令 $n_h$ 为高度为 h 的树所拥有的最小节点数，则有

$$n_h=n_{h-1}+n_{h-2}+1$$

$$\Rightarrow n_h=F_{h+2}-1\approx\displaystyle\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{h+2}-1$$

$$\Rightarrow h=O(\ln n)$$

Splay Tree

假如 M 次连续的操作需要的时间为 $O(M\log N)$，需要保证每次操作一定是 $O(\log N)$ 的吗？显然不需要。可以通过移动每次操作涉及的节点使得平均的消耗是 $O(\log N)$ 的

定义

Splay Tree 是特殊的 AVL Tree，每次查询到节点后，通过旋转的操作使得该节点被移到根

旋转

递归的进行如下操作，直到 X 为根

对于节点 X，记父节点为 P，祖父节点为 G

1. P 是 root：将 X 旋转到 P
2. P 不是 root：
   1. zig-zag（即 G-P-X 为折线）：通过两次旋转，使得 X 旋转到根，P 和 G 作为 X 的左右孩子
   2. zig-zig（即 G-P-X 为直线）：通过一次旋转，使得 X 旋转到根，X-P-G

该操作不仅将访问的节点移动到根，而且还将路径上大多数节点的深度大致减半

删除

1. 寻找 X（同时移到了根）
2. 删除 X（此时获得了左右子树）
3. 寻找左子树的最大值（同时移到了左子树的根，左子树没有了右孩子）
4. 将右子树接到左子树右孩子处

Amortized Analysis

均摊消耗介于最坏消耗和平均消耗之间，而且与概率无关

聚合分析 Aggregate analysis

考虑 n 个操作，如果每个操作的最坏情况消耗为 $T(n)$，则均摊消耗为 $T(n)/n$

带有 multipop 的 stack

对一个初始为空的 stack 进行 n 次 push，pop 和 multipop，虽然 multipop 操作的消耗 $T=\min\{sizeof(S), k\}=O(n)$，但是注意到 multipop 或 pop 的操作总次数不能大于 push 的次数，因此总共的消耗依然是 $O(n)$ 的

$$T_{amortized}=O(n)/n=O(1)$$

计数法 Counting Method

设某个操作的均摊消耗是 $\hat c_i$，第 i 次操作的实际消耗是 $c_i$，定义 credit 为均摊消耗与实际消耗的差，并储蓄下来，用于补偿支付后续超过均摊消耗的实际消耗

$$\sum\hat c_i\ge\sum c_i$$

$$T_{amortized}=\sum\hat c_i/n$$

带有 multipop 的 stack

依然是这个例子，我们有：

	Push	Pop	Multipop
$c_i$	1	1	$\min\{sizeof(S), k\}$
$\hat c_i$	2	0	0
credit	1	-1	-1 for each +1

有 credit 不为负，则

$$T_{amortized}=\sum\hat c_i/n=O(n)/n=O(1)$$

潜能法 Potential Method

$$credit_i=\hat c_i-c_i=\Phi(D_i)-\Phi(D_{i-1})$$

$$\Rightarrow\sum\hat c_i=\sum c_i+\Phi(D_n)-\Phi(D_{0})$$

$$\Rightarrow \sum\hat c_i\ge\sum c_i\lrArr\Phi(D_n)-\Phi(D_{0})\ge0$$

带有 multipop 的 stack

还是这个例子，定义 $D_i$ 为 i 次操作后 stack 的状态；$\Phi(D_i)$ 为 stack 中元素的个数。易得

$$\Phi(D_i)\ge\Phi(D_0)=0,i\ge0$$

• Push

$$\Phi(D_i)-\Phi(D_{i-1})=1$$

$$\Rightarrow\hat c_i=1+1=2$$

• Pop

$$\Phi(D_i)-\Phi(D_{i-1})=-1$$

$$\Rightarrow\hat c_i=1-1=0$$

• Multiop

$$\Phi(D_i)-\Phi(D_{i-1})=-k_i$$

$$\Rightarrow\hat c_i=k_i-k_i=0$$

伸展树

Red-Black Trees and B+ Trees

Red-Black Trees

定义

黑高（从 X 到 leaf 的黑节点数量，不包括 X）：$bh(X)$

RBT 的扩展：对每个叶子结点补充 2 个 NIL

Lemma

一个有 N 个内部节点的 RBT，高度不超过 $2\ln(N+1)$

操作

插入

先把插入节点 V 设置成红色，然后从 V 的父节点 U 开始调整（如果 U 是黑色，无需调整）

1. U 的兄弟节点 S 是红色，此时 U-V 冲突，那就把 U 和 S 都改成黑色，把 P 改成红色
   1. P 的父节点 G 是黑色：调整结束
   2. P 是根，染黑 P
   3. G 是红色，继续调整 G
2. S 是黑色（则 P 一定是红色）：通过旋转使得 U 变为 V，P 的父节点，染黑 U，染红 V 和 P

删除

B+ Tree

定义

M 阶 B+ Tree 有如下特性：

1. 所有的叶子有同样的高度
2. 所有的非叶节点有 M / 2 至 M 个孩子（以及孩子数 - 1 个数的索引数字）
3. 所有的真实数据被储存在叶子中，非叶节点储存的数据为这个索引所对应孩子子树中的最小值

例如 4 阶 B+ Tree 中有非叶节点 [25, 31, 41]，则有 4 个子树，每个子树的最小值分别是 X, 25, 31, 41

操作

插入

插入元素后，若叶子超过了容量 M，则发生分裂；分裂是向上传递的，如果非叶节点的元素超过了 M - 1，也会发生分裂

// T(M, N) = O((M / log(M)) * log(N))
Btree  Insert ( ElementType X,  Btree T ) 
{ 
	Search from root to leaf for X and find the proper leaf node;
	Insert X;
	while ( this node has M+1 keys ) {  // T = O(M)
    		split it into 2 nodes with (M+1)/2 and (M+1)/2 keys, respectively;
    		if (this node is the root)
        		create a new root with two children;
    		check its parent;
	}
} 

M 最优取值为 3 或 4

删除

删除元素后，若叶子的实际元素数量少于了 M / 2，则发生合并，合并也是向上传递的

复杂度

$Depth(M, N) = O(\log_{M/2+1}N)$

$T_{Find}(M,N)=O(\log N)$

Inverted File Index

从搜索引擎开始，当我们在搜索引擎中输入一个字符串 S 的时候，到底发生了什么？

引入

Sol. 1

一篇一篇找，太烂了

Sol. 2 Term-Document Incidence Matrix

以页面序号为 col，单词为 row，构建矩阵

矩阵过于稀疏，空间浪费了！

Sol. 3 Compact Version - Inverted File Index

倒排索引的思路，某个单词 T 对应一个列表 posting list，储存包含 T 的所有页面的指针

索引生成

while ( read a document D ) {
    while ( read a term T in D ) {
        if ( Find( Dictionary, T ) == false )
            Insert( Dictionary, T );
        Get T’s posting list;
        Insert a node to T’s posting list;
    }
}
Write the inverted index to disk;

优化

Word Stemming

不同时态和分词的同一个词可以合并到一个列表

Stop Words

对理解文章结构帮助不大的 a, the, it 等，选择无视

Relevance

如何衡量一个搜索引擎的好坏

	Relevant	Irrelevant
Retrieved	RR	IR
Not Retrieved	RN	IN

如何理解 Relevant 和 Retrieved？前者意味着找到的东西符合需求，但是不一定都找得到（相关的）；后者意味着找得到大部分需要的东西，同时可能找到一些没用的（检索到的）

于是引申出 Precision 和 Recall

$$P=RR/(RR+IR)$$

$$R=RR/(RR+RN)$$

精确度：若干次问询中，真正需要对于检索到的占比。意味着检索到的相关性高，但是可能没找到很多有用的
召回度：若干次问询中，真正需要对于相关的占比。意味着找到了几乎所有的相关东西，但是参杂了很多没用的信息

Leftist Heaps and Skew Heaps

Leftist Heaps

定义

1. 对于节点 X，定义 npl(X) 为从 X 到一个叶子结点的最短路径。npl(NULL) = -1
2. 对于左式堆的任一节点 X，满足 $npl(L)\ge npl(R)$

如果左式堆的右路径上有 r 个节点，那么这个堆最少有 $2^r-1$ 个节点

操作

插入是特殊的合并，因此只考虑合并两个左式堆

合并

定义一个左式堆如下

struct TreeNode 
{ 
	ElementType	    Element;
	PriorityQueue	    Left;
	PriorityQueue	    Right;
	int		    Npl;
} ;

合并函数 merge 如下，目的是保证 H1 和 H2 都非空，且 H1 不大于 H2

PriorityQueue  Merge ( PriorityQueue H1, PriorityQueue H2 )
{ 
	if ( H1 == NULL )   return H2;	
	if ( H2 == NULL )   return H1;	
	if ( H1->Element < H2->Element )  return Merge1( H1, H2 );
	else return Merge1( H2, H1 );
}

merge1 如下，可以阐述为：

1. 首先将 H1 的右子树和 H2 合并，作为 H1 的右子树
2. 如果合并后 H1 的左式堆性质被破坏，则交换其两个孩子
3. 更新 H1 的 npl（交换后一定是 H1->Right->Npl + 1）

static PriorityQueue
Merge1( PriorityQueue H1, PriorityQueue H2 )
{ 
	if ( H1->Left == NULL ) 	/* single node */
		H1->Left = H2;	/* H1->Right is already NULL 
				    and H1->Npl is already 0 */
	else {
		H1->Right = Merge( H1->Right, H2 );     /* Step 1 & 2 */
		if ( H1->Left->Npl < H1->Right->Npl )
			SwapChildren( H1 );	/* Step 3 */
		H1->Npl = H1->Right->Npl + 1;
	} /* end else */
	return H1;
}

Skew Heap

斜堆是条件更宽松的左式堆

与左式堆不同，斜堆在任何情况下都会交换子树

定义和操作与左式堆类似，在此不表

复杂度

对斜堆进行均摊分析，定义势能函数 $\Phi(D_i)$ 为 heavy 节点的数量；定义 heavy 节点 X 为：X 的右子树的后代数量不小于 X 的后代的一半（X 的后代包括 X 自己）

$$T_{amortized}=O(\log N)$$

Binomial Queue

二项队列是二项树的集合

二项树

记高度为 k 的二项树为 $B_k$

$B_0$ 是只有一个节点的树

$B_k$ 是两个 $B_{k-1}$ 的组合，其中一个是另一个的子树

$B_k$ 的根有 k 个孩子，分别是 $B_0, B_1, ..., B_{k-1},B_k$
$B_k$ 有 $2^k$ 个节点，深度为 d 的节点数量是 $C_k^d$

性质

二项队列中不会出现 2+ 个相同高度的二项树

具有 n 个元素的二项队列的结构是一定的，就是 n 的二进制表示

操作

FindMin

由于最小值一定出现在根上，对根遍历即可

$$T(N)=O(\log N)$$

Merge

从小到大依次合并，$B_k$ 和 $B_k$ 合并成 $B_{k+1}$

$$T(N)=O(\log N)$$

Insertion

特殊的合并，向初始为空的二项队列进行 N 次插入，总共需要 $O(N)$ 的消耗

实现

typedef struct BinNode *Position;
typedef struct Collection *BinQueue;
typedef struct BinNode *BinTree;  /* missing from p.176 */

struct BinNode 
{ 
	ElementType	    Element;
	Position	    LeftChild;
	Position 	    NextSibling;
} ;

struct Collection 
{ 
	int	    	CurrentSize;  /* total number of nodes */
	BinTree	TheTrees[ MaxTrees ];
} ;

BinTree
CombineTrees( BinTree T1, BinTree T2 )
{  /* merge equal-sized T1 and T2 */
	if ( T1->Element > T2->Element )
		/* attach the larger one to the smaller one */
		return CombineTrees( T2, T1 );
	/* insert T2 to the front of the children list of T1 */
	T2->NextSibling = T1->LeftChild;
	T1->LeftChild = T2;
	return T1;
}

BinQueue  Merge( BinQueue H1, BinQueue H2 )
{	BinTree T1, T2, Carry = NULL; 	
	int i, j;
	if ( H1->CurrentSize + H2-> CurrentSize > Capacity )  ErrorMessage();
	H1->CurrentSize += H2-> CurrentSize;
	for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) {
	    T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i]; /*current trees */
	    switch( 4*!!Carry + 2*!!T2 + !!T1 ) { 
		case 0: /* 000 */
	 	case 1: /* 001 */  break;	
		case 2: /* 010 */  H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL; break;
		case 4: /* 100 */  H1->TheTrees[i] = Carry; Carry = NULL; break;
		case 3: /* 011 */  Carry = CombineTrees( T1, T2 );
			            H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
		case 5: /* 101 */  Carry = CombineTrees( T1, Carry );
			            H1->TheTrees[i] = NULL; break;
		case 6: /* 110 */  Carry = CombineTrees( T2, Carry );
			            H2->TheTrees[i] = NULL; break;
		case 7: /* 111 */  H1->TheTrees[i] = Carry; 
			            Carry = CombineTrees( T1, T2 ); 
			            H2->TheTrees[i] = NULL; break;
	    } /* end switch */
	} /* end for-loop */
	return H1;
}

ElementType  DeleteMin( BinQueue H )
{	BinQueue DeletedQueue; 
	Position DeletedTree, OldRoot;
	ElementType MinItem = Infinity;  /* the minimum item to be returned */	
	int i, j, MinTree; /* MinTree is the index of the tree with the minimum item */

	if ( IsEmpty( H ) )  {  PrintErrorMessage();  return –Infinity; }

	for ( i = 0; i < MaxTrees; i++) {  /* Step 1: find the minimum item */
	    if( H->TheTrees[i] && H->TheTrees[i]->Element < MinItem ) { 
		MinItem = H->TheTrees[i]->Element;  MinTree = i;    } /* end if */
	} /* end for-i-loop */
	DeletedTree = H->TheTrees[ MinTree ];  
	H->TheTrees[ MinTree ] = NULL;   /* Step 2: remove the MinTree from H => H’ */ 
	OldRoot = DeletedTree;   /* Step 3.1: remove the root */ 
	DeletedTree = DeletedTree->LeftChild;   free(OldRoot);
	DeletedQueue = Initialize();   /* Step 3.2: create H” */ 
	DeletedQueue->CurrentSize = ( 1<<MinTree ) – 1;  /* 2^MinTree – 1 */
	for ( j = MinTree – 1; j >= 0; j – – ) {  
	    DeletedQueue->TheTrees[j] = DeletedTree;
	    DeletedTree = DeletedTree->NextSibling;
	    DeletedQueue->TheTrees[j]->NextSibling = NULL;
	} /* end for-j-loop */
	H->CurrentSize  – = DeletedQueue->CurrentSize + 1;
	H = Merge( H, DeletedQueue ); /* Step 4: merge H’ and H” */ 
	return MinItem;
}

Backtracking

解决一个问题的方法之一是枚举所有可能的答案，然而不是所有问题的可能的答案都是足够少的，回溯算法使得我们可以在枚举答案的过程中，消除一些明显不可能的答案（也就是剪枝 prunning）

八皇后问题

对于枚举法解决 N 皇后问题，有 $T(N)=O(N!)$

想象一个 DFS 的过程，来检查决策树，一旦遇到冲突，就返回

收费公路重构问题 The Turnpike Reconstruction Problem

给定 N 个点和 N(N - 1) / 2 个距离组成的距离集 S，要求在 x 轴上部署这些点，使得点与点的距离集和给定的距离相同

解决方法

1. $x_1 = 0;x_N=max\{S\}$
2. 找到 S 中目前最大的距离，放置点（2 种方法，靠近 $x_1$ 或 $x_N$）
3. 进行检查，检查成功则从 S 中删去检查出来的距离并回到 2；否则回溯

代码

bool Reconstruct ( DistType X[ ], DistSet D, int N, int left, int right )
{ /* X[1]...X[left-1] and X[right+1]...X[N] are solved */
    bool Found = false;
    if ( Is_Empty( D ) )
        return true; /* solved */
    D_max = Find_Max( D );
    /* option 1：X[right] = D_max */
    /* check if |D_max-X[i]|D is true for all X[i]’s that have been solved */
    OK = Check( D_max, N, left, right ); /* pruning */
    if ( OK ) { /* add X[right] and update D */
        X[right] = D_max;
        for ( i=1; i<left; i++ )  Delete( |X[right]-X[i]|, D);
        for ( i=right+1; i<=N; i++ )  Delete( |X[right]-X[i]|, D);
        Found = Reconstruct ( X, D, N, left, right-1 );
        if ( !Found ) { /* if does not work, undo */
            for ( i=1; i<left; i++ )  Insert( |X[right]-X[i]|, D);
            for ( i=right+1; i<=N; i++ )  Insert( |X[right]-X[i]|, D);
        }
    }
    /* finish checking option 1 */
    if ( !Found ) { /* if option 1 does not work */
        /* option 2: X[left] = X[N]-D_max */
        OK = Check( X[N]-D_max, N, left, right );
        if ( OK ) {
            X[left] = X[N] – D_max;
            for ( i=1; i<left; i++ )  Delete( |X[left]-X[i]|, D);
            for ( i=right+1; i<=N; i++ )  Delete( |X[left]-X[i]|, D);
            Found = Reconstruct (X, D, N, left+1, right );
            if ( !Found ) {
                for ( i=1; i<left; i++ ) Insert( |X[left]-X[i]|, D);
                for ( i=right+1; i<=N; i++ ) Insert( |X[left]-X[i]|, D);
            }
        }
        /* finish checking option 2 */
    } /* finish checking all the options */
    
    return Found;
}

模板

bool Backtracking ( int i )
{   Found = false;
    if ( i > N )
        return true; /* solved with (x1, …, xN) */
    for ( each xi  Si ) { 
        /* check if satisfies the restriction R */
        OK = Check((x1, …, xi) , R ); /* pruning */
        if ( OK ) {
            Count xi in;
            Found = Backtracking( i+1 );
            if ( !Found )
                Undo( i ); /* recover to (x1, …, xi-1) */
        }
        if ( Found ) break; 
    }
    return Found;
}

回溯的效率跟 S 的规模、约束函数的复杂性、满足约束条件的结点数相关。
约束函数决定了剪枝的效率，但是如果函数本身太复杂也未必合算。
满足约束条件的结点数最难估计，使得复杂度分析很难完成。

如果 S 有不同的大小，更小的 S 优先

井字棋 Tic-tac-toe: Minimax Strategy

代入电脑，尝试理解电脑是如何从 30 多万种可能性中找到胜利的下法的

定义对于某个位置 P 的估计性质的胜率函数 f

$$f(P)=W_C-W_H$$

W：可能取得胜利的数量（统计所有未下的棋子，下下去找就行了）
C：computer
H：human

computer 希望 f 增大；human 希望 f 减小

$\alpha-\beta$ Prunninng

以 max 为例，假如已知选择路线 1 的 min 分数为 30，在搜索后继的路线 2 时，发现存在分数为 20 的情况，那么路线 2 无需继续搜索（进行剪枝），因为下一次会走 min 选择，路线 2 的实际分数一定不大于 20

同理，在 min 选择的时候，假如路线出现了比之前大的分数，也可以剪枝

$\alpha-\beta$ Prunninng 可以在实践中将搜索量减少到 $O(\sqrt{N})$

处理决策树时，从底层往上，类似于 DFS

Divide and Conquer

Divide - Conquer - Combine

$$T(N) = aT(N/b) + f(N)$$

Closest Points Problem

给定平面中 N 个点，找到距离最近的 2 个点

Sol.

递归的：将平面分成 2 部分，分别从左边，中间，右边三个区域中找到最近的 2 个点（左边指 2 个点都在左边）

分治法复杂度计算

替换法 Substitution method

guess, then prove (?)
疑似有些幽默了

$$T( N ) = 2 T( N / 2 ) + N\lrArr T(N)=O(N\log N)$$

Recursion-tree method

将所有复杂度构建一棵递归树

$$T( N ) = 3 T( N / 4 ) + O(N^2)$$

$$=cN^2+3/16*cN^2+(3/16)^2*cN^2+...+3^{\log_4N}*T(1)$$

$$=O(3^{\log_4N})=O(N^{\log_43})$$

Master method

Theorem

$$T(N) = aT(N/b) + O(N^k\log^pN)$$

$$T(N)=\begin{cases} O(N^{\log_b a}),&a>b^k\\ O(N^k\log^{p+1}N),&a=b^k\\ O(N^k\log^{p}N),&a<b^k\\ \end{cases}$$

Dynamic Programming

使用储存中间数据的表格而不是递归的方法解决问题

斐波那契数列

int  Fibonacci ( int N ) 
{   int  i, Last, NextToLast, Answer; 
    if ( N <= 1 )  return  1; 
    Last = NextToLast = 1;    /* F(0) = F(1) = 1 */
    for ( i = 2; i <= N; i++ ) { 
        Answer = Last + NextToLast;   /* F(i) = F(i-1) + F(i-2) */
        NextToLast = Last; Last = Answer;  /* update F(i-1) and F(i-2) */
    }  /* end-for */
    return  Answer; 
}

Ordering Matrix Multiplications

对于连续的矩阵相乘，寻找一个计算量最小的顺序

令 $b_n$ 为连续 n 个矩阵相乘的顺序数量

$$b_n=\sum_{i=1}^{n-1}b_ib_{n-1}$$

$$\Rightarrow b_n=O(\displaystyle\frac{4^n}{n\sqrt{n}})$$

/* r contains number of columns for each of the N matrices */ 
/* r[ 0 ] is the number of rows in matrix 1 */ 
/* Minimum number of multiplications is left in M[ 1 ][ N ] */ 
void OptMatrix( const long r[ ], int N, TwoDimArray M ) 
{   int  i, j, k, L; 
    long  ThisM; 
    for( i = 1; i <= N; i++ )   M[ i ][ i ] = 0; 
    for( k = 1; k < N; k++ ) /* k = j - i */ 
        for( i = 1; i <= N - k; i++ ) { /* For each position */ 
	j = i + k;    M[ i ][ j ] = Infinity; 
	for( L = i; L < j; L++ ) { 
	    ThisM = M[ i ][ L ] + M[ L + 1 ][ j ] 
		    + r[ i - 1 ] * r[ L ] * r[ j ]; 
	    if ( ThisM < M[ i ][ j ] )  /* Update min */ 
		M[ i ][ j ] = ThisM; 
	}  /* end for-L */
        }  /* end for-Left */
}

$$T(N)=O(N^3)$$

Optimal Binary Search Tree

对于单词 w 有出现概率 p，将 w 构建一个二叉树使得查询期望消耗最小

$$c_{i,j}=p_k+c_{i,k-1}+c_{k+1,j}+w_{i,k-1}+w_{k+1,j}=w_{i,j}+c_{i,k-1}+c_{k+1,j}$$

$$\Rightarrow c_{i,j}=\min_{i<k\le j}\{w_{i,j}+c_{i,k-1}+c_{k+1,j}\}$$

All-Pairs Shortest Path

/* A[ ] contains the adjacency matrix with A[ i ][ i ] = 0 */ 
/* D[ ] contains the values of the shortest path */ 
/* N is the number of vertices */ 
/* A negative cycle exists iff D[ i ][ i ] < 0 */ 
void AllPairs( TwoDimArray A, TwoDimArray D, int N ) 
{   int  i, j, k; 
    for ( i = 0; i < N; i++ )  /* Initialize D */ 
         for( j = 0; j < N; j++ )
	 D[ i ][ j ] = A[ i ][ j ]; 
    for( k = 0; k < N; k++ )  /* add one vertex k into the path */
         for( i = 0; i < N; i++ ) 
	 for( j = 0; j < N; j++ ) 
	    if( D[ i ][ k ] + D[ k ][ j ] < D[ i ][ j ] ) 
		/* Update shortest path */ 
		 D[ i ][ j ] = D[ i ][ k ] + D[ k ][ j ]; 
}

$$T(N)=O(N^3)$$

But faster in dense 稠密 graph

Product Assembly

f[0][0]=0; L[0][0]=0;
f[1][0]=0; L[1][0]=0;
for(stage=1; stage<=n; stage++){
  for(line=0; line<=1; line++){
    f_stay = f[  line][stage-1] + t_process[  line][stage-1];
    f_move = f[1-line][stage-1] + t_transit[1-line][stage-1];
    if (f_stay<f_move){
      f[line][stage] = f_stay;
      L[line][stage] = line;
    }
    else {
      f[line][stage] = f_move;
      L[line][stage] = 1-line;
    }
  }
}