拓扑排序-判断是否为有向无环图

#include<queue>
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1000;
vector<int> g[maxn];
int n, m, indgree[maxn];
bool topsort() {
	int num = 0; //记录拓扑排序的顶点数
	queue<int> q;
	for (int i = 0; i < n; i++)
		if (indgree[i] == 0)
			q.push(i);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
//cout<<u<<endl;
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			indgree[v]--;
			if (indgree[v] == 0)
				q.push(v);
		}
		num++;
	}
	if (num == n) //为有向无环图
		return true;
	else
		return false;
}
int main() {
	cin >> n >> m; //点,边
	for (int i = 0; i < n; i++) //初始化,可以省略,一般自动初始化
			{
		indgree[i] = 0;
		g[i].clear();
	}
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		indgree[b]++;
		g[a].push_back(b);
	}
	if (topsort())
		cout << 1 << endl;
	else
		cout << 0 << endl;
	return 0;
}
/*
 input:
 3 2
 0 1
 1 2
 */
/*
 output:
 1
 */
/*
 input:
 2 2
 0 1
 1 0
 */
/*
 output:
 0
 */

 

0

邻接表的初始化

第一种:较常见

	cin>>n>>m;//点,边
	for(int i=0;i<n;i++)//初始化,可以省略,一般自动初始化
	{
		indgree[i]=0;
		g[i].clear();
	}
	int a,b;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		indgree[b]++;
		g[a].push_back(b);
	}

第二种:
    cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>num;   //每个表结点有几个边结点
		for(j=0;j<num;j++)
		{
			cin>>temp;
			adj[i].push_back(temp);
		}
	}

0

Dropout

一. 原理

dropout 是指在深度学习网络的训练过程中,按照一定的概率将一部分神经网络单元暂时从网络中丢弃,相当于从原始的网络中找到一个更瘦的网络

二. 流程

  1. 首先随机(临时)删掉网络中一半(p=0.5)的隐藏神经元,输入输出神经元保持不变;
  2. 然后把输入x通过修改后的网络前向传播,然后把得到的损失结果通过修改的网络反向传播。一小批训练样本执行完这个过程后就按照随机梯度下降法更新没有被删除的神经元对应的参数(w,b);
  3. 然后继续重复这一过程:
  • 恢复被删掉的神经元(此时 被删除的神经元 保持原样,而没有被删除的神经元已经有所更新)
  • 从隐藏神经元中随机选择一个一半大小的子集 临时删除掉(备份被删除神经元的参数)
  • 对一小批训练样本,先前向传播然后反向传播损失并根据随机梯度下降法更新参数(w,b) (没有被删除的那一部分参数得到更新,删除的神经元参数保持被删除前的结果)

三. 为何有效

  • bagging减少variance。整个dropout过程就相当于对很多个不同的神经网络取平均,相当于bagging减少variance
  • 减少神经元之间复杂的共适应关系。因为dropout程序导致两个神经元不一定每次都在一个dropout网络中出现。(这样权值的更新不再依赖于有固定关系的隐含节点的共同作用,阻止了某些特征仅仅在其它特定特征下才有效果的情况)。 迫使网络去学习更加鲁棒的特征 (这些特征在其它的神经元的随机子集中也存在)。

四. 实现: Vanilla Dropout 和 Inverted Dropout(目前主流框架都是后者)

Vanilla Dropout:以p的概率丢弃,那么训练阶段的期望为: (1-p)*x+p*0=(1-p)x , 为了保持训练阶段和预测阶段的分布一致,即期望一致,那么在预测阶段需要乘以(1-p)得到(1-p)*x

Inverted Dropout: 以p的概率丢弃,在训练阶段进行乘以1/(1-p)进行rescale,那么期望为[(1-p)*x+p*0]/(1-p)=(1-p)x/(1-p)=x, 那么在预测阶段就不用做任何操作。

#tensorflow dropout layer 源码
def call(self, inputs, training=None):
    if training is None:
      training = K.learning_phase()

    def dropped_inputs():
      return nn.dropout(
          inputs,
          noise_shape=self._get_noise_shape(inputs),
          seed=self.seed,
          rate=self.rate)
    # 如果training=True,那么返回rescale的dropped_inputs,否则直接返回inputs
    output = tf_utils.smart_cond(training,
                                 dropped_inputs,
                                 lambda: array_ops.identity(inputs))
    return output

五. 参考

0

DFS+BFS(邻接矩阵)

不写邻接表是因为感觉不会考到…因为手动输值建立邻接表是不唯一的,因此输出答案也不唯一,考试可以完美避开~
更正:不对,一般按照习惯,这类问题一般都是邻接矩阵,除非是拓扑排序;

#include<iostream>
#include<queue>
using namespace std;
const int maxn = 1000, INF = 1000000000;
int n, m, vis[maxn], g[maxn][maxn];
void dfs(int s, int depth) {
	vis[s] = 1;
	cout << s << endl;
	for (int i = 0; i < n; i++) {
		if (vis[i] == 0 && g[s][i] != INF)
			dfs(i, depth + 1);
	}
}
void bfs(int s) //两次vis和cout
		{
	queue<int> q;
	q.push(s);
	vis[s] = 1;
	cout << s << endl;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < n; i++) {
			if (vis[i] == 0 && g[u][i] != INF) {
				q.push(i);
				vis[i] = 1;
				cout << i << endl;
			}
		}
	}
}
int main() {
	int u, v;
	cin >> n >> m;
	fill(g[0], g[0] + maxn * maxn, INF);
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		g[u][v] = g[v][u] = 1;
	}
	int depth = 1;
	dfs(0, depth);
	fill(vis, vis + maxn, 0);
	bfs(0);
}
/*
 6 6
 0 1
 0 2
 0 3
 1 4
 1 5
 2 4
 */
/*
 0
 1
 4
 2
 5
 3
 0
 1
 2
 3
 4
 5
 */

 

0