反馈点集问题

算是在 HUST-Smart 实验室的一次小实习。

背景介绍

有向反馈点集问题主要研究如何消除有向拓扑图中的环路问题。

题目描述

给定一个有向图，请删除最少数量的顶点使得图无环，请注意顶点的输入输出都从\(0\)开始编号。

输入包括\(n+1\)行，第\(1\)行为顶点数\(n\)以及边数\(m\)，接下来\(n\)行分别代表顶点\(0 \sim n-1\)的邻接表。

输出包括若干行，每一行为要删除的一个顶点的编号。

理论原理

在有向图中，反馈集由图中在圈上的点（包括圈和圈的交点）组成。反馈点集问题的内容是：如何消除尽可能少的点，使得一个有向图无环，换言之就是如何找到有向图的最小反馈点集。

In a directed graph, a feedback set is a set of vertices that intersects any cycle of the graph.

实现代码

#include <vector>
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <random>
#include <fstream>
#include <cstring>
#include <ctime>
#include <chrono>
#include <unordered_map>

#pragma warning(disable: 4996)

//#define OFFLINE
#define __TIMER__

using namespace std;
using namespace chrono;

struct Node {
	int nodeId;
	vector<int> pred; // 前驱节点
	vector<int> succ; // 后继节点
	Node(int id = -1) :nodeId(id), pred(vector<int>()), succ(vector<int>()) {}
};

void init() {

}

double rand_p() {
	return rand() / double(RAND_MAX);
}

vector<int> get_conflict_points(unordered_map<int, int>& S, pair<int, int> move, vector<Node>& graph) {
	if (move.first == -1) return {};
	vector<int> conflictPoints;
	for (auto su : graph[move.first].succ) {
		if ((move.first == su) || (S.count(su) && move.second >= S[su])) {
			conflictPoints.emplace_back(su);
		}
	}
	return conflictPoints;
}

//first为结点ID，second为插入位置
pair<int, int> rand_choice(unordered_map<int, int>& S, vector<Node>& graph) {
	int nodeID = -1, insertPos = 0;
	while (S.size() < graph.size() && -1 == nodeID) {
		int r = rand() % graph.size();
		if (S.find(r) == S.end()) nodeID = r;
	}
	if (nodeID != -1) {
		for (auto pr : graph[nodeID].pred) {
			if (S.count(pr)) {
				insertPos = max(insertPos, S[pr] + 1);
			}
		}
	}
	return { nodeID, insertPos };
}

void add_sol(unordered_map<int, int>& S, vector<Node>& graph, pair<int, int> move, vector<int>& conflictPoints) {
	if (move.first == -1) return;
	S.insert(move);
	//去除冲突点
	for (auto cp : conflictPoints) {
		S.erase(cp);
	}
	for (auto& it : S) {
		if (it.first != move.first && it.second >= move.second) {
			it.second++;
		}
	}
}

unordered_map<int, int> SA_FVSP(vector<Node>& graph, long long secTimeOut) {
	//初始化解
	unordered_map<int, int> S, S_star;
	//初始化模拟退火所需的参数
	double T = 0.6, alpha = 0.98;
	//int maxFail = 50, maxMvt = 5 * graph.size(), nbFail = 0;
	//可以适当修改参数，前40个算例没必要那么多轮迭代
	int maxFail = 25, maxMvt = 5 * graph.size(), nbFail = 0;
	//模拟退火算法主函数
#ifdef __TIMER__
	time_t start_t, end_t;
	auto start = system_clock::now();//运用c++ 11 auto
	auto end = system_clock::now();
	start_t = system_clock::to_time_t(start);//to_time_t函数：time_point转换成time_t秒(即ctime标准类型)
	long long duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
#endif
	do {
		int nbMvt = 0;
		bool failure = true;
		do {
			auto move = rand_choice(S, graph);
			auto conflictPoints = get_conflict_points(S, move, graph);
			int delta = conflictPoints.size() - 1;
			if (delta <= 0 || exp(-delta / T) > rand_p()) {
				add_sol(S, graph, move, conflictPoints);
				nbMvt++;
				if (S.size() > S_star.size()) {
					S_star = S;
					failure = false;
				}
			}
#ifdef __TIMER__
			end = system_clock::now();
			duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
			if (duration == secTimeOut) {
				cerr << "Time limit exceeded!" << endl;
				exit(-1);
			}
#endif
		} while (nbMvt != maxMvt);
		nbFail = (failure ? nbFail + 1 : 0);
		T *= alpha;
	} while (nbFail != maxFail);
	//返回最优解
	return S_star;
}

long long to_ll(const char* src) {
	int len = strlen(src);
	long long ans = 0;
	for (int i = 0; i < len; i++) {
		ans = ans * 10 + (src[i] - '0');
	}
	return ans;
}

int main(int argc, char* argv[]) {
	//快速I/O
#ifdef OFFLINE
	auto start = clock();
#endif
	cin.tie(0);
	cout.tie(0);
	cout.sync_with_stdio(false);
	//处理命令行参数
	long long secTimeout = 0;
	if (argc == 3) {
		secTimeout = atoll(argv[1]);
		srand(atoi(argv[2]));
	} else return 0;
	//读入数据
	int n, m;
#ifdef OFFLINE
	//const string targetFilePath("C:\\Users\\17258\\Desktop\\npbenchmark.data\\DFVSP\\Instance\\pardalos.n1000e30000.txt");
	const string targetFilePath("testData.txt");
	ifstream in(targetFilePath);
	in >> n >> m;
	in.get();
#else
	cin >> n >> m;
	cin.get();
#endif
	//读入有向图
	vector<Node> graph(n);
	for (int s = 0; s < n; s++) {
		graph[s].nodeId = s;
		string line;
#ifdef OFFLINE
		getline(in, line);
#else 
		getline(cin, line);
#endif
		stringstream ss(line);
		vector<int> cur;
		int e;
		while (ss >> e) {
			graph[e].pred.emplace_back(s);
			graph[s].succ.emplace_back(e);
		}
	}
	//求解
	auto sol = SA_FVSP(graph, secTimeout);
	//打印结果
	for (int i = 0; i < n; i++) {
		//打印删除的点
		if (0 == sol.count(i)) {
			cout << i << endl;
		}
	}
#ifdef OFFLINE
	auto end = clock();
	cout << double(end - start) / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}