Welcome to Narcissus's Blog!

• 0/1背包问题

  2018-12-23

  Narcissus

  algorithm

  背包问题
  • 0/1背包
    • 暴力解决：二维动态规划
    • 改进1：一维动态规划——（优化空间复杂度）

  0/1背包

  暴力解决：二维动态规划

  • 二维dp的定义：$f[i][j]​$: 考虑前i个物品，总体积为j的最大价值为$f[i][j]​$
  • 返回结果：$max(f[n][0~v])$,因为背包可以不填满，因此也存在不被选择的物体
  • 递推公式：
    • 不选择第i个物品：$f[i][j]=f[i-1][j]$
    • 选择第i个物品：$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])​$
  • 初始化：$f[0][0]=0​$
  • 复杂度：
    • 时间复杂度：$O(nv)​$
    • 空间复杂度：$O(n^2)​$

  #include<iostream>
  using namespace std;
  int N=1001;
  
  int main()
  {
      int n,v;
      cin>>n>>v;
      int V[N],W[N];
      for(int i=1;i<=n;i++)
      {
          cin>>V[i]>>W[i];
      }
      int dp[N][N];
      dp[0][0]=0;
      
      for(int i=1;i<=n;i++)
      {
          for(int j=0;j<=v;j++)
          {
              dp[i][j]=dp[i-1][j];//不选第i个物品
              if(j>=V[i])//选第i个物品
              {
                  dp[i][j]=max(dp[i][j],dp[i-1][j-V[i]]+ W[i]);
              }
          }
      }
      //背包可能没填满，但是要遍历完所有的背包
      int res=0;
      for(int i=0;i<=v;i++)res=max(res,dp[n][i]);
      cout<<res;
      return 0;
  }
  

  改进1：一维动态规划——（优化空间复杂度）

  • 定义dp数组：dp[j],表示容量为j时，最大的价值.

  • 递推公式：

    • $dp[j]=max(dp[j-v[i]]+w[i])​$

  • 技巧

    • 子程序：1.要保证dp[j]的递推来自第i-1个物品。dp[j]对应第f[i][j]，那么要保证dp[j]的递推来自dp[i-1][j-V[i]]，就要让容量递减的计算，也就是计算dp[v]->dp[0].抽象一个一维数组解决0/1背包的子程序（处理第i个物品）：

      int zeroOnePack(int dp[],int V[],int W[],n,v,i)//i为第i个物品
      {
          for(int j=v;j>=V[i];j--)
          {
              dp[j]=max(dp[j],dp[j-V[i]]+W[i])
          }
      }
      

    • 初始化

      • 要求恰好装满背包：在初始化时除了F [0]为0，其它dp [1..v ]均设为−∞，这样就可以保证最终得到的dp[v ]是一种恰好装满背包的6最优解。
      • 不要求装满背包:dp[0…v]=0

    #include<iostream>
    using namespace std;
    int N=1001;
      
    int main()
    {
        int n,v;
        cin>>n>>v;
        int V[N],W[N],dp[N];
      
        for(int i=1;i<=n;i++)
        {
            cin>>V[i]>>W[i];
        }
          
        for(int i=1;i<=n;i++)
        {
            for(int j=v;j>=V[i];j--)
            {
                dp[j]=max(dp[j],dp[j-V[i]]+ W[i]);
            }
            //or
            //zeroOnePack(int dp,V,W,n,v,i);
        }
        cout<<dp[v]<<endl;
        return 0;
    }
    

  Read All

  ---

• 自平衡二叉搜索树

  2018-10-28

  Narcissus

  数据结构
  • AVL树
  • RB-tree
    • 性质
    • 实现

  C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树

  是一种平衡的二叉搜索树，因而其查找的平均时间复杂度为元素总个数的对数（即logN）

  AVL树

  插入时出现失衡的情况有如下四种（其中X为最小失衡子树的根节点）：

  1. 插入点位于X的左子节点的左子树——左左；
  2. 插入点位于X的左子节点的右子树——左右；
  3. 插入点位于X的右子节点的左子树——右左；
  4. 插入点位于X的右子节点的右子树——右右。

  情况1和4对称，称为外侧插入，可以采用单旋转操作调整恢复平衡；2和3对称，称为内侧插入，可以采用双旋转操作调整恢复平衡：先经过一次旋转变成左左或右右，然后再经过一次旋转恢复平衡，例如：

  

  3，4类似于1，2。

  RB-tree

  RB-tree的平衡条件不同于AVL-tree，但同样运用了单旋转和双旋转的恢复平衡的机制，下面我们详细介绍RB-tree的实现。

  性质

  • 每个节点不是黑色就是红色；
  • 根节点为黑色；
  • 每个叶子节点（NIL）为黑色；
  • 如果节点为红，其左右子节点必为黑；
  • 对每个节点，从该节点到其子孙中的叶子节点的所有路径上所包含的黑色点数目相同。

  这些约束保证了这个树大致上是平衡的，这也决定了红黑树的插入、删除、查询等操作是比较快速的。 根据规则5，新增节点必须为红色；根据规则4，新增节点之父节点必须为黑色。当新增节点根据二叉搜索树的规则到达其插入点时，却未能符合上述条件时，就必须调整颜色并旋转树形。下图是一个典型的RB-tree（来自wiki）：

  

  实现

  • RB-tree的结构定义：主要包含一个标志颜色的bool变量 _M_color，3个节点指针 _M_parent , _M_left , _M_right，2个成员函数 _S_minimum 和 _S_maximum （分别求取最小（最左）、最大（最右）节点）

  typedef bool _Rb_tree_Color_type;
  const _Rb_tree_Color_type _S_rb_tree_red = false;
  const _Rb_tree_Color_type _S_rb_tree_black = true;
  //======================================
  struct _Rb_tree_node_base { // 节点的定义
    typedef _Rb_tree_Color_type _Color_type;
    typedef _Rb_tree_node_base* _Base_ptr;
    _Color_type _M_color; // 节点颜色，实际为一个bool型变量
    _Base_ptr _M_parent; // 指向父节点，方便遍历
    _Base_ptr _M_left;
    _Base_ptr _M_right;
  
    static _Base_ptr _S_minimum(_Base_ptr __x) {
      while (__x->_M_left != 0) __x = __x->_M_left;
      return __x;
    }
    static _Base_ptr _S_maximum(_Base_ptr __x) {
      while (__x->_M_right != 0) __x = __x->_M_right;
      return __x;
    }
  };
  //======================================
  template <class _Value> struct _Rb_tree_node : public _Rb_tree_node_base { // 节点的定义
    typedef _Rb_tree_node<_Value>* _Link_type;
    _Value _M_value_field;
  };
  

  • 迭代器：自增自减操作

  • 插入操作

  • • 基本插入操作

    • 调整至平衡

    • 破坏RB-tree性质4的可能起因是插入了一个红色节点、将一个黑色节点变为红色或者是旋转，而破坏性质5的可能原因是插入一个黑色的节点、节点颜色的改变（红变黑或黑变红）或者是旋转。

    • 新插入的节点的颜色必为红色，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点的父结点为红色时（如下图所示），将会违反红黑树的性质：一条路径上不能出现父子同为红色结点。这时就需要通过一系列操作来使红黑树保持平衡。为了清楚地表示插入操作以下在结点中使用“N”字表示一个新插入的结点，使用“P”字表示新插入点的父结点，使用“U”字表示“P”结点的兄弟结点，使用“G”字表示“P”结点的父结点。插入操作分为以下几种情况：

    • • 树为空
      • • 将插入节点改成黑色以满足性质2
      • 黑父（插入时不影响平衡）
      • • 红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。

      • 红父（复杂）

        由于父节点为红，所以祖父节点必为黑色。由于新节点和父节点均为红，所以需要重新着色或进行旋转，此时就需要考虑叔父节点的颜色，进而可能需要考虑祖父、祖先节点的颜色。

        • 叔父为红

          

        • 叔父为黑

          

  • 删除操作(复杂)

  • 查询操作（简单O(logN))
  Read All

  ---

• relation network for object detection

  2018-09-25

  Narcissus

  图像理解

  ObjectDetection  RelationshipDetection
  • 整体思路

  整体思路

  

  图1 整体结构

  主要是在原来的四阶段检测的基础上增加了关系信息模块，在instance recognition模块，FC模块和relation模块的输入输出都是一样的，因此能直接加入到FC层之后，这个relation模块主要是利用了每个物体与其他物体之间的关系，它的建立是基于原始attention model改的。而duplicate removal模块主要是代替NMS，进行一个二分类，去除一些重复的框。

  Read All

  ---

• Deep Visual-Semantic Alignments for Generating Image Description

  2018-09-23

  图像理解

  图像字幕
  • Deep Visual-Semantic Alignments for Generating Image Description

  Deep Visual-Semantic Alignments for Generating Image Description

  Read All

  ---

• Faster-RCNN论文解析

  2018-09-22

  图像理解

  ObjectDetection

  

  物体检测领域（Object Detection）领域是计算机视觉的经典问题，其目标是在输入图像中寻找特定类别的物体，并使用矩形框将物体包括在内，并预测出该框的类别。深度学习在物体检测领域已经取得了相比于传统视觉方法质的提升，其中很重要原因就是单阶段检测方法（One-Stage Method）和两阶段检测方法（Two-Stage Method）的出现，本篇博客将就物体检测Two Stage检测经典方法Faster RCNN做一些简单的总结，结合一些源码给出个人的理解。

  Read All

  ---

• Neural Motifs Scene Graph Pasing With Global Context!

  2018-09-12

  图像理解

  RelationshipDetection
  • Stacked Motif Networks

  Stacked Motif Networks

  Read All

  ---