Топологическая сортировка+Поиск кратчайшего пути

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

Граф, который не содержит циклов, называется ациклическим.

Ориентированные ациклические графы используются для указания последовательности действия, где каждое действие зависит от других. Например: установка программ с помощью системы управления пакетами или сборка с помощью Makefil'ов. (wikipedie (c))

Топологическая сортировка проводится с помощью поиска в глубину, которая описана в моем блоге: Поиск в глубину
Суть топологической сортировки можно связать с временем закрытия. Чем больше время закрытия, тем первее будет вершина графа в сортировке.
Пример отсортированного графа:

На рисунке представлена последовательность одевания утром. Первым делом идут носки (socks), потом трусы (undershorts) и самым последним идет пиджак у него время закрытия 4.

Для реализации топологической сортировки нам всего лишь нужно добавить в реализацию поиска в глубину глобальный стэк для вершин - stack<unsigned int> answer;
И! где мы красим вершину в черный после цикла, добавим добавление вершины в стек:

answer.push(u);

Теперь нам осталось всего лишь вывести стек) Вот и получили ответ.

Приложение: поиск кратчайшего пути в ациклическом графе.
Алгоритм выглядит так:

1. Сначала делаем топологическую сортировку графа
2. Для каждой вершины u в порядке топологической сортировки
1. Для каждой смежной вершине v к вершине u
1. Делаем релаксацию, т.е. запускаем старую добрую RELAX(u,v,w) 

Read More

Разложение Шеннона по таблице истинности

Мое разложение Шеннона получилось ну сильно неоптимальным, можно было легче сделать через манипуляции с таблицей истинности.
Разложение Шеннона-способ представление функции с помощью подфункций размером уже от (n-1) переменных.
Алгоритм (он у нас для n разбиений, все переменные для разбиения находятся в очереди):

1. Сначала мы берем СДНФ и разбиваем ее на конъюнкции
2. Эти конъюнкции уже разбиваем на те, которые относятся к первой переменной разбиения, которая равна в таблице истинности единице, и те которым соответсвует 0.
3. Запускаем процедуру декомпозиции

Сама идея процедуры очень проста, но реализовано все очень прожорливо, через вектора:

queue <int> variables - очередь, которая хранит в себе все переменные, которые мы выбрали для разбиения.

Мы разбиваем на конъюнкции , где xi=1 (plus) и xi=0 (minus) и смотрим 3 случая:

1. Все вектора конъюнкций не пусты
2. plus вектор пуст
3. minus вектор пуст

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

В общем на blogspote ограничение на 200 символов, так что по просьбе могу скинуть на хостинг проект.

Read More

Поиск в глубину у графа

Поиск в глубину - это метод прохода графа, когда просматривается еще не пройденная вершина, потом происходит проход по смежным вершинам, затем когда остаются не иследованные ребра, происходит возврат в вершину. Алгоритм работает до тех пор, пока не будут открытые все вершины, достижимые из исходной.
Сам алгоритм:
Он состоит из 2 ух процедур:

1. DFS(G) - нужна для инициализации всех переменных и цикла для прохода по всем вершинам
2. DFS_VISIT(u) - где u - вершина, которую нужно посетить. Эта процедура обработки вершина, где проиходит окраска каждой вершины, обозначения времени открытия и закрытия вершины (закрытие - окраска в черный цвет, открытие - окраска в серый цвет).

DFS(G)

Для каждой вершины u из множества вершин Графа

Окрасить в белый цвет

Инициализировать счетчик времени нулем
Для каждой вершины u из множества вершин Графа

Если вершина окрашена в белый, т.е. не пройдена

Посетить ее, т.е. запустить процедуру DFS_VISIT(u)

DFS_VISIT(u)

Окрасить вершину в серый цвет
Увеличить счетчик времени time++
Обозначить время открытия d[u]=time
Для каждой вершины v смежной нашей вершине u

Если вершина v окрашена в белый, т.е. не пройдена

Обозначить u как вершину предшествующую вершине v
Рекурсивно вызвать процедуру обработки для v: DFS_VISIT(v)


Окрасить вершину u в черный цвет
Обозначить время закрытия f[u]=time=time+1

Использующиеся данные:

Глобальная область видимости:

vector<unsigned int> color; //вектор цветов, 0 - белый, 1 - серый, 2 - черный

vector<unsigned int> predcessors; //вектор предшественников, если хотите построить дерево глубины

vector<unsigned int> d; //вектор к-ый хранит время открытия вершины

vector<unsigned int> f;  //вектор к-ый хранит время закрытия вершины

unsigned int timer; //таймер

ConnectionMatrix-матрица смежности графа

Реализация процедуры DFS:

void DFS (unsigned int NumOfVertices, double **ConnectionMatrix){

color.assign(NumOfVertices,0); //инициализация всех векторов

predcessors.resize(NumOfVertices);

d.resize(NumOfVertices);

f.resize(NumOfVertices);

timer=0; //обнуляем таймер

for (int u=0; u<NumOfVertices; u++){

if (color[u]==0) //если не пройденна - посетить

DFS_VISIT(u, ConnectionMatrix, NumOfVertices);

}

}

Реализация DFS_VISIT:

void DFS_VISIT(unsigned int u, double **ConnectionMatrix, unsigned int NumOfVertices){

color[u]=1; //теперь вершина окрашена в серый

timer++; //увеличим время

d[u]=timer; //время открытия

for (unsigned int v=0; v<NumOfVertices; v++){

if (ConnectionMatrix[u][v])

if (color[v]==0){

predcessors[v]=u;

DFS_VISIT(v, ConnectionMatrix, NumOfVertices); //рекурсивынй вызов для                       вершины v

}

}

color[u]=2; //покрасим в черный

f[u]=timer=timer+1; //обозначим время закрытия вершины u

}

Read More

Поиск в ширину у графа

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

• Суть данного алгоритма в том, что в процессе обхода мы идем вширь, то есть, перед тем, как приступить к поиску вершин на расстоянии k+1, мы выполняем обход всех вершин на расстоянии k.
• Для отслеживания процесса обхода, мы окрашиваем вершины в белый, серый или черный цвета.
• Сначала мы все вершины у нас белые, начальную вершину мы красим серым цветом, для обозначения окраса у нас есть вектор colors[numOfVertices]:
1. color[i]=0 - белый цвет
2. color[i]=1 - серый цвет
3. color[i]=2 - черный цвет
• Еще у нас есть вектор расстояний d[numOfVertices] - очень удобная штука, чтобы посмотреть, есть ли у нас какие нибудь несвязные вершины.

Алгоритм:

1. Пока очередь не пуста:
1. Взять первый элемент из очереди u
2. Цикл для каждой связной с вершиной u вершиной (v)
1. если у нас вершина v не окрашенная
1. окрасит в серый
2. пометить в векторе, что d[v]=d[u]+1
3. добавить вершину в очередь
3. Окрасить вершину u в черный цвет

Реализация:

void BFS(unsigned int NumOfVertices, double **ConnectionMatrix, unsigned int start, unsigned int target){
  //BFS algorithm
 if (target==start) return;
 const double INFINITY=1E10;
 unsigned int u=start;
 //0-white, grey-1, black-2
 vector  d (NumOfVertices,INFINITY); //вектор расстояний
 d[start]=0;
 vector  color(NumOfVertices,0); //вектор закраски
 color[start]=1;
 vector  predcessors (NumOfVertices);
 predcessors[start]=-1;
 queue  q;
 q.push(start);
 while (!q.empty()) {
  u=q.front();
  q.pop();
  for (int v=0; v< NumOfVertices; v++) {
   if (color[v]==0&&ConnectionMatrix[u][v]) {
    color[v]=1;
    d[v]=d[u]+1;
    predcessors[v]=u;
    q.push(v);
   }
  }
  color[start]=2;
 }
 cout< path;
 for (int cur=target; cur!=-1; cur=predcessors[cur])
  path.push_back (cur);
 reverse (path.begin(), path.end());
 cout << "Path from " << start << " to " << target << ": ";
 for (size_t i=0; i

Read More

Алгоритм Форда-Беллмана. Реализация на С++

Алгоритм Форда-Беллмана применяется для нахождения кратчайшего пути от одной вершины до всех остальных во взвешенном графе.
Главное его преимущество перед алгоритмом Дейкстры в том, что он способен работать с отрицательными весами, НО имеет главный минус в производительности-работает за O(|V| × |E|), так как инициализация матрицы занимает время O(V) и на каждый проход надо V(E).

Случай 1: Граф без отрицательного цикла.
Для начала реализуем простейшую реализацию для графа без отрицательных весов, этот случай будет рассмотрен в другой статье. Увы, эта реализация будет бесконечно делать релаксацию, так как при суммарном весе цикла меньше 0, при обходе сколько угодно раз, длина кратчайшего пути будет выражаться большим по модулю отрицательным числом.

Итак, все действующие лица:

• Переменная numOfVertices обозначает количество вершин в графе.
• Переменная start нужна для обозначения номера начальной вершины.
• Вектор расстояний d[numOfVertices] который имеет размер такой же как и количество вершин в графе (numOfVertices), он хранит в себе ВСЕ КРАТЧАЙШИЕ РАССТОЯНИЯ от нашей стартовой вершины до ВСЕХ ДРУГИХ.
• Структура Edge (Ребро) для описания ребра, ясно, что ребро связывает вершину u с вершиной v и имеет вес w.

struct Edge {

 unsigned int u;

 unsigned int v;

 double w;

};

•  Будем использовать вектор для хранения ребер vector<Edge>EdgeList, так как к вектору удобно обращаться по индексу;
•  Переменная const double INFINITY=1E+10 для инициализации расстояний в начале работы функции.
• Введем функцию релаксации ребер Relax (unsigned int index, vector <double> &d) для того, чтобы алгоритм был более понятен, какой кусок кода за что отвечает. index-индекс текущего ребра, d - вектор расстояний.

void Relax (unsigned int index, vector <double> &d){

 if (d[EdgeList[index].v]>d[EdgeList[index].u]+EdgeList[index].w){

d[EdgeList[index].v]=d[EdgeList[index].u]+EdgeList[index].w;

}

}

          Процесс релаксации ребра заключается в проверке ребра на то, можно ли улучшить путь из вершины u в v.
Примеры с картиночками можно почитать у Кормена на странице 670.

Сам алгоритм состоит в том, чтобы:

1. Cначала инициализируем все расстояния бесконечными величинами, а расстояние стартовой вершины нулем.
2. Цикл for для каждой вершины
1. Вложенный цикл где для каждого ребра идет процесс релаксации
3. Вывод расстояний

Простейшая неоптимизированная реализация:

void Bellman_Ford_Shortest_Path(double start, unsigned int numOfVertices){

 vector<double> d (numOfVertices, INFINITY);

 d[start]=0;

 for (unsigned int i=0; i<numOfVertices-1; i++){

  for (unsigned int j=0; j<EdgeList.size();j++){

   Relax(j,d);//РЕЛАКСАЦИЯ РЕБРА

  }

 }

 for (int i=0; i<d.size(); i++){

  if (d[i]<INFINITY){ //ЕСЛИ ЕСТЬ ПУТЬ

   cout<<"vertex "<< i+1 <<") "<<d[i]<<endl;

  }

  else cout<<"vertex "<< i+1 <<") "<<"No way to this vertex"<<endl;

 }

}

Брр. тега <code> На блогспоте не вижу, очень неудобно внедрять код.

Read More

Создание установщика для консольного приложения в vs 2010

Собственно, наступило время, когда приходится писать не простые вузовские лабораторные по программированию, а приложению рассчитанные на пользователя.
Одна из важнейших вещей - это развертывание приложения. Можно сделать это по разному : с помощью WinRar'a, обычный перенос файлов на жесткий диск и так далее. Но многим удобнее использовать обычный установщик, например формата msi, так как не каждый имеет на компьютере WinRar (да-да, странно в наши дни), а в другом способе может быть очень много файлов, что в некоторых случаях неудобно переносить на компьютер, поэтому установщик очень удобен и в этой статье я расскажу как его создать.
Для примера создам простейший Console application project (имя проекта HelloWorld) с файлом HelloWorld.cpp :)

#include "stdafx.h"

#include <iostream>

int _tmain(int argc, _TCHAR* argv[]) {

std::cout<<"HelloWorld";

return 0;

}

Далее создадим новый проект из шаблона New Project-->Other Project Types-->Setup and Deployment-->Visual Studio Installer-->Setup Project
Назовем его HelloWorldInstaller. Я его поместил в D:\Labs\2sem

Получили результат.

Нажимаем правой клавишей в окне Solution Explorer на SolutionHelloWorldInstaller выбираем в всплывающем окне Add-->Existing Project и ищем папку нашего проекта HelloWorld и ищем файл с форматом vcxproj. Выбираем его. Все! Он добавился.

Далее в Solution Explorer щелкаем правой клавишей на HelloWorldInstaller. Выбираем Add-->Project Output.

На экране появилось окно. Выбираем наш проект HelloWorld в списке проектов. Пункт Primary Output позволяет добавить все .dll и .exe файлы (которые были построены) из проекта.

Нажимаете ОК. Теперь постройте проект (Build).

Ура! Мы получили готовый msi файл и установщик. Дело сделано.

Read More