亚洲必赢手机算法概论笔记,拖动时中怎样推断源节点作为靶子节点的子节点依然手足节点

by admin on 2019年9月22日

指标:只允许同级拖动。

选取步步逼近的诀要社团难点的解,其下一步的抉择总是在脚下看来收效最快和效劳最醒目标极其。

五个剖断:

应用前提: 验证贪心形式的有效

1.原节点(假使为:S)的父级如若不对等目的节点(假如为:T)的父节点,那么发生了跨级,即非同级移动。那几个剖断很轻巧。

最小生成树(minimum spanning tree)

输入:无向图G=(V, E); 边权重w(e)
输出:树T=(V, E’),

其中![](http://latex.codecogs.com/svg.latex?E’
\subseteq E),
使得权重![](http://latex.codecogs.com/svg.latex?weight(T))
= \sum_{e \in E’} w_e)

2.S、T是同顶级的,可是S是活动到T下一流,这种情景下,移动进度中,S和T的父节点是大同小异的,不可能剖断是还是不是跨级移动,那么如何做判别呢?

树的习性
  1. 不无n个节点的树的边数为n-1
  2. 亚洲必赢手机,三个无向图是树,当且仅当任性七个节点间仅存在独一路线

方案1:在afterDrop事件中来决断父节点是或不是一致,因为运动已经做到,父节点发什么了转移,根据推断结果然后再把节点苏醒回去。这种做法很low。

Kruskal算法

不停地再度地挑选未被选中的边中权重最轻而且不会产生环的一条。

procudure kruskal
for all u in V:
    makeset(u)
sort the edges E by weight
for all edges {u, v} in E, in increasing order of weight:
    if find(u) != find(v)
        add edge {u,v} to X
        union(u, v)
  • makeset(x): 创设叁个仅包蕴x的单身成团
  • find(x): x属于哪个集结?
  • union(x, y): 合併包罗x和y的集聚
    共需要|V|次makeset + 2|E|次find + |V|-1次union操作

find操作不自然成功触发union操作,由此最坏情状下会要求2|E|次

数据结构:有向树
集合中的顶点对应树的节点,各种节点蕴涵贰个父指针,一流级指向树根。树根的父指针指向该因素本身。

亚洲必赢手机 1

有向树

node

  1. p //父节点指针
  2. rank //该节点下悬挂的子树高度
  • 方案一
    统一时让相当的低的树的根指向较高的树的根(基于品级的联合)

  procedure makeset(x)
    p(x) = x
    rank(x) = 0
  procedure find(x)
    while(x != p(x))
        x = p(x)
    return x
  procedure union(x, y)
    rx = find(x), ry = find(y)
    if rx == ry return
    if rank(rx) > rank(ry)
        p(ry) = rx
    else if rank(rx) == rank(ry)
        p(rx) = ry
        rank(ry) += 1
    else
        p(rx) = ry
  • 方案二
    路径压缩:
    循着一密密麻麻的父指针最终找到树根后,退换全部这么些父指针的对象,使其从来指向树根

  procedure find(x)
    while(x != p(x))
        p(x) = find(p(x))
    return x

find中rank未进行更新,此时rank的意思不能解释为子树的莫斯科大学。
这儿有向树的冲天不会当先2。

  • 方案三
    作者们能够窥见find和union操作均只关注树的顶层,是还是不是足以间接行使树高为2的有向树啊?并在union()操作中,对于多少个树高为2的有向树,举办内部一棵的收缩。

但留心深入分析能够吸收,此方案与方案二精神同样,仅将find()操作总共所做的职业转移到union()操作中。

方案序号 makeset find union 该部分效率
1 O(1) O(logn) O(logn) (V+E)logn
2 O(1) > O(1) > O(1) V+E

方案2什么样分担深入分析?TODO
总时间复杂度为T(sort)和T(find/union)中相当大的拾叁分

see java implement:
greedy.mst.KruskalMST

方案2:在运动进度中推断S被移位到T节点的职分:T节点前、T节点后、T节点下,倘诺是移动到T节点下,那么禁止移动就能够。

Prim算法

算法中间阶段的边集X构成二个子树,该子树顶点的聚合表示为S。大家选拔S中顶点与S外顶点之间的最轻边出席X,即以细小代价将享有原先不属于S的极端包括进来。

与Dijkstra的关系
伪代码基本一致,不同显示在优先队列排序使用的键值

  • Prim: 键值为节点与集结S中顶点间的最轻边的权重;
  • Dijkstra:键值为节点到起先点的完全路线长度;

pseudocode如下:

procedure prim
for all u in V
    dist(u) = \infty
    pre(u) = nil

dist(s) = 0
PQ = makequeue(V) (using dist-values as keys)
while PQ is not empty
    u = deletemin(PQ)
    for all edges (u, v) in E
        if dist(v) > l(u, v)
            dist(v) = l(u, v)
            pre(v) = u
            decreasekey(PQ, v)

能够看来仅是dist(u)+l(u, v)变为l(u, v)

see java implement:
greedy.mst.PrimMST

上边贴出方案2剖断方法:

哈夫曼编码
  • 编码压缩

削减比越高,随机性越低,可预测性越好

  • 无前缀本性,任一个码字都不应该是任何码字的前缀

无前缀编码中每种字符对应于树中的三个叶节点

procedure Huffman(f)
Input: An array f[1...n] of frequencies
Output: An encoding tree with n leaves

let H be a priority queue of integers, ordered by f
for i = 1 to n: insert(H, i)
for k = n + 1 to 2n -1
    i = deletemin(H), j = deletemin(H)
    create a node numbered k with children i,j
    f[k] = f[i] + f[j]
    insert(H, k)

编码输出

call print(root, 1)

print(node, num) {
  if node is null return
  print node's code based on num
    :num to binary and then remove the head '1'
  print(node.left, 2*num)
  print(node.right, 2*num + 1)
}

see implement:
greedy.Huffman

 

其他
/// <summary>
        /// 获取拖动过程中的方向
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        /// <returns></returns>
        private DragInsertPosition AjustDirection(object sender, DragEventArgs e)
        {
            TreeListNode dragNode, targetNode;
            TreeList tl = sender as TreeList;
            Point p = tl.PointToClient(new Point(e.X, e.Y));
            dragNode = e.Data.GetData(typeof(TreeListNode)) as TreeListNode;
            TreeListHitInfo hit = tl.CalcHitInfo(p);
            PropertyInfo pi = typeof(TreeList).GetProperty("Handler", BindingFlags.Instance | BindingFlags.NonPublic);
            TreeListHandler handler = (TreeListHandler)pi.GetValue(tl, null);
            return handler.StateData.DragInfo.DragInsertPosition;

        }

 private void treeListNav_DragOver(object sender, DragEventArgs e)
        {
            TreeListNode dragNode = e.Data.GetData(typeof(TreeListNode)) as TreeListNode;
            System.Diagnostics.Debug.WriteLine("Over:" + e.Effect);
            TreeListNode targetNode;
            Point p = treeListNav.PointToClient(MousePosition);
            targetNode = treeListNav.CalcHitInfo(p).Node;
            if (targetNode == null)
            {
                return;
            }
            FileContent tagParent = null;//拖动后的父级数据
            if (targetNode.ParentNode != null)
            {
                tagParent = this.treeListNav.GetRow(targetNode.ParentNode.Id) as FileContent;
            }
            if (sourceParent != tagParent)//发生跨级拖动
            {
                // MessageHelper.ShowHit("只能在同一级拖动,移动未成功。");
                e.Effect = DragDropEffects.None;
                return;
            }

            //移动到了同级子节点下
            if (AjustDirection(sender, e) == DragInsertPosition.AsChild)
            {
                e.Effect = DragDropEffects.None;                
                return;
            }

            if (e.Effect == DragDropEffects.Link)
            {
                //     MessageHelper.ShowHit("不能移动到子集。");
                e.Effect = DragDropEffects.None;
            }


        }
Horn公式

难点陈诉
Horn公式中最焦点的指标是取值为true或false的布尔变量,变量的文化通过包涵式、纯否定两类子句来抒发。给定有些由以上两类子句构成的聚众,我们要求看清是或不是留存八个均等的讲解,即一组使得全部子句都满意的变量(true/false)赋值,该解释成为该Horn公式的贰个可满足赋值。

求解攻略
从具备变量为false开首,依次将“只需且不得不”这样做以使得有些包罗式满足的变量置为true;一旦有所的包涵式都得到满意,再回头检查是或不是具备否定子句还是知足。

其一分明移动方向的枚举:

集聚覆盖

主题素材陈说

亚洲必赢手机 2

图中的点表示一组城市和商场,要求城乡村建设设环保部分新的母校。

具体须求:

  1. 具有的高校都必需建在城镇上
  2. 从随机三个村镇接触,都应有可以在30海里的界定到达当中的某一所学校
    那正是说,最少必要建多少所学校吧?

较优解求解计谋(贪心)
对各种城市和市集x,令S(x)为在其30公里范围内的市场会合。
分选包蕴未被隐蔽元素的最大集结Si,不断重复,直到全数因素都被覆盖。

贪婪算法的临界因子
贪求无厌算法的解与实际的最优解的层面之比想必因难题输入的两样而区别,不过总小于ln(n)。大家称这一最大比值为贪欲算法的临界因子。

namespace DevExpress.XtraTreeList
{
    public enum DragInsertPosition
    {
        None = 0,
        AsChild = 1,
        Before = 2,
        After = 3
    }
}
写在最终
  • 立个Flag,TODO will be done some day。
  • 渣代码,且轻喷:worried:。

 

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图