math::TravellingSalesmansProblem Class Reference

Решение задачи коммивояжера More...

#include <travelling_salesmans_problem.h>

Collaboration diagram for math::TravellingSalesmansProblem:

Public Member Functions
	TravellingSalesmansProblem (AdjacencyMatrix &matrix, std::size_t num_of_flyers=1)
	Инициализирует новый экземпляр TravellingSalesmansProblem для нескольких коммивояжеров
std::vector< std::size_t >	GetTrajectory ()
double	GetTrajLength () const

Private Member Functions
std::vector< std::size_t >	CalculateTrajectory ()
	Просчитывает оптимальную маршрут
void	CompleteEdgePath (std::shared_ptr< TSPNode > node)
	Замыкает Гамильтонов цикл обхода контрольных точек
std::vector< std::size_t >	ConvertToVertexPath ()
	Переводит ребра, содержащихся в пути в последовательность обхода контрольных точек
AdjacencyMatrix &	DeleteEdge (AdjacencyMatrix &matrix, std::size_t start_num, std::size_t end_num)
	Удаляет ребро из матрицы смежности
void	ExpandStack ()
	Заменяет вершину графа в path_stack_ на её детей, без нарушения порядка
std::size_t	FindIndex (double eval) const
	Находит место для вставки вершины для соблюдения порядка

Private Attributes
std::vector< Edge >	edge_path_
std::size_t	num_of_flyers_ {1}
double	paths_len_
std::vector< std::shared_ptr< TSPNode > >	paths_stack_

Detailed Description

Решение задачи коммивояжера

Constructor & Destructor Documentation

TravellingSalesmansProblem()

math::TravellingSalesmansProblem::TravellingSalesmansProblem	(	AdjacencyMatrix &	matrix,
		std::size_t	num_of_flyers = 1 )

Инициализирует новый экземпляр TravellingSalesmansProblem для нескольких коммивояжеров

Parameters

matrix	матрица смежности графа
num_of_flyers	количество коммивояжеров

    : num_of_flyers_{num_of_flyers} {
  if (num_of_flyers > 1) m.ExtendTo(num_of_flyers);
  paths_stack_.push_back(std::make_shared<TSPNode>(m));
  if (m.GetSize() == 2) CompleteEdgePath(paths_stack_[0]);
}

Here is the call graph for this function:

Member Function Documentation

CalculateTrajectory()

std::vector< std::size_t > math::TravellingSalesmansProblem::CalculateTrajectory ( )

private

Просчитывает оптимальную маршрут

Returns

std::vector<std::size_t>: порядок следования вершин

                                                                     {
  while (paths_stack_[0]->matrix.GetSize() > 2) ExpandStack();
  paths_len_ = paths_stack_[0]->evaluation;
  edge_path_ = paths_stack_[0]->path;
  return ConvertToVertexPath();
}

Here is the call graph for this function:

Here is the caller graph for this function:

CompleteEdgePath()

void math::TravellingSalesmansProblem::CompleteEdgePath ( std::shared_ptr< TSPNode > node )

private

Замыкает Гамильтонов цикл обхода контрольных точек

Parameters

node	вершина графа поиска оптимального пути

                                 {
  Edge first_missed_edge(std::pair(node->matrix.GetMatrixValue(0, 2), 0));
  Edge second_missed_edge(std::pair(node->matrix.GetMatrixValue(1, 2), 0));
  for (std::size_t i = 0; i < 2; ++i) {
    if ((node->matrix.GetMatrixValue(0, 0) + node->matrix.GetMatrixValue(1, 1) <
         node->matrix.GetMatrixValue(0, 1) +
             node->matrix.GetMatrixValue(1, 0))) {
      first_missed_edge.end_num =
          (std::size_t)node->matrix.GetMatrixValue(2, 0);
      second_missed_edge.end_num =
          (std::size_t)node->matrix.GetMatrixValue(2, 1);
    } else {
      first_missed_edge.end_num =
          (std::size_t)node->matrix.GetMatrixValue(2, 1);
      second_missed_edge.end_num =
          (std::size_t)node->matrix.GetMatrixValue(2, 0);
    }
  }
  node->path.push_back(first_missed_edge);
  node->path.push_back(second_missed_edge);
}

Here is the caller graph for this function:

ConvertToVertexPath()

std::vector< std::size_t > math::TravellingSalesmansProblem::ConvertToVertexPath ( )

private

Переводит ребра, содержащихся в пути в последовательность обхода контрольных точек

Returns

std::vector<std::size_t>: последовательность обхода контрольных точек

                                                                     {
  std::map<std::size_t, std::size_t> aux_path;
  for (std::size_t i = 0; i < edge_path_.size(); ++i) {
    aux_path[edge_path_[i].start_num] = edge_path_[i].end_num;
  }
  std::vector<std::size_t> final_path;
  final_path.push_back(0);
  std::size_t key = 0;
  while (aux_path[key] != 0) {
    final_path.push_back(aux_path[key]);
    key = aux_path[key];
  }
  for (std::size_t i = 0; i < final_path.size(); ++i)
    if (final_path[i] > final_path.size() - num_of_flyers_) final_path[i] = 0;
  return final_path;
}

Here is the caller graph for this function:

DeleteEdge()

AdjacencyMatrix & math::TravellingSalesmansProblem::DeleteEdge ( AdjacencyMatrix & matrix, std::size_t start_num, std::size_t end_num )

private

Удаляет ребро из матрицы смежности

Parameters

matrix	матрица смежности
start_num	начало ребра
end_num	конец ребра

Returns

AdjacencyMatrix: матрица с удалённым ребром

                                                                           {
  for (std::size_t i = 0; i < matrix.GetSize(); ++i) {
    if (std::abs(matrix.GetMatrixValue(i, matrix.GetSize()) -
                 (double)start_num) > precision)
      continue;
    for (std::size_t j = 0; j < matrix.GetSize(); ++j) {
      if (std::abs(matrix.GetMatrixValue(matrix.GetSize(), j) -
                   (double)end_num) > precision)
        continue;
      matrix.SetMatrixValue(i, j, inf);
    }
  }
  return matrix;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ExpandStack()

void math::TravellingSalesmansProblem::ExpandStack ( )

private

Заменяет вершину графа в path_stack_ на её детей, без нарушения порядка

                                             {
  std::pair<std::size_t, std::size_t> value =
      paths_stack_[0]->matrix.GetSelectedValue();
  Edge edge(paths_stack_[0]->matrix.GetSelectedEdge());
 
  // Первый ребенок, c включением edge
  AdjacencyMatrix with_edge_matrix = paths_stack_[0]->matrix.Reducted();
  with_edge_matrix = DeleteEdge(with_edge_matrix, edge.end_num, edge.start_num);
 
  // Исключение возможности цикла
  std::map<std::size_t, std::size_t> prev_chains = paths_stack_[0]->chains;
  std::map<std::size_t, std::size_t> new_chains = paths_stack_[0]->chains;
  bool is_new = true;
  for (const auto& [start, end] : prev_chains) {
    if (start == edge.end_num) {
      new_chains.erase(start);
      new_chains[edge.start_num] = end;
      is_new = false;
      break;
    } else if (end == edge.start_num) {
      new_chains[start] = edge.end_num;
      is_new = false;
      break;
    }
  }
  if (is_new) new_chains[edge.start_num] = edge.end_num;
  for (const auto& [start, end] : new_chains) {
    for (const auto& [start2, end2] : new_chains) {
      if (end2 == start) {
        new_chains[start2] = end;
        new_chains.erase(start);
      }
      if (end == start2) {
        new_chains[start] = end2;
        new_chains.erase(start2);
      }
    }
  }
  for (const auto& [start, end] : new_chains) {
    with_edge_matrix = DeleteEdge(with_edge_matrix, end, start);
  }
  // Исключение возможности цикла
 
  with_edge_matrix = with_edge_matrix.Minor(value.first, value.second);
  paths_stack_[0]->with_edge = std::make_shared<TSPNode>(
      with_edge_matrix, paths_stack_[0], edge, new_chains);
  if (paths_stack_[0]->with_edge->matrix.GetSize() == 2)
    CompleteEdgePath(paths_stack_[0]->with_edge);
 
  // Второй ребенок, c исключением edge
  AdjacencyMatrix without_edge_matrix = paths_stack_[0]->matrix.Reducted();
  without_edge_matrix =
      DeleteEdge(without_edge_matrix, edge.start_num, edge.end_num);
  paths_stack_[0]->without_edge =
      std::make_shared<TSPNode>(without_edge_matrix, paths_stack_[0]);
 
  // Добавляем детей в стек вершин,удаляем их родителя
  double with_eval = paths_stack_[0]->with_edge->evaluation;
  double without_eval = paths_stack_[0]->without_edge->evaluation;
  if (!std::isinf(without_eval)) {
    if (FindIndex(without_eval) < paths_stack_.size())
      paths_stack_.insert(paths_stack_.begin() + FindIndex(without_eval),
                          paths_stack_[0]->without_edge);
    else
      paths_stack_.push_back(paths_stack_[0]->without_edge);
  }
  if (!std::isinf(with_eval)) {
    if (FindIndex(with_eval) < paths_stack_.size())
      paths_stack_.insert(paths_stack_.begin() + FindIndex(with_eval),
                          paths_stack_[0]->with_edge);
    else
      paths_stack_.push_back(paths_stack_[0]->with_edge);
  }
  paths_stack_.erase(paths_stack_.begin());
}

Here is the call graph for this function:

Here is the caller graph for this function:

FindIndex()

std::size_t math::TravellingSalesmansProblem::FindIndex ( double eval ) const

private

Находит место для вставки вершины для соблюдения порядка

Parameters

eval	нижняя оценка матрицы

Returns

std::size_t: индекс вставки вершины

                                                                 {
  // Нижняя и верхняя границы
  std::size_t start = 0;
  std::size_t end = paths_stack_.size();
  // Уменьшение области поиска
  while (start < end) {
    std::size_t mid = (start + end) / 2;
    // Если eval нашлось
    if (std::abs(paths_stack_[mid]->evaluation - eval) <= precision)
      if (mid)
        return mid;
      else
        return mid + 1;
    else if (paths_stack_[mid]->evaluation < eval)
      start = mid + 1;
    else
      end = mid;
  }
  if (end)
    return end;
  else
    return end + 1;
}

Here is the caller graph for this function:

GetTrajectory()

std::vector< std::size_t > math::TravellingSalesmansProblem::GetTrajectory ( )

inline

                                              {
    return CalculateTrajectory();
  }

Here is the call graph for this function:

Here is the caller graph for this function:

GetTrajLength()

double math::TravellingSalesmansProblem::GetTrajLength ( ) const

inline

{ return paths_len_; }

Member Data Documentation

edge_path_

std::vector<Edge> math::TravellingSalesmansProblem::edge_path_

private

num_of_flyers_

std::size_t math::TravellingSalesmansProblem::num_of_flyers_ {1}

private

{1};

paths_len_

double math::TravellingSalesmansProblem::paths_len_

private

paths_stack_

std::vector<std::shared_ptr<TSPNode> > math::TravellingSalesmansProblem::paths_stack_

private

---

The documentation for this class was generated from the following files:

• math/littles_algorithm/travelling_salesmans_problem.h
• math/littles_algorithm/travelling_salesmans_problem.cpp