| « | December 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | |
|
公告 |
在此正式宣布，这个Blog下的地盘，都是偶的啦  这个版面专用于技术...别的就先不贴了！ |
| 信息 |
|
blog名称:技术至上
日志总数:4
评论数量:1
留言数量:0
访问次数:73485
建立时间:2004年12月11日 |
| |
|
 [Algorithms]脱线MIN算法
读书笔记, 软件技术
Stanley 发表于 2005/1/16 2:16:42 |
|
Union-Find算法的应用与推广
指令Insert(i)：把元素i插入集合S中。指令Extract_min：从集合S中找出最小元并进行删除。两种指令的简单表示法：用i表示Insert(i)，用E表示Extract_min。例：7，2，5，9，E，6，E，E，3，E，1，4，E这种序列满足两个性质：1）任一i (1≤ i ≤n) 在序列中最多出现一次（元素之间互不相同）；2）从左起任意一段中，插入指令条数要大于等于E指令条数。（否则无元素可删。）脱线MIN问题：给定一个Insert与Extract_min的指令序列σ之后，对在序列中出现的每个i，算法要输出i是被第几条E指令删除的。（对于序列中未出现的i，算法应输出相应信息。）上例中有：1(5), 2(1), 3(4), 4(未被删除)，5(2)，6(3)，7，9与4一样未被删除，8未出现。因要对合并后的集合进行强制命名，故采用Aho书中的UNION(i,j,k)算法（可强制命名为k）：wlg assume COUNT[ROOT[i]] ≤ COUNT[ROOT[j]](otherwise interchange i and j in the following lines)LARGE←ROOT[j];SMALL←ROOT[i];FATHER[SMALL]←LARGE;COUNT[LARGE]←COUNT[LARGE]+ COUNT[SMALL];NAME[LARGE]←k;ROOT[k]←LARGE;由于该算法不执行Find，故在O(1)时间里即可完成。算法开始之前，先把所有元素的所属集合名NAME[i]置为0（O(n)）；再扫描指令序列，把由E隔开的每段中的元素组成若干个集合并命名（O(n)）：e.g.: 1=，2=，3={}9,7,5,2{}6∅，4={}3，5={}4,1，6= ∅用集合名（数字）来表示删除i的E指令序号，算法从i=1开始逐一检查，找到1所在的元素集合名（5），输出1是被第5条E指令删除的;输出后用UNION算法把集合5与6合并为6：6=。 {4,1 }下一步看i=2，找到2所在的元素集合名（1），输出2是被第1条E指令删除的;输出后用UNION算法把集合1、2合并, 得到2={2,5,6,7,9}。其次看i=3，找到3所在的元素集合名（4），输出3是被第4条E指令删除的；输出后用UNION算法把集合4与6合并(集合5已经不存在了)，得到6={1,3,4}。i=4时，找到4所在的元素集合名（6），但6>E指令条数（只有5条），故输出“4未被删除”。i=5时，找到5所在的元素集合名（2），输出5是被第2条E指令删除的；输出后用UNION算法把集合2与3合并，得3={2,5,6,7,9}。i=6时，找到6所在的元素集合名（3），输出6是被第3条E指令删除的；输出后用UNION算法把集合3与6合并，得6={1,2,3,4,5,6,7,9}其后的7，9与4一样未被删除，而8未在序列中出现，因Find(8)=0，故应输出“8未出现”。为合并时方便地找到后继集合，引入Pred和Succ 2个数组：Pred[j]记录了前一个集合的名称(数字),初始时为j-1，Succ[j]记录了后一个集合的名称(数字),初始时为j+1。算法：for i=1 to n do {j←FIND(i);if j=0 then {输出“i未在序列中出现”}else if j>k then {输出“i未被删除”}else{ /* i确实被删除了*/输出“i被第j条E指令所删除”；UNION(j，Succ[j]，Succ[j])；Succ[Pred[j]]←Succ[j]；/* 集合j不再存在*/Pred[Succ[j]]←Pred[j]}}算法的主要工作是执行O(n)条FIND指令，（其余工作在循环的每一轮都是常数时间）故该算法的时间复杂度为O(n*G(n))。
|
|
|