Материал: Алгоритм, эвристически строящий оптимальный граф для задачи децентрализованного поиска

4х4 (стартовый граф - полный граф)

Можно заметить, что результаты алгоритма не отличаются не зависимо от стартового графа, поэтому можно предполагать, что мы нашли глобальный минимум. Рассмотрим результаты для графа 5х5.

5х5 (стартовый граф - граф-сетка)

5х5 (стартовый граф - полный граф)

В этом же примере можно заметить, что алгоритм может давать разные решения при разном начальном графе. Далее будут приведены оптимальный графы размером 6х6 и 7х7 по одному для каждой функции расстояний.

6х6

Рисунок 61 - L1, 0, 13356 c полного

Рисунок 62 - L2, 2, 13452 с полного

Рисунок 63 - LI, 0, 13882 и с полного и с сетки

7х7

Рисунок 64 - L1, 0, 28177 с полного

Рисунок 65 - L2, 0, 29095 с полного

Рисунок 66 - LI, 0, 29498 с полного

Для метода ветвей и границ на вход были поданы матрицы меньших размеров, так как этот алгоритм ищет точное оптимально решение и это занимает много времени. Тесты проводились на этом алгоритме, чтобы проверить корректность предположения, что среди всех оптимальных решений обязательно найдется хотя бы одно, которое содержит в себе только симметричные ребра.

Можно заметить, что для графов 2х3, 2х4 и 2х5 получившиеся оптимальные графы являются симметричными, однако для 1х11 уже возникает несимметричное решение. При этом симметричное все же присутствует. Однако не всегда так. Рассмотрим следующие результаты для 3х4.

Получившиеся решения не симметричны, однако для каждого несимметричного есть симметричное ему другое несимметричное решение. Таким образом гипотеза, что всегда есть симметричное решение не подтвердилась, поэтому нужно либо отказываться от симметричности и перебирать все ребра, либо находить такой способ, чтобы при жадный поиск строил симметричные пути.

Также табу алгоритм был запущен на графах с 1х4 до 1х42 и с 2х2 до 2х25, по результатам работы были построены графики зависимости сложности поиска от количества вершин. Результаты приведены на следующих рисунках.

Для того, чтобы понять какая зависимость представлена на графике, то построим зависимость сложности от квадрата логарифма количества вершин.

Можно заметить, что сложность поиска для таких графов будет .

Построим зависимость сложности от количества вершин для графов 2х2, 3х3, 4х4, 5х5, 6х6, 7х7, 8х8, 9х9.

Можно заметить, что тут также присутствует сложность поиска .

граф алгоритм локальный стартовый

Вывод

В результате работы был предложен алгоритм, который эвристически строит оптимальный граф для задачи децентрализованного поиска. Предполагалось, что алгоритм построит решения, на которых поиск будет работать быстрее, чем у Клайнберга, однако такого не произошло. Сложность поиска остается одинаковой. Также был предложен алгоритм, который находит точные решения для поставленной задачи на малых размерах. Предполагалось, что алгоритм подтвердит наличие оптимальных решений с только симметричными ребрами, однако алгоритм дал отрицательный результат. В будущем предполагается построить алгоритм, который будет строить оптимальный граф для поиска с возможностью ошибки, т.е. не находить иногда необходимую вершину (задача аппроксимированного поиска ближайшего соседа). Возможно на такой задаче сложность поиска удастся уменьшить.

Список литературы

1.      Milgram, Stanley. "The small world problem." Psychology today 2, no. 1 (1967): 60-67.

.        Maymounkov, Petar, and David Mazieres. "Kademlia: A peer-to-peer information system based on the xor metric." In Peer-to-Peer Systems, pp. 53-65. Springer Berlin Heidelberg, 2002.

.        Beaumont, Olivier, Anne-Marie Kermarrec, Loris Marchal, and Etienne Riviere. "VoroNet: A scalable object network based on Voronoi tessellations." In Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International, pp. 1-10. IEEE, 2007.

.        Kleinberg, Jon. "The small-world phenomenon: An algorithmic perspective." In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 163-170. ACM, 2000.

.        Watts, Duncan J., and Steven H. Strogatz. "Collective dynamics of ‘small-world’networks." nature 393, no. 6684 (1998): 440-442.

6.      Bollobás, Béla, and Oliver Riordan. "The diameter of a scale-free random graph." Combinatorica 24, no. 1 (2004): 5-34.

Приложение

#include "Graph.h"

#include <math.h>

#include <algorithm>

#include <fstream>

#include <iostream>

#include <sys/stat.h>

#include <random>TYPE;TYPE_V;::vector <Graph> bestest;counter;namespace std;::Graph(int n, int m, bool flag)

{>v = n*m;= new int*[v];= new int[v];= new bool[v];= new bool[v];(int i = 0; i < v; i++){[i] = new int[v];[i] = 0;[i] = false;[i] = false;

}(int i = 0; i < v; i++){(int j = 0; j < v; j++){[i][j] = 0;

}

}(i - 1 >= (i / n)*n){[i - 1][i] = 1;[i][i - 1] = 1;

}(i + n < v){[i + n][i] = 1;[i][i + n] = 1;

}(i - n >= 0){[i - n][i] = 1;[i][i - n] = 1;

}

}(flag == true){(int i = 0; i < v; i++){(int j = 0; j < v; j++){(i != j && arr[i][j] == 0)[i][j] = 2;

}

}

}

(int i = 0; i < v; i++){(int j = 0; j < v; j++){(arr[i][j] != 0)[i] += 1;

}

}>n = n;>m = m;

}::Graph(const Graph& g){= g.n;= g.m;= g.v;= new int*[v];= new int[v];= new bool[v];= new bool[v];(int i = 0; i < v; i++){[i] = new int[v];[i] = g.getDegree()[i];[i] = false;[i] = false;

}(int i = 0; i < v; i++){(int j = 0; j < v; j++){[i][j] = g.getArr()[i][j];

}

}(int i = 0; i < g.getStrict().size(); i++){.push_back(g.getStrict()[i]);

}= g.getO();

}::Graph(string nfile){file(nfile);a, b;>> a >> b;>n = a;>m = b;>v = a*b;>arr = new int*[v];>degree = new int[v];>inSearch = new bool[v];>inPath = new bool[v];(int i = 0; i < this->v; i++){>arr[i] = new int[v];>degree[i] = 0;>inSearch[i] = false;>inPath[i] = false;

}(int i = 0; i < this->v; i++){(int j = 0; j < this->v; j++){>> this->arr[i][j];

}

}(int i = 0; i < this->v; i++){(int j = 0; j < this->v; j++){>degree[i] += this->arr[i][j];

}

}

}Graph::addToStrict(Edge ed){.push_back(ed);

}Graph::canDoAction(int iAdd, int jAdd, int iDelete, int jDelete, double best) {a1 = (iAdd / n + 1)*n - 1 - iAdd%n;b1 = (jAdd / n + 1)*n - 1 - jAdd%n;a2 = n*m - 1 - iAdd;b2 = n*m - 1 - jAdd;a3 = (a2 / n + 1)*n - 1 - a2%n;b3 = (b2 / n + 1)*n - 1 - b2%n;ad1 = (iDelete / n + 1)*n - 1 - iDelete%n;bd1 = (jDelete / n + 1)*n - 1 - jDelete%n;ad2 = n*m - 1 - iDelete;bd2 = n*m - 1 - jDelete;ad3 = (a2 / n + 1)*n - 1 - a2%n;bd3 = (b2 / n + 1)*n - 1 - b2%n;oldO = O;flag = 0;(int index = 0; index < strict.size(); index++){(((iAdd == strict.at(index).start && jAdd == strict.at(index).finish) || (a1 == strict.at(index).start && b1 == strict.at(index).finish) || (a2 == strict.at(index).start && b2 == strict.at(index).finish) || (a3 == strict.at(index).start && b3 == strict.at(index).finish)) && strict.at(index).action == true){++;

}(((iDelete == strict.at(index).start && jDelete == strict.at(index).finish) || (ad1 == strict.at(index).start && bd1 == strict.at(index).finish) || (ad2 == strict.at(index).start && bd2 == strict.at(index).finish) || (ad3 == strict.at(index).start && bd3 == strict.at(index).finish)) && strict.at(index).action == false){++;

}

}(flag == 0){true;

}(iAdd != -1){>addSymEdges(iAdd, jAdd);

}(iDelete != -1){>deleteSymEdges(iDelete, jDelete);

}();(O < best){(iAdd != -1){>deleteSymEdges(iAdd, jAdd);

}(iDelete != -1){>addSymEdges(iDelete, jDelete);

}(oldO);true;

}(iAdd != -1){>deleteSymEdges(iAdd, jAdd);

}(iDelete != -1){>addSymEdges(iDelete, jDelete);

}(oldO);false;

}Graph::canDoActionInTabu(int iAdd, int jAdd, int iDelete, int jDelete) {a1 = (iAdd / n + 1)*n - 1 - iAdd%n;b1 = (jAdd / n + 1)*n - 1 - jAdd%n;a2 = n*m - 1 - iAdd;b2 = n*m - 1 - jAdd;a3 = (a2 / n + 1)*n - 1 - a2%n;b3 = (b2 / n + 1)*n - 1 - b2%n;ad1 = (iDelete / n + 1)*n - 1 - iDelete%n;bd1 = (jDelete / n + 1)*n - 1 - jDelete%n;ad2 = n*m - 1 - iDelete;bd2 = n*m - 1 - jDelete;ad3 = (a2 / n + 1)*n - 1 - a2%n;bd3 = (b2 / n + 1)*n - 1 - b2%n;oldO = O;flag = 0;(int index = 0; index < strict.size(); index++){(((iAdd == strict.at(index).start && jAdd == strict.at(index).finish) || (a1 == strict.at(index).start && b1 == strict.at(index).finish) || (a2 == strict.at(index).start && b2 == strict.at(index).finish) || (a3 == strict.at(index).start && b3 == strict.at(index).finish)) && strict.at(index).action == true){++;

}(((iDelete == strict.at(index).start && jDelete == strict.at(index).finish) || (ad1 == strict.at(index).start && bd1 == strict.at(index).finish) || (ad2 == strict.at(index).start && bd2 == strict.at(index).finish) || (ad3 == strict.at(index).start && bd3 == strict.at(index).finish)) && strict.at(index).action == false){++;

}

}(flag == 0){true;

}false;

}Graph::addSymEdges(int a, int b){count = 0;(a >= 0 && b >= 0 && a < v && b < v){(arr[a][b] == 0){[a][b] = 2;[b][a] = 2;[a]++;[b]++;++;a1 = (a / n + 1)*n - 1 - a%n;b1 = (b / n + 1)*n - 1 - b%n;(arr[a1][b1] == 0){[a1][b1] = 2;[b1][a1] = 2;[a1]++;[b1]++;++;

}a2 = n*m - 1 - a;b2 = n*m - 1 - b;(arr[a2][b2] == 0){[a2][b2] = 2;[b2][a2] = 2;[a2]++;[b2]++;++;

}a3 = (a2 / n + 1)*n - 1 - a2%n;b3 = (b2 / n + 1)*n - 1 - b2%n;(arr[a3][b3] == 0){[a3][b3] = 2;[b3][a3] = 2;[a3]++;[b3]++;++;

}count;

}

}0;

}Graph::deleteSymEdges(int a, int b){count = 0;(a >= 0 && b >= 0 && a < v && b < v){(arr[a][b] == 2){[a][b] = 0;[b][a] = 0;[a]--;[b]--;++;a1 = (a / n + 1)*n - 1 - a%n;b1 = (b / n + 1)*n - 1 - b%n;(arr[a1][b1] == 2){[a1][b1] = 0;[b1][a1] = 0;[a1]--;[b1]--;++;

}a2 = n*m - 1 - a;b2 = n*m - 1 - b;(arr[a2][b2] == 2){[a2][b2] = 0;[b2][a2] = 0;[a2]--;[b2]--;++;

}a3 = (a2 / n + 1)*n - 1 - a2%n;b3 = (b2 / n + 1)*n - 1 - b2%n;(arr[a3][b3] == 2){[a3][b3] = 0;[b3][a3] = 0;[a3]--;[b3]--;++;

}count;

}

}0;

}Graph::Distance(int a, int b){x_a = a%n;y_a = a / n;x_b = b%n;y_b = b / n;(TYPE == -1){d = max(abs(x_a - x_b), abs(y_a - y_b));d;

}{d = pow(abs(x_a - x_b), TYPE) + pow(abs(y_a - y_b), TYPE);pow(d, 1 / (double)TYPE);

}

}Graph::FindPath(int a, int b){[a] = true;(a == b){[a] = true;;

}[a] = true;t = 0;* paths = new double[degree[a]];* indexes = new int[degree[a]];(int i = 0; i < v; i++){(arr[a][i] > 0){[i] = true;[t] = Distance(i, b);[t] = i;++;(t == degree[a]);

}

}minI = 0;minV = paths[0];(int i = 1; i < degree[a]; i++){(paths[i] < minV && inPath[indexes[i]] == false){= paths[i];= i;

}{(TYPE_V){0:(paths[i] == minV && inPath[indexes[i]] == false){(degree[indexes[i]] < degree[indexes[minI]]){= paths[i];= i;

}

};1:(paths[i] == minV && inPath[indexes[i]] == false){(degree[indexes[i]] > degree[indexes[minI]]){= paths[i];= i;

}

};2:(paths[i] == minV && inPath[indexes[i]] == false){(rand()%2 == 0){= paths[i];= i;

}

};

}

}

}(indexes[minI], b);[] paths;[] indexes;;

}Graph::calculateO(){* sum = new int[v];(int i = 0; i < v; i++){[i] = 0;(int j = 0; j < v; j++){(int t = 0; t < v; t++){[t] = false;

}(i, j);count = 0;(int t = 0; t < v; t++){[i] += inSearch[t];+= inSearch[t];[t] = false;

}

//cout << "For v = " << i << " serch to " << j << " = " << count << endl;

}

}s = 0.0;(int i = 0; i < v; i++){

//cout<<"i = "<< i << " sum = " << sum[i] << endl;+= sum[i];

}[] sum;= s;s;

}Graph::calculateApproxO(){sum = 0.0;number = 20;t = 0;(number != t){i = rand()%v;j = rand()%v;(int t = 0; t < v; t++){[t] = false;

}(i, j);(int t = 0; t < v; t++){+= inSearch[t];[t] = false;

}++;

}= (sum/number)*(v*v);sum;

}Graph::setO(double O){>O = O;

}Graph::save(std::string dir, std::string name){::cout << "Start SAVE" << std::endl;file;

//dir = "/"+dir;

//std::cout << dir << endl;(dir.c_str(), 0777);// << endl;.open(dir + "/" + name);(int i = 0; i < v; i++){(int j = 0; j < v; j++){(arr[i][j] != -1)<< arr[i][j] << " ";<< 0 << " ";

}<< endl;

}.close();::cout << "Finish SAVE" << std::endl;

}& Graph::operator=(const Graph &g){(int i = 0; i < v; i++){[i] = g.getDegree()[i];[i] = false;

}(int i = 0; i < v; i++){(int j = 0; j < v; j++){[i][j] = g.getArr()[i][j];

}

}.clear();(int i = 0; i < g.getStrict().size(); i++){.push_back(g.getStrict()[i]);

}= g.getO();*this;

}Graph::CheckStrict(){(int i = 0; i < strict.size(); i++){[i].numberOfSteps--;

}(int i = strict.size() - 1; i >= 0; i--){(strict[i].numberOfSteps == 0){.erase(strict.begin() + i);

}

}

}Graph::RealTabuStep(int number_for_add, int number_for_delete){bestKnown(*this);fails = 0;flag = false;(number_for_add + number_for_delete > 0){();<Graph> graphs;** edges_add = new int*[number_for_add];** edges_delete = new int*[number_for_delete];(int i = 0; i < number_for_add; i++)_add[i] = new int[2];(int i = 0; i < number_for_delete; i++)_delete[i] = new int[2];c_add = 0;c_delete = 0;(int i = 0; i < v; i++){((i < (n*m / 2)) && (i <= (n/ 2 + i / n))){(int j = i + 1; j < v; j++){(arr[i][j] == 0){_add[c_add][0] = i;_add[c_add][1] = j;_add++;

}(arr[i][j] == 2){_delete[c_delete][0] = i;_delete[c_delete][1] = j;_delete++;