传教士和野人问题（M-C问题）

有N个传教士和N个野人来到河边渡河，河岸有一条船，每次至多可供k人乘渡。河两岸以及船上的野人数目总是不超过传教士的数目(否则不安全，传教士有可能被野人吃掉)。即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M(传教士数)≥C(野人数)和M+C≤k的摆渡方案。以下讨论三个传教士三个野人还有一条船最多能载两个人的方案。

状态空间

我们用一个三元组(m，c，b)来表示河岸上的状态，其中m、c分别代表某一岸上传教士与野人的数目，b=1表示船在这一岸，b=0则表示船不在

约束条件是: 两岸上M≥C, 船上M+C≤2

（mi，ci）为船上的传教士和野人数量

左岸初态为（3,3,1），终态为（0,0,0）

upload successful

为什么不能直接暴力穷举然后剪枝？

因为可能运过去两个人，然后又把同样的两个人运回来了(或者使用别的形式但是依旧是空转)，所以要杜绝这种可能，当然最好的方法就是使用带有记忆的状态，如果之前遇到过这种状态那就拒绝执行return。

所以….如何实现去重的目标？？？

答：set，我采取的是单个状态采用int，记录路径经过的状态采用string（中间用空格隔开）

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<set>
#include<vector>
using namespace std;
int N;
set<string>ans;
void print(vector<int>way){
    int i=0;
    string h;
    for(i=1;i<way.size();i++){
        printf("%03d   ",way[i]);
        if(way[i]<100){
            h+="0";
        }
        h+=to_string(way[i]);
        h+=" ";
    }
    cout<<"\n-------"<<endl;
    ans.insert(h);
}
void dfs(int pre,int ni,int nj,int c,set<int>s,vector<int>way){
    // set insert
    int now=ni*100+nj*10+c;
    s.insert(pre);    
    if(s.count(now)||(N-ni)<0||(N-nj)<0||ni<0||nj<0||(ni<nj&&ni!=0)||((N-ni)<(N-nj)&&(N-ni)!=0)){
        return;
    }
    if(pre==0){
        // 如果上一轮就截止了
        print(way);
        return;
    }
    way.push_back(pre);
    if(c==1){
        // zero people . no one on ship is illegal
        // dfs(now,ni,nj,0,s,way);
        // one people on
        dfs(now,ni-1,nj,0,s,way);
        dfs(now,ni,nj-1,0,s,way);
        // two people on
        dfs(now,ni-2,nj,0,s,way);
        dfs(now,ni,nj-2,0,s,way);
        dfs(now,ni-1,nj-1,0,s,way);
    }
    else{
        // zero people . no one on ship is illegal
        // dfs(now,ni,nj,1,s,way);
        // one people on
        dfs(now,ni+1,nj,1,s,way);
        dfs(now,ni,nj+1,1,s,way);
        // two people on
        dfs(now,ni+2,nj,1,s,way);
        dfs(now,ni,nj+2,1,s,way);
        dfs(now,ni+1,nj+1,1,s,way);        
    }
}
int main(){
    int chooseN;
    int c=1;
    // init num and ship side 1 means left and 0 means right
    int ni,nj;
    // Ni(传教士),Nj(野人) on the left side.
    int pre=-1;
    set<int>s;
    //cin>>chooseN;
    chooseN=3;
    N=nj=ni=chooseN;
    vector<int>way;
    dfs(pre,ni,nj,c,s,way);
    cout<<"\nfinally , the answer is:\n\n";
    for(auto it=ans.begin();it!=ans.end();it++){
        cout<<*it<<endl;
    }
}

/*
331   310   321   300   311   110   221   020   031   010   111   
-------
331   310   321   300   311   110   221   020   031   010   111   
-------
331   310   321   300   311   110   221   020   031   010   021   
-------
331   310   321   300   311   110   221   020   031   010   021
-------
331   220   321   300   311   110   221   020   031   010   111
-------
331   220   321   300   311   110   221   020   031   010   111   
-------
331   220   321   300   311   110   221   020   031   010   021
-------
331   220   321   300   311   110   221   020   031   010   021
-------

finally , the answer is:

331 220 321 300 311 110 221 020 031 010 021
331 220 321 300 311 110 221 020 031 010 111
331 310 321 300 311 110 221 020 031 010 021
331 310 321 300 311 110 221 020 031 010 111
*/

传说中的基于A*算法的解法：

评估函数的建立：

M 表示左岸的传教士的人数，N 表示左岸野人的数目，B 取值为0或1 ，1 表示船在左岸，0 表示船在右岸。d 表示节点的深度。

  • 下面我们来证明h(n)＝M+C-2B是满足A*条件的：

我们分两种情况考虑。
（1）先考虑船在左岸的情况。如果不考虑限制条件，也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河2人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需要摆渡[(M+N-3)/2]*2+1次。其中分子上的”－3”表示剩下三个留待最后一次运过去。除以”2”是因为一个来回可以运过去2人，需要[(M+N-3)/2]个来回，而”来回”数不能是小数，需要向上取整，这个用符号[ ]表示。而乘以”2”是因为一个来回相当于两次摆渡，所以要乘以2。而最后的”＋1”，则表示将剩下的3个运过去，需要一次摆渡。

化简得：需要 M+N-2次单向摆渡

（2）再考虑船在右岸的情况。同样不考虑限制条件。船在右岸，需要一个人将船运到左岸。因此对于状态(M，N，0)来说，其所需要的最少摆渡数，相当于船在左岸时状态(M+1，N，1)或(M，N+1，1)所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡数为：(M+N+1)-2+1。其中(M+N+1)的”＋1”表示送船回到左岸的那个人，而最后边的”＋1”，表示送船到左岸时的一次摆渡。

化简有：(M+N+1)-2+1=M+N。

综合船在左岸和船在右岸两种情况下，所需要的最少摆渡次数用一个式子表示为：$M+N-2B$ ，其中B＝1表示船在左岸，B＝0表示船在右岸。该摆渡次数是在不考虑限制条件下，推出的最少所需要的摆渡次数。

算法

红黑树

鸣谢：
https://www.jianshu.com/p/0eaea4cc5619
https://blog.csdn.net/tanrui519521/article/details/80980135
https://zhuanlan.zhihu.com/p/24367771

删除：https://www.cnblogs.com/tongy0/p/5460623.html

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

性能优于AVL树，C++中的map，以及Java中的TreeMap，TreeSet， Java8中的HashMap的实现也采用了红黑树。

5条基本特征：

（1）每个结点要么是红的要么是黑的。
（2）根结点是黑的。
（3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
（4）如果一个结点是红的，那么它的两个儿子都是黑的。
（5）对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

  • 红黑树的5条特性确保了从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，使得整棵树大致上是平衡的

upload successful

树的插入：（警惕红）

新插入的节点总是设为红色的，所以如果父节点为黑色，就不需要修复，因为没有任何性质被改变，所以只有在父节点为红色节点时需要做修复操作。

可以肯定调节的时候该点一定有grandparent，因为根节点为黑，连续两个红才需要调整。

情况1：cur为红，parent为红，pParent为黑，uncle存在且为红

则将parent，uncle改为黑，pParent改为红，然后把pParent当成cur，继续向上调整。

对策 :把父节点和叔叔节点变黑，爷爷节点涂红，然后把当前节点指针给到爷爷，让爷爷节点那层继续循环，接受红黑树特性检测。

simple case

z是当前点

情况2：cur为红，parent为红，pParent为黑，uncle不存在/u为黑

对策：当前节点的父节点作为新的当前节点，以新当前指点为支点左旋

parent为pParent的左孩子，cur为parent的左孩子，则进行右单旋转。

upload successful

情况3：当前节点的父节点是红色，叔叔节点是黑色/不存在，且当前节点是其父节点的右儿子，祖父节点的左儿子是父节点

对策： 父节点变黑，祖父变红，以祖父节点为支点右旋

1为当前点，祖父节点为下一轮遍历的当前节点。

只变色不拐

4为当前点，取初始父节点3为下一轮遍历的当前节点。然后交换一下3和4，然后再重组

不变色只拐

3为当前点，取父亲为下一轮遍历的当前节点。

变色+拐

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
#define N 1000
#define red true
#define black false
class Node{
    public:
    static int length;
    bool br;
    // true red false black
    int num;
    Node*l,*r,*f;
    Node(){
        num=-1;
        r=f=l=NULL;
    } 
};
int Node::length=0;
void left_turn(Node*&root){
    Node*p=root->f;
    Node*pP=root->f->f;
    if(p->l){
        p->l->f=pP;
    }
    p->f=pP->f;
    pP->r=p->l;
    p->l=pP;
    if(pP->f==NULL){

    }
    else if(pP->f->num>pP->num){
        pP->f->l=p;
    }
    else{
        pP->f->r=p;
    }
    pP->f=p;
}
void right_turn(Node*&root){
    Node*p=root->f;
    Node*pP=root->f->f;
    if(p->r){
        p->r->f=pP;
    }
    p->f=pP->f;
    pP->l=p->r;
    p->r=pP;
    if(pP->f==NULL){

    }
    else if(pP->f->num>pP->num){
        pP->f->l=p;
    }
    else{
        pP->f->r=p;
    }
    pP->f=p;
}
void balance(Node*&root){
    // 如果是top点，没有father/grandfather需要单独讨论，因为可能是红点做top点
    if(root->f==NULL){
        root->br=black;
        return;
    }
    else if(root->br==black){
        return;
    }
    if(root->f->br==red){
        // Need to deal with this situation.
        // first decide you are in which side(l/r). there will be two choice and four cases.
        if(root->f->f->l&&root->f->f->r&&root->f->f->l->br==red&&root->f->f->r->br==red){
            // balance1 , p=red , uncle=red
            root->f->f->br=red;
            root->f->f->l->br=black;
            root->f->f->r->br=black;
            balance(root->f->f);
        }
        else{
            // balance2, p(left)=red , uncle=black/NULL
            if(root->f->f->r==NULL||root->f->f->r->br==black){
                // right turn
                Node*pP=root->f->f;
                Node*p=root->f;
                if(root->f->num>root->num){
                    p->br=black;
                    pP->br=red;
                    right_turn(root);
                    balance(root->f);
                }
                else{
                    root->br=black;
                    pP->br=red;                    
                    // adjust
                    if(root->l){
                        root->l->f=root->f;
                    }
                    p->r=root->l;
                    pP->l=root;
                    root->f=pP;
                    root->l=p;
                    p->f=root;
                    right_turn(root->l);
                    balance(root);
                }
            }
            // balance3 , p(right)=red , uncle(left)=black/NULL
            else{   // warm up
                Node*pP=root->f->f;
                Node*p=root->f;
                //left turn
                if(root->f->num>root->num){
                    root->br=black;
                    pP->br=red;                    
                    // adjust
                    pP->r=root;
                    p->f=root;
                    root->f=pP;
                    Node*t=root;
                    // 为了防止root被误置为NULL,出此下策保留该root指针
                    p->l=root->r; // bug p->l(指向root的左指针)=root->r 变成了 root=root->r
                    
                    root=t;
                    root->r=p;
                    left_turn(root->r);
                    balance(root);
                }
                else{
                    p->br=black;
                    pP->br=red;                    
                    left_turn(root);
                    balance(root->f);
                }
            }
        }
    }
    else{
        return;
    }
}
Node* leave=NULL;
Node* insert(Node*&root,int num){
    if(root==NULL){       
        Node *node=new Node();
        node->num=num;
        node->br=red;
        if(node->length==0){
            // root必须为black
            node->length=1;
            node->br=black;
        }
        root=node;
        leave=root;
        return node;
    }
    else if(root->num>num){
        root->l=insert(root->l,num);
        root->l->f=root;      
    }
    else{
        root->r=insert(root->r,num);
        root->r->f=root;      
    }
    return root;
}
// 打印看看结构
void print(Node*root){
    if(root==NULL){
        return;
    }
    cout<<root->num<<"  color: "<<(root->br==black?"black":"red")<<endl;
    print(root->l);
    print(root->r);
}
int main(){
  int i,j,input,k;
  int p,e;
  Node*root=NULL;
  freopen("inputs.txt","r+",stdin);
  cin>>p;
  for(i=0;i<p;i++){
      cin>>e;
      insert(root,e);
      balance(leave);
      root->length++; 
  }
  cout<<"preorder :\n";
  print(root);
}

/*
7
5 7 1 4 6 3 2

5  color: black
3  color: red
1  color: black
2  color: red
4  color: black
7  color: black
6  color: red

6 7 0 4 5 2 1

6  color: black
4  color: red
1  color: black
0  color: red
2  color: red
5  color: black
7  color: black

*/

树的删除：（警惕黑）

在红黑树中，删除一个节点往大的说，只有以下四种情况。

情况一：删除的节点的左、右子树都非空；

情况二：删除的节点的左子树为空树，右子树非空；

情况三：删除的节点的右子树为空树，左子树非空；

情况四：删除的节点的左、右子树都为空树；

其中情况一，可以按与其他二叉搜索树的删除方式一样处理，最终可以转换到后面的三种情况。具体为：找到(Old)D节点的直接后继节点(暂且称为X节点)，然后将X的值转移到D节点，最后将X节点作为真正要被删除掉的节点(即：(Real)D节点)。这样删除操作后，可以保证该树仍然为一棵二叉搜索树。但这样删除(Real)D节点后，可能会破坏红黑树的性质。所以需要额外做一些调整处理，这便是下面将要详细讨论的内容。

说明：下文中所提到的D，除非有特别说明，否则都将指的是(Real)D（一般可以认为该RealD节点的左子树为空，OldD不一定），最终要删除的节点一般是OldD的右节点或者右节点的最前面的一个左节点，当然也可能无右节点只能删自己。

upload successful

删除的类别可以分为几种：

（1）首先 ，从当前点D和DR之间的颜色顺序看。

< 1 > 红->黑/NULL ，P肯定为黑 ， 直接删掉红，用黑（NULL）替换。

upload successful

< 2 > 黑->红 ，直接拿红替换黑，然后红变黑。

upload successful

< 3 > 黑->黑 / NULL ， 情况变得复杂。

（2）然后 ，根据uncle的颜色再分一次情况讨论：

< 1 > 如果uncle是红，那就很容易了。因为P不可能是红只能是黑，只有一种情况。

upload successful

upload successful

< 2 > uncle为黑时，特别复杂。

  • 1.SL=红，uncle=黑，P=黑/红，SR=黑/红

将S右旋转时，接着将SL改为P的颜色，P的颜色改为黑色(用这个黑色来填补DR分支的黑节点数)，将P左旋转。

upload successful

  • 2.SR=红，P=黑/红，SL=黑/红

upload successful

  • 3.S=黑，P=红，SL=SR=黑（处理简单，只要变色）

upload successful

  • 4.SR=SL=黑，P=黑（处理简单，只要变色）

upload successful

kd树

kd树：

计算时采用线性扫描的方式O(n^2)，效率奇低。采用平衡二叉树的方法存储各个点，用中位数做分割，划分左右区间，并进行以x-y轴为中心进行交替选择。

（2，4.5）

（2.1，3.1）

算法复杂度：

构建：O(log2n)
插入：O(log n)
删除：O(log n)
查询：平均情况下 O(log n) ，最好情况 O(1)，最坏情况O(n)

  1. 构建kd树：

（1）按y排序，抽取其中的中位数（向上取整）对应的点，axis代表的维自增。每个node保留一个指针指向父节点。

  • 怎么确定split域的首先该取的值（先划分x轴还是y轴）？

分别计算x，y方向上数据的方差得知x方向上的方差最大

  1. 搜寻确定查询点最小范围的点：

（1）先以y分割判断点A>Sy，向左子树查。
（2）再以x分割判断B<Sy，向右子树搜索。

  1. while查找二维空间里的最近点。

如果点非空而且栈非空（在根节点退到root->f即空节点而且栈为空（叶节点情况下一般栈非空））退出。
（1）如果 minr < r(当前点，搜索点)，则无需查找另外一侧的子节点。r=r->f
（2）如果minr > r(当前点，搜索点)，则去另一侧的子节点找找看。r=r->l/r（看你搜索点在线的哪一侧（根据x/y相对大小），取反方向即可），同时，stack记录r。
（3）当r==NULL，触底回退到stack为空（保留stack[0]），然后r=r->f（会不会重新陷回r->l/r ？不会左边的minr可能值都遍历了，所以会使r指向另一侧，等栈pop回到原点时又毫不留情r=r->f）

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int splits=0;
// 维数
int now_axis=0;
// 当前所在维数
class kd_tree{
    public:
    vector<float>point;
    // (x,y,z...)
    float range;
    // x<range and x>range
    int split;
    // x,y,z....轴标记
    kd_tree*l;
    kd_tree*r;
    kd_tree*f;
    kd_tree(){
        l=NULL;
        r=NULL;
        f=NULL;
        range=0;
        split=0;
    }
};
kd_tree* insert(kd_tree*root,vector<float>v,int split){
    if(root==NULL){
        root=new kd_tree();
        root->point.assign(v.begin(),v.end());
        root->split=split;
        root->range=v[split];
        root->point.assign(v.begin(),v.end());
    }
    else{
        if(v[root->split]>root->range){
            root->r=insert(root->r,v,split);
            root->r->f=root;
        }
        else if(v[root->split]<root->range){
            root->l=insert(root->l,v,split);
            root->l->f=root;
        }
    }
    return root;
}
// 排序用
bool cmp(vector<float>a,vector<float>b){
    return a[now_axis]<b[now_axis];
}
// 初始化必须集齐所有数据
void init(kd_tree*&root,vector<vector<float>>v,int left,int right,int split){
    if(left>right){
        return;
    }
    now_axis=split%splits;
    
    sort(v.begin()+left,v.begin()+right+1,cmp);

    int middle=(left+right+1)/2;
    // +1是向上取整，不加是向下取整
    root=insert(root,v[middle],now_axis);
    init(root,v,left,middle-1,split+1);
    init(root,v,middle+1,right,split+1);
    return;
}
int choose_split(vector<vector<float>>v){
    int i,j;
    vector<float>ave(splits);
    for(i=0;i<splits;i++){
        float sum=0;
        for(j=0;j<v.size();j++){
            sum+=v[j][i];
        }
        ave[i]=sum/float(v.size());
    }
    int ans=0;
    float maxd=0;
    for(i=0;i<splits;i++){
        float sumd=0;
        for(j=0;j<v.size();j++){
            sumd+=(v[j][i]-ave[i])*(v[j][i]-ave[i]);
        }
        if(sumd>maxd){
            ans=i;
            maxd=sumd;
        }
    }
    return ans;
}
kd_tree* find_range(kd_tree*root,vector<float>&v){
    if(root->point[root->split]>v[root->split]){
        if(root->l==NULL){
            return root;
        }
        else{
            find_range(root->l,v);
        }
    }
    else if(root->point[root->split]<v[root->split]){
        if(root->r==NULL){
            return root;
        }
        else{
            find_range(root->r,v);
        }
    }
    else{
        return root;
    }
}
void preorder(kd_tree*root){
    if(root==NULL){
        return;
    }
    cout<<root->point[0]<<","<<root->point[1]<<endl;
    cout<<(root->split==0?"x":"y")<<":"<<root->range<<endl;
    preorder(root->l);
    preorder(root->r);
}
// 最小半径的平方
float minr=0x7fffffff;
kd_tree* find_nearest_node(kd_tree*root,vector<float>&v){
    if(root==NULL){
        return NULL;
    }
    kd_tree*ans=root;
    vector<kd_tree*>list;
    while(!(root==NULL)||!list.empty()){
        // if(root){
        //     打印路径
        //     cout<<root->point[0]<<" "<<root->point[1]<<endl;
        // }
        if(root==NULL){                
            root=list[0];
            while(!list.empty()){
                list.pop_back();
            }
            root=root->f;
        }
        else{
            int i=0;
            float r_now=0;
            // calc the distance^2

            for(i=0;i<splits;i++){
                r_now+=(root->point[i]-v[i])*(root->point[i]-v[i]);
            }
            if(r_now<minr){
                // current point is much more near
                minr=r_now;
                ans=root;
            }
            if((root->point[root->split]-v[root->split])*(root->point[root->split]-v[root->split])>=minr){
                // if the cirle which based on the radius between current point and the point to be searched
                // doesn't intersect with the straight line(x=...,y=...), then search the father side; 
                root=root->f;
                if(!list.empty()){
                    list.pop_back();
                }
            }
            else{
                list.push_back(root);
                // or turn to the other side of 
                if(v[root->split]<root->point[root->split]){
                    root=root->r;
                }
                else{
                    root=root->l;
                }
            }
        }
    }
    return ans;
}
int main()
{
    freopen("inputs.txt","r+",stdin);
    int length;
    int i,j,x;
    vector<vector<float>>v;
    kd_tree* root=NULL;
    cin>>length;
    cin>>splits;
    for(i=0;i<length;i++){
        vector<float>vv;
        for(j=0;j<splits;j++){
            cin>>x;
            vv.push_back(x);
        }
        v.push_back(vv);
    }
    int left=0,right=v.size()-1,split;

    split=choose_split(v);
    // choose the largest D(..) to define x/y/z as the start axis.

    init(root,v,left,right,split);
    // init the b-tree.

    if(root==NULL){
        cout<<"failed"<<endl;
    }
    vector<float>vvv={2,4.5};
    // point to be search.

    kd_tree*r=find_range(root,vvv);
    // return the range define node.
    
    r=find_nearest_node(r,vvv);
    // return the answer node

    cout<<(split==0?"x":"y")<<" as the firat axis."<<endl;
    cout<<"\nr^2: "<<minr<<endl;
    cout<<"\nanswer node: ("<<r->point[0]<<","<<r->point[1]<<")"<<endl;

    return 0;
}

/*

6
2
2 3
4 7
5 4
7 2
8 1
9 6

(5,4)
*/
Machine Learning

感知机

感知机是二分类的线性模型，其输入是实例的特征向量，输出的是事例的类别，分别是+1和-1，属于判别模型。假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面。如果是非线性可分的数据，则最后无法获得超平面

分类效果

点到线的距离公式：

$d=\frac{Ax_0+By_0+C}{\sqrt{A^2+B^2}}$

假设有一超平面，h=w*x+b，其中w=（w0，w1…wm），x=（x0，x1…xm），样本x’到超平面的距离为：

$d=\frac{w*x’+b}{||w||}$

输出的模型如下：

$f(x)=sign(w*x+b)$

$sign(x)=\begin{cases} 1 \quad\quad\quad x>0
-1 \quad\quad\quad x\leq0\end{cases}$

如果 $ \frac{w\star x’+b}{||w||}>0 $，则y=1。如果<0，则y=-1。这样分类正确的话 $y*\frac{w\star x’+b}{||w||}>0$ 恒成立（||w||是L2范数）

损失函数：

$L(w,b)=-\frac{1}{||w||}\sum_{x_i \in M}y_i(w*x_i+b)$（M集合是误分类点的集合）

当然因为||$w$||>0所以我们可以去掉它

$L(w,b)=-\sum_{x_i \in M}y_i(w*x_i+b)$

感知机分类的最终目的是让最终值=0，所以少除也无所谓，还能降低计算量。(所以有个前提：能收敛到0)

随机梯度下降算法

用普通的基于所有样本的梯度和的均值的批量梯度下降法（BGD）是行不通的，原因在于我们的损失函数里面有限定，只有误分类的M集合里面的样本才能参与损失函数的优化。所以我们不能用最普通的批量梯度下降,只能采用随机梯度下降（SGD）

$\nabla_wL(w,b)=-\sum_{x_i \in M}y_i*x_i$

$\nabla_bL(w,b)=-\sum_{x_i \in M}y_i$

$w \gets w+\etay_ix_i$

$b \gets b+\eta*y_i$

  • xi实际上是(x,y)，yi实际上是{-1，1}，$\eta$是步长。

计算过程：

  1. 获取{-1，1}对应的点，初始化w矩阵和b变量的值。
  2. 正确分类的不用管，不正确分类的利用梯度对w和b的值进行更新。
  3. 循环带入所有的点，直到满足要求。
例：点x1=（3，3），w0=0，b0=0，y1=1，步长为1

1. y1*（w0*x1+b0）=0，分类错误。

2. w1=w0+y1*x1=(3，3)^T，b1=b0+y1=1

3. 得到线性模型 f（x）=sign（3x+3y+1）(只输出在线的哪一侧)

线性可分

线性不可分

对偶形式算法：

对偶形式的目的是降低运算量，但是并不是在任何情况下都能降低运算量，而是在特征空间的维度很高时才起到作用。

原：

$w \gets w+\etay_ix_i$

$b \gets b+\eta*y_i$

现：

初始值为（0，0）的w和b经过了n次修改后：（$a_i=n_i\eta$）

$w=\sum_{i=1}^na_iy_ix_i$

$b=\sum_{i=1}^na_iy_i$

$sign（wx+b）$，将$w=\sum_{i=1}^na_iy_ix_i$带入得$f(x)=\sum_{i=1}^na_iy_ix_ixj+b$

  • 第n-1次的参数$a_i$在第2(n-1)轮要再加$\eta$，所以参数$a_i$越大，说明该点位于分割线附近，在更新的时候容易受影响难以正确分类。$a_i$默认初始为0

$a_i \gets a_i+\eta$

$b \gets b+\eta y_i$

加速的设计：

gram矩阵，$G=[x_ix_j]_{NN}$

很可惜，因为不能解决异或问题躺尸了很多年。。。

new和malloc的区别

new与malloc的区别?

（1）申请的内存所在位置:
new操作符从自由存储区上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。

那么自由存储区是否能够是堆，这取决于operator new 的实现细节。自由存储区不仅可以是堆，还可以是静态存储区，这都看operator new在哪里为对象分配内存。

在C++中，内存区分为5个区，分别是堆、栈、自由存储区、全局/静态存储区、常量存储区，但是new其实是对malloc的封装，所以只是逻辑上有所区别….

（2）返回类型安全性：
new操作符内存分配成功时，返回的是对象类型的指针，无须进行类型转换，故new是符合类型安全性的操作符。而malloc内存分配成功则是返回void ，需要通过强制类型转换将void指针转换成我们需要的类型。

（3）是否调用构造函数/析构函数：
使用new操作符来分配对象内存时会经历三个步骤：
第一步：调用operator new 函数（对于数组是operator new[]）分配一块足够大的，原始的，未命名的内存空间以便存储特定类型的对象。
第二步：编译器运行相应的构造函数以构造对象，并为其传入初值。
第三部：对象构造完成后，返回一个指向该对象的指针。

使用delete操作符来释放对象内存时会经历两个步骤：
第一步：调用对象的析构函数。
第二步：编译器调用operator delete(或operator delete[])函数释放内存空间。

C++操作系统底层

内存垃圾管理（智能指针）

智能指针：
https://blog.csdn.net/u012501459/article/details/48229399

C++11中引入了智能指针的概念。使用普通指针，容易造成堆内存泄露（忘记释放），二次释放，使用智能指针能更好的管理堆内存。

  • 构造函数中创建类的新对象时，初始化引用计数为1；
  • 拷贝构造函数复制指针，并使相应的引用计数增加1；
  • 赋值操作减少左操作数所值对象的引用计数，增加右操作数所指对象的引用计数；
  • 析构函数使引用计数减少1，并且当引用计数为0时，释放指针说指向的对象；

upload successful

Ref_ptr类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//使用int*指针初始化ptr，注意必须要放在初始化列表中
Ref_ptr(int * i):ptr(new Referenced(i))
{

}
//拷贝构造函数，又有一个变量指向了这块内存
Ref_ptr(const Ref_ptr & rhs)
{
    ptr=rhs.ptr;//将右操作数的引用计数对象赋值给左操作数
    ptr->ref();//将它们的应用计数加1
}

Ref_ptr r1=new int(4); //调用构造函数
Ref_ptr r2=r1; //调用拷贝构造函数

upload successful

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//赋值操作符，右操作数的引用计数要减1，左操作数的引用计数要加1
Ref_ptr & operator=(const Ref_ptr & rhs)
{
    if(&rhs==this)
        return *this;
    if(ptr->unref()==0)//赋值操作符，首先将当前类的引用计数减1，因为现在指向它的指针少了一个。
    {
        cout<<"delete Ref_ptr"<<endl;
        delete ptr;
    }
    ptr=rhs.ptr; //将右操作数的引用计数赋值给当前对象
    ptr->ref(); //引用计数加1
    return *this;
}

//析构函数，引用计数要减1，如果减为0，删除这块内存
~Ref_ptr()
{
    if(ptr->unref()==0)
    {
        cout<<"delete Ref_ptr"<<endl;
        delete ptr;
    }
}

Referenced类：

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
//初始化这个类，引用计数设为1，并且将p指向传入的地址
Referenced(int * pi)
{
    refCount=1;
    p=pi;
}

//引用计数加1
int ref()
{
    return ++refCount;
}	

//引用计数减1
int unref()
{
    return --refCount;
}

//析构函数，释放掉内存
~Referenced()
{
    cout<<"delete referenced"<<endl;
    delete p;
}

好处：

  • 智能指针能够帮助我们处理资源泄露问题；
  • 它也能够帮我们处理空悬指针的问题；
  • 它还能够帮我们处理比较隐晦的由异常造成的资源泄露。
C++

STL里的四种智能指针auto_ptr,scoped_ptr,shared_ptr,weak_ptr

基于安全考虑：

1
2
3
auto_ptr< string> ps (new string ("I reigned lonely as a cloud.”）;
auto_ptr<string> vocation; 
vocaticn = ps;

因为程序将试图删除同一个对象两次，要避免这种问题，方法有多种：

（1）定义赋值运算符，使之执行深复制。这样两个指针将指向不同的对象，其中的一个对象是另一个对象的副本，缺点是浪费空间，所以智能指针都未采用此方案。

（2）建立所有权概念。对于特定的对象，只能有一个智能指针可拥有，这样只有拥有对象的智能指针的析构函数会删除该对象。然后让赋值操作转让所有权。这就是用于auto_ptr和unique_ptr 的策略，但unique_ptr的策略更严格。

（3）创建智能更高的指针，跟踪引用特定对象的智能指针数。这称为引用计数。例如，赋值时，计数将加1，而指针过期时，计数将减1,。当减为0时才调用delete。这是shared_ptr采用的策略。

1. unique_ptr：

unique_ptr由C++11引入，旨在替代不安全的auto_ptr。
unique_ptr不共享它的所管理的对象。它无法复制到其他unique_ptr，无法通过值传递到函数，也无法用于需要副本的任何标准模板库 （STL）算法。只能移动 unique_ptr，即对资源管理权限可以实现转移。

upload successful

1
2
3
4
5
6
7
8
9
10
11
12
//智能指针的创建  
unique_ptr<int> u_i; //创建空智能指针
u_i.reset(new int(3)); //"绑定”动态对象  
unique_ptr<int> u_i2(new int(4));//创建时指定动态对象
unique_ptr<T,D> u(d);	//创建空unique_ptr,执行类型为T的对象，用类型为D的对象d来替代默认的删除器delete

//所有权的变化  
int *p_i = u_i2.release(); //释放所有权  
unique_ptr<string> u_s(new string("abc"));  
unique_ptr<string> u_s2 = std::move(u_s); //所有权转移(通过移动语义)，u_s所有权转移后，变成“空指针” 
u_s2.reset(u_s.release());//所有权转移
u_s2=nullptr;//显式销毁所指对象，同时智能指针变为空指针。与u_s2.reset()等价

2.auto_ptr：为什么不用它而用unique_ptr

使用unique_ptr时编译出错，与auto_ptr一样，unique_ptr也采用所有权模型，但在使用unique_ptr时，程序不会等到运行阶段崩溃，而在编译期因下述代码行出现错误。一句话总结就是：避免因潜在的内存问题导致程序崩溃。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
	auto_ptr<string> films[5] ={
	auto_ptr<string> (new string("Fowl Balls")),
	auto_ptr<string> (new string("Duck Walks")),
	auto_ptr<string> (new string("Chicken Runs")),
	auto_ptr<string> (new string("Turkey Errors"))
	};
    auto_ptr<string> pwin;
    pwin = films[2]; 
    // films[2] loses ownership. 将所有权从films[2]转让给pwin，此时films[2]不再引用该字符串从而变成空指针

	for(int i = 0; i < 4; ++i)
	{
		cout << *films[i] << endl;
	}
	return 0;
}

从上面可见，unique_ptr比auto_ptr更加安全，因为auto_ptr有拷贝语义，拷贝后原象变得无效，再次访问原对象时会导致程序崩溃；unique_ptr则禁止了拷贝语义，但提供了移动语义，即可以使用std::move()进行控制权限的转移

1
2
3
4
5
6
7
8
unique_ptr<string> upt(new string("lvlv"));
unique_ptr<string> upt1(upt);	//编译出错，已禁止拷贝
unique_ptr<string> upt1=upt;	//编译出错，已禁止拷贝
unique_ptr<string> upt1=std::move(upt);  //控制权限转移，正确的写法

auto_ptr<string> apt(new string("lvlv"));
auto_ptr<string> apt1(apt);	//编译通过
auto_ptr<string> apt1=apt;	//编译通过

  • 使用shared_ptr时运行正常，因为shared_ptr采用引用计数，pwin和films[2]都指向同一块内存，在释放空间时因为事先要判断引用计数值的大小因此不会出现多次删除一个对象的错误。

3. shared_ptr

参看内存垃圾管理（智能指针）

4. weak_ptr

被设计为与shared_ptr共同工作，可以从一个shared_ptr或者另一个weak_ptr对象构造而来。

循环引用：

一般来讲，解除这种循环引用有下面三种可行的方法：
（1）当只剩下最后一个引用的时候需要手动打破循环引用释放对象。
（2）当parent的生存期超过children的生存期的时候，children改为使用一个普通指针指向parent。
（3）使用弱引用的智能指针打破这种循环引用。
虽然这三种方法都可行，但方法1和方法2都需要程序员手动控制，麻烦且容易出错。这里主要介绍一下第三种方法，使用弱引用的智能指针std:weak_ptr来打破循环引用。

C++STL

__cdecl,__stdcall,__fastcall,__pascal,__thiscall 的区别

关于函数的调用规则（调用约定），大多数时候是不需要了解的，但是如果需要跨语言的编程，比如VC写的dll要delphi调用，则需要了解。

1.__cdecl

__cdecl 是 C Declaration 的缩写，表示 C 语言默认的函数调用方法：所有参数从右到左依次入栈，这些参数由调用者清除，称为手动清栈。被调用函数不会要求调用者传递多少参数，调用者传递过多或者过少的参数，甚至完全不同的参数都不会产生编译阶段的错误。

2.__stdcall

__stdcall 是 Standard Call 的缩写，是 C++ 的标准调用方式：所有参数从右到左依次入栈，如果是调用类成员的话，最后一个入栈的是 this 指针。这些堆栈中的参数由被调用的函数在返回后清除，使用的指令是 retnX，X 表示参数占用的字节数，CPU 在 ret 之后自动弹出 X 个字节的堆栈空间，称为自动清栈。函数在编译的时候就必须确定参数个数，并且调用者必须严格的控制参数的生成，不能多，不能少，否则返回后会出错。

3.__fastcall

fastcall 是编译器指定的快速调用方式。由于大多数的函数参数个数很少，使用堆栈传递比较费时。因此 fastcall 通常规定将前两个（或若干个）参数由寄存器传递，其余参数还是通过堆栈传递。不同编译器编译的程序规定的寄存器不同，返回方式和 __stdcall 相当。

4.__pascal

pascal 是 Pascal 语言（Delphi）的函数调用方式，也可以在 C/C++ 中使用，参数压栈顺序与前两者相反。返回时的清栈方式与 stdcall 相同。

5.__thiscall

thiscall 是为了解决类成员调用中 this 指针传递而规定的。thiscall 要求把 this 指针放在特定寄存器中，该寄存器由编译器决定。VC 使用 ecx，Borland 的 C++ 编译器使用 eax。返回方式和 __stdcall 相当。

C++

大小端存储

大端模式，是指数据的高字节保存在内存的低地址中。

upload successful
4个两位16进制数=8*4=32位=4B=1int

编程判断大小端的两种方法：

  1. union 判断法

在union中所有的数据成员共用一个空间，同一时间只能储存其中一个数据成员，所有的数据成员具有相同的起始地址。即上述的union虽然定义了两个成员，但其实这个union只占用了4个字节(32位机器中)，往a成员赋值，然后读取b就相读取a成员的低位第一个字节的值。如果机器使用大端模式，则u.a=1那a的最高字节值为1；

1
2
3
4
5
6
7
8
9
10
11
typedef union {
	int i;
	char c;
}my_union;
 
int checkSystem1(void)
{
	my_union u;
	u.i = 1;
	return (u.i == u.c);
}

  1. 直接判断法
1
2
3
4
5
6
int checkSystem2(void)
{
	int i = 0x12345678;
	char *c = (char*)&i;
	return ((c[0] == 0x78) && (c[1] == 0x56) && (c[2] == 0x34) && (c[3] == 0x12));
}
C++操作系统底层
| 本站总访问量次 ,本文总阅读量次