Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <assert.h>
- #include <vector>
- #include <unordered_set>
- #include <ctime>
- #include <set>
- #include <limits>
- #include <random>
- #include <iomanip>
- using std::vector;
- using std::set;
- const int inf = std::numeric_limits<int>::max();
- const double lowest=std:: numeric_limits<double> :: min();
- struct IGraph {
- virtual ~IGraph() {}
- virtual void AddEdge(int from, int to, double lenght) = 0;
- virtual int VerticesCount() const = 0;
- virtual void GetNextVertices(int v, std::vector<std::pair<int, double >> &next) const = 0;
- virtual void GetPrevVertices(int v, std::vector<std::pair<int, double >> &prev) const = 0;
- virtual double getweight(int from, int to) const {}
- };
- class MatrixGraph : public IGraph {
- public:
- explicit MatrixGraph(int count);
- MatrixGraph(const IGraph &graph) {};
- virtual ~MatrixGraph() {};
- // Добавление ребра от from к to.
- virtual void AddEdge(int from, int to, double length);
- virtual int VerticesCount() const;
- virtual void GetNextVertices(int vertex, std::vector<std::pair<int, double>> &next) const;
- virtual void GetPrevVertices(int vertex, std::vector<std::pair<int, double >> &prev) const {};
- double getweight(int from, int to) const;
- private:
- int Vertices_number;
- std::vector<std::vector<double>> matrix;
- };
- MatrixGraph::MatrixGraph(int count) : Vertices_number(count), matrix(count, std::vector<double>(count, 0.0)) {}
- void MatrixGraph::AddEdge(int from, int to, double length) {
- matrix[from][to] = length;
- matrix[to][from] = length;
- }
- int MatrixGraph::VerticesCount() const { return Vertices_number; }
- void MatrixGraph::GetNextVertices(int vertex, std::vector<std::pair<int, double>> &next) const {
- for (int i = 0; i < Vertices_number; ++i) {
- if (matrix[vertex][i] != 0) {
- next.push_back(std::make_pair(i, matrix[vertex][i]));
- }
- }
- }
- double MatrixGraph::getweight(int from, int to) const { return matrix[from][to]; }
- void MST(const IGraph &graph, IGraph &result) {
- vector<std::pair<int, double>> key(graph.VerticesCount(), std::pair<int, double>(inf, -1));
- vector<bool> visited(graph.VerticesCount(), false);
- set<std::pair<double, int>> queue;
- key[0].second = 0;
- for (int i = 0; i < graph.VerticesCount(); i++)
- queue.emplace(std::pair<double, int>(key[i].second, i));
- while (!queue.empty()) {
- int v = queue.begin()->second;
- queue.erase(queue.begin());
- visited[v] = true;
- vector<std::pair<int, double>> related;
- graph.GetNextVertices(v, related);
- for (const std::pair<int, double> &u : related) {
- if ((!visited[u.first] and key[u.first].second > u.second)
- or key[u.first].second + 1 < lowest) {
- // Decreasing key
- queue.erase(std::pair<double, int>(key[u.first].second, u.first));
- key[u.first].first = v;
- key[u.first].second = u.second;
- queue.emplace(key[u.first].second, u.first);
- }
- }
- }
- for (unsigned i = 1; i < graph.VerticesCount(); i++)
- result.AddEdge(i, key[i].first, key[i].second);
- }
- void DFS(const IGraph &Graph, int dot, std::vector<int> &tour, std::vector<bool> &visited) {
- std::vector<std::pair<int, double>> vertices;
- Graph.GetNextVertices(dot, vertices);
- for (auto c: vertices) {
- if (!visited[c.first]) {
- visited[c.first] = true;
- tour.push_back(c.first);
- DFS(Graph, c.first, tour, visited);
- }
- }
- }
- void finding_min_matching( IGraph&MST, const IGraph&graph){std:: vector< int> nechet;
- for (int i=0;i<MST.degrees.size();++i){if (MST.degrees[i]%2==1){nechet.push_back(i);}}
- double sum=0;
- for (int i=0;i+1<nechet.size();i+=2){
- sum+=graph.getweight(nechet[i],nechet[i+1]);
- }
- double min_sum=sum;
- std :: vector<int> permutation=nechet;
- while (std :: next_permutation(nechet.begin(),nechet.end())){
- double sum1=0;
- for (int i=0;i+1<nechet.size();i+=2){
- sum1+=graph.getweight(nechet[i],nechet[i+1]);
- }
- if (sum1<min_sum){min_sum=sum1;for(int k=0;k<nechet.size();++k){permutation[k]=nechet[k];}}
- }
- for (int i=0;i+1<nechet.size();i+=2){
- MST.AddEdge(nechet[i],nechet[i+1],graph.getweight(nechet[i],nechet[i+1]));
- }}
- double mintourLenMst(const IGraph &Graph) {
- std::vector<int> tour;
- MatrixGraph mst(Graph.VerticesCount());
- MST(Graph, mst);
- std::vector<bool> visited(Graph.VerticesCount(), false);
- visited[0] = true;
- DFS(mst, 0, tour, visited);
- finding_min_matching( mst, Graph);
- double Tour = Graph.getweight(tour[Graph.VerticesCount() - 2], 0) + Graph.getweight(0, tour[0]);
- for (int i = 1; i < Graph.VerticesCount() - 1; i++) { Tour += Graph.getweight(tour[i - 1], tour[i]); }
- return Tour;
- }
- double getTourLen(const IGraph &graph, std::vector<int> &tour) {
- double tour_weight = graph.getweight(tour[graph.VerticesCount() - 2], 0) + graph.getweight(tour[0], 0);
- for (int i = 1; i < graph.VerticesCount() - 1; ++i) {
- tour_weight += graph.getweight(tour[i - 1], tour[i]);
- }
- return tour_weight;
- }
- void getting_all_permitations(int depth, std::vector<int> &tour, const IGraph &Graph, double &min_tour) {
- if (depth == tour.size()) {
- double tour1 = getTourLen(Graph, tour);
- if (tour1 < min_tour) { min_tour = tour1; }
- return;
- }
- for (int i = 0; i <= depth; ++i) {
- std::swap(tour[i], tour[depth]);
- getting_all_permitations(depth + 1, tour, Graph, min_tour);
- std::swap(tour[i], tour[depth]);
- }
- }
- double Min_tour_len(const IGraph &graph) {
- if (graph.VerticesCount() <= 1) {
- return 0;
- }
- std::vector<int> tour;
- for (int i = 1; i < graph.VerticesCount(); ++i) {
- tour.push_back(i);
- }
- double min_tour = getTourLen(graph, tour);
- getting_all_permitations(1, tour, graph, min_tour);
- return min_tour;
- }
- int main() {
- std::cout << "Average_quality" << " " << "Deviation" << std::endl;
- int times = 100;
- double avg_quality = 0;
- std::vector<double> qualities;
- for (int number_of_vertices = 2; number_of_vertices < 11; number_of_vertices++) {
- for(int z=0;z<times;++z){
- std::random_device rd;
- std::mt19937 gen(rd());
- std::normal_distribution<double> d;
- std::vector<std::pair<double, double>> coordinates;
- std::vector<double> for_coords(2 * number_of_vertices);
- for (int i = 0; i < number_of_vertices; ++i) {
- double x_coord;
- x_coord = d(gen);
- for_coords[i * 2] = x_coord;
- }
- for (int i = 0; i < number_of_vertices; ++i) {
- double y_coord;
- y_coord = d(gen);
- for_coords[i * 2 + 1] = y_coord;
- }
- for (int i = 0; i < number_of_vertices * 2; i += 2) {
- coordinates.emplace_back(std::make_pair(for_coords[i], for_coords[i + 1]));
- }
- MatrixGraph graph(number_of_vertices);
- for (int i = 0; i < number_of_vertices; ++i) {
- for (int j = i; j < number_of_vertices; ++j) {
- double distance = sqrt(
- (coordinates[i].first - coordinates[j].first) * (coordinates[i].first - coordinates[j].first)
- + (coordinates[i].second - coordinates[j].second) *
- (coordinates[i].second - coordinates[j].second));
- graph.AddEdge(i, j, distance);
- }
- }
- double ans1 = Min_tour_len(graph);
- double ans2 = mintourLenMst(graph);
- double quality = ans2 / ans1;
- avg_quality += quality;
- qualities.push_back(quality);
- }
- avg_quality = avg_quality / times;
- double sum = 0;
- for (int i = 0; i < times; ++i) {
- sum += ((qualities[i] - avg_quality) * (qualities[i] - avg_quality));
- }
- double deviation = sqrt(sum / (times - 1));
- std::cout << std::setprecision(10) << avg_quality << " " << deviation << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement