Задача коммивояжера методом Литтла на C++

в 6:37, , рубрики: c++, Алгоритмы, дискретная математика, Занимательные задачки, Литтл, Программирование, С++

Обучаясь в университете, каждому приходилось делать разного рода задачи. Вот, наступает конец полугодия, сессия на носу, начало выдачи курсовых заданий и мне посчастливилось стать тем, кто должен реализовать метод Литтла для задачи коммивояжера. Итак начнем.

Кто такой коммивояжер? Коммивояжер — это разъездной торговый агент какой-либо фирмы, предлагающий покупателям товары по образцам и каталогам. Его задача объездить все пункты назначения, не побывав ни в одном дважды и вернуться в точку старта.

image

Метод Литтла

Целью данного метода является поиск гамильтонового цикла с минимальной стоимостью в графе. Что бы найти его, нужно придерживаться следующим действиям:

  1. В каждой строке матрицы стоимости найдем минимальный элемент и вычтем его из всех элементов строки. Сделаем это и для столбцов, не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент.
  2. Для каждого нулевого элемента матрицы, рассчитываем коэффициент k, который равен сумме минимальных элементов столбца и строки этого нуля. Выбираем нуль с максимальным коэффициентом (если таковых несколько выбираем любой из них). Вносим в гамильтонов контур соответствующую дугу.
  3. Удаляем строку и столбец, на пересечении которого выбранный нами нуль.
  4. Проверяем граф на наличие точек возврата, если есть таковые, то меняем их значение на максимальное. Повторяем предыдущие действия пока не останется матрица порядка 2.
  5. Вносим в гамильтонов контур недостающие дуги. Получаем искомый цикл.

Реализация

Для дальнейшего расширения и работы с другими алгоритмами, создадим класс Algorithm:

Algorithm

//Algorithm.h
class Algorithm
{
public:
	char* name = "Algorithm"; // Название алгоритма
	std::vector<std::vector<int>> data; // Массив значений (матрица)
	Algorithm();
	Algorithm(std::vector<std::vector<int>>);
	Algorithm(char*);
	bool LoadData(std::vector<std::vector<int>>);
	bool LoadData(char*);
	virtual void Run(); // Метод для запуска алгоритма
protected:
	int GetStrCount(std::ifstream&); // Считываем количество строк в файле
	int GetColCount(std::ifstream&); // Считываем количество столбцов в файле
	virtual bool validateData(); // Метод для проверки значений в матрице. Вызывается перед Run()
};

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

Далее, создадим класс интересующего нам алгоритма. В нашем случае LittleAlgorithm.

LittleAlgorithm

class LittleAlgorithm : public Algorithm
{
public:
	vector<pair<int,int>> result; // Результат. Здесь будет храниться искомый цикл
	LittleAlgorithm();
	LittleAlgorithm(vector<vector<int>>);
	LittleAlgorithm(char*);
	virtual void Run();
private:
	enum check{Row, Col};
	int getMin(vector<vector<int>>, int, check); // Поиск минимального элемента столбца/строки
	void matrixProcedure(vector<vector<int>>); // Метод в котором идет поиск цикла
	void showMatrix(vector<vector<int>>); // Вывод матрицы
	int getResultSum(); // Считывание суммы всех выбранных дуг
	virtual bool validateData(); 
};

Реализация вспомогательных методов:

Other

void LittleAlgorithm::Run()
{
	name = "Little algorithm";
	Algorithm::Run();

	matrixProcedure(vector<vector<int>>(data));
}
int LittleAlgorithm::getMin(vector<vector<int>> matrix, int sel, check pos)
{
	int min = INT32_MAX;
	for (int i = 0; i < matrix[sel].size() - 1; i++)
		switch (pos)
		{
		case LittleAlgorithm::Row:
			if (min > matrix[sel][i])
				min = matrix[sel][i];
			break;
		case LittleAlgorithm::Col:
			if (min > matrix[i][sel])
				min = matrix[i][sel];
			break;
		}
	return min;
}
void LittleAlgorithm::showMatrix(vector<vector<int>> temp)
{
	std::cout << endl;
	std::cout << "t";
	for (int i = 0; i < temp[temp.size() - 1].size() - 1; i++) {
		std::cout << temp[temp.size() - 1][i] << "t";
	}
	std::cout << endl;
	std::cout << "t";
	for (int i = 0; i < temp[0].size(); i++)
		for (int j = 0; j<6; j++) std::cout << "_";
	std::cout << endl <<endl;
	for (int i = 0; i < temp.size() - 1; i++) {
		std::cout << temp[i][temp.size() - 1] << " | " << "t";
		for (int j = 0; j < temp[i].size() - 1; j++)
			if(temp[i][j] != INT32_MAX && j != temp.size() - 1)std::cout << temp[i][j] << "t";
			else std::cout << "inf" << "t";
		std::cout << endl;
	}
	std::cout << endl << endl;
}
int LittleAlgorithm::getResultSum()
{
	int sum = 0;
	for (int i = 0; i < result.size(); i++)
		sum += data[result[i].first - 1][result[i].second - 1];
	return sum;
}
bool LittleAlgorithm::validateData()
{
	//Добавляем в нашу матрицу столбец и строку с нумерацией для отслеживания удаляемых ребер
	for (int i = 0; i < data.size(); i++)
		for (int j = 0; j < data[i].size(); j++)
			if (data[i][j] == 0)
				data[i][j] = INT32_MAX;

	vector<vector<int>> temp(data);
	for (int i = 0; i < data.size(); i++)
		data[i].push_back(i + 1);
	vector<int> numeration;
	for (int i = 0; i < data[0].size(); i++)
		numeration.push_back(i + 1);
	data.push_back(numeration);

	return true;
}

А вот и собственно говоря сам метод, реализующий метод Литтла:

matrixProcedure

void LittleAlgorithm::matrixProcedure(vector<vector<int>> matrix)
{
	//Определяем точку возврата и удаляем необходимое ребро
	if (matrix.size() - 1 > 2){
		vector<int> vertexes;
		for (int i = 0; i < result.size(); i++) {
			vertexes.push_back(result[i].first);
			vertexes.push_back(result[i].second);
		}
		for (int i = 0; i < vertexes.size(); i++) {
			pair<int, int> elem(INT32_MAX, INT32_MAX), elem1(INT32_MAX, INT32_MAX);
			for (int j = 0; j < vertexes.size(); j++) {
				if (vertexes[i] != vertexes[j]) {
					for (int k = 0; k < matrix[matrix.size() - 1].size() - 1; k++) {
						if (vertexes[i] == matrix[k][matrix[k].size() - 1]) elem.first = k;
						if (vertexes[j] == matrix[k][matrix[k].size() - 1]) elem1.first = k;
					}
					for (int k = 0; k < matrix.size() - 1; k++) {
						if (vertexes[i] == matrix[matrix.size() - 1][k]) elem.second = k;
						if (vertexes[j] == matrix[matrix.size() - 1][k]) elem1.second = k;
					}
				}
			}
			for (int i = 0; i < matrix.size() - 1; i++)
				for (int j = 0; j<matrix.size() - 1; j++)
					if (i == elem1.first && j == elem1.second)
						matrix[elem1.first][elem1.second] = INT32_MAX;
			for (int i = 0; i < matrix.size() - 1; i++)
				for (int j = 0; j < matrix.size() - 1; j++)
					if (i == elem.first && j == elem.second)
						matrix[elem.first][elem.second] = INT32_MAX;
		}
	}

	//Вычитаем из каждой строки минимальное значение
	for (int i = 0; i < matrix.size() - 1; i++) {
		int min = 0;
		if ((min = getMin(matrix, i, check::Row)) == INT32_MAX) {
			showMatrix(matrix);
			std::cout << endl << "Bad road" << endl;
			return;
		}
		if ((min = getMin(matrix, i, check::Row)) != 0)
			for (int j = 0; j < matrix[i].size() - 1; j++)
				if(matrix[i][j] != INT32_MAX) matrix[i][j] -= min;
	}

	//Вычитаем из каждого столбца минимальное значение
	for (int i = 0; i < matrix[matrix.size() - 1].size() - 1; i++) {
		int min = 0;
		if ((min = getMin(matrix, i, check::Col)) == INT32_MAX) {
			showMatrix(matrix);
			std::cout << endl << "Bad road" << endl;
			return;
		}
		if ((min = getMin(matrix, i, check::Col)) != 0)
			for (int j = 0; j < matrix.size() - 1; j++)
				if (matrix[j][i] != INT32_MAX) matrix[j][i] -= min;
	}

	//Находим максимально оцененный ноль
	int Max = 0;
	for (int i = 0; i < matrix.size() - 1; i++)
		for (int j = 0; j < matrix[i].size() - 1; j++)
			if (matrix[i][j] == 0) {
				matrix[i][j] = INT32_MAX;
				int max = (getMin(matrix, i, check::Row) == INT32_MAX || getMin(matrix, j, check::Col) == INT32_MAX)? INT32_MAX: getMin(matrix, i, check::Row) + getMin(matrix, j, check::Col);
				if (max > Max) Max = max;
				matrix[i][j] = 0;
			}

	//Находим все нули максимальная оценка которых равна Max
	vector<pair<int, int>> Maxs;
	for (int i = 0; i < matrix.size() - 1; i++)
		for (int j = 0; j < matrix[i].size() - 1; j++)
			if (matrix[i][j] == 0) {
				matrix[i][j] = INT32_MAX;
				int max = (getMin(matrix, i, check::Row) == INT32_MAX || getMin(matrix, j, check::Col) == INT32_MAX) ? INT32_MAX : getMin(matrix, i, check::Row) + getMin(matrix, j, check::Col);
				if (max == Max) Maxs.push_back(pair<int, int>(matrix[i][matrix.size() - 1], matrix[matrix.size() - 1][j]));
				matrix[i][j] = 0;
			}
	//Вывод координат выбранных нулей
	std::cout << "Maxs - ";
	for (int i = 0; i < Maxs.size(); i++)
		std::cout << Maxs[i].first << " " << Maxs[i].second << "t";
	std::cout << endl;
	//Вывод матрицы
	showMatrix(matrix);
	std::cout << endl;
	//Завершаем выполнение данной ветви если нету нулей
	if (Maxs.size() == 0) {
		std::cout << "Bad road." << endl;
		return;
	}
	
	for (int i = 0; i < Maxs.size(); i++) {
		//Добавляем вершину в массив с результатом
		result.push_back(Maxs[i]);
		//Если размер матрицы порядка 1, выводим результат и завершаем текущию ветвь
		if (matrix.size() - 1 == 1) {
			for (int i = 0; i < result.size(); i++)
				std::cout << "(" << result[i].first << ", " << result[i].second << ")t";
			std::cout << endl;
			std::cout << "Result: " << getResultSum() << endl;
			result.pop_back();
			return;
		}
		//Создаем копию текущей матрицы и удаляем из нее строку и столбец выбранного нуля
		vector<vector<int>>  temp(matrix);
		pair<int, int> elem(INT32_MAX, INT32_MAX), elem1(INT32_MAX, INT32_MAX);
		for (int j = 0; j < temp[temp.size() - 1].size() - 1; j++) {
			if (Maxs[i].first == temp[j][temp[j].size() - 1]) elem.first = j;
			if (Maxs[i].second == temp[j][temp[j].size() - 1]) elem1.first = j;
		}
		for (int j = 0; j < temp.size() - 1; j++) {
			if (Maxs[i].second == temp[temp.size() - 1][j]) elem.second = j;
			if (Maxs[i].first == temp[temp.size() - 1][j]) elem1.second = j;
		}

		for(int i = 0; i < temp.size() - 1; i++)
			for(int j = 0;j<temp.size() - 1; j++)
				if(i == elem1.first && j == elem1.second)
					temp[elem1.first][elem1.second] = INT32_MAX;

		for (int j = 0; j < temp[temp.size() - 1].size(); j++)
			temp[j].erase(temp[j].begin() + elem.second);
		temp.erase(temp.begin() + elem.first);
		//Вызываем рекурсивно эту же функцию для уже новой матрицы
		matrixProcedure(temp);
		//Удаляем последние значение из массива с результатом 
		result.pop_back();
	}
}

Результат

К примеру для матрицы:

0 5 8 10 0 0 3 6
5 0 2 0 0 0 0 1
8 2 0 4 5 6 0 7
10 0 4 0 12 9 7 0
0 0 5 12 0 9 0 12
0 0 6 9 9 0 8 0
3 0 0 7 0 8 0 2
6 1 7 0 12 0 2 0

Результатом будет:

Результат

Little algorithm:
Maxs - 1 7 7 1

1 2 3 4 5 6 7 8
______________________________________________________

1 | inf 2 5 5 inf inf 0 3
2 | 3 inf 1 inf inf inf inf 0
3 | 5 0 inf 0 0 0 inf 5
4 | 5 inf 0 inf 5 1 3 inf
5 | inf inf 0 5 inf 0 inf 7
6 | inf inf 0 1 0 inf 2 inf
7 | 0 inf inf 3 inf 2 inf 0
8 | 4 0 6 inf 8 inf 1 inf

Maxs - 7 8

1 2 3 4 5 6 8
________________________________________________

2 | 0 inf 1 inf inf inf 0
3 | 2 0 inf 0 0 0 5
4 | 2 inf 0 inf 5 1 inf
5 | inf inf 0 5 inf 0 7
6 | inf inf 0 1 0 inf inf
7 | inf inf inf 3 inf 2 0
8 | 1 0 6 inf 8 inf inf

Maxs - 8 2

1 2 3 4 5 6
__________________________________________

2 | 0 inf 1 inf inf inf
3 | 2 0 inf 0 0 0
4 | 2 inf 0 inf 5 1
5 | inf inf 0 5 inf 0
6 | inf inf 0 1 0 inf
8 | inf 0 6 inf 8 inf

Maxs - 2 3

1 3 4 5 6
____________________________________

2 | inf 0 inf inf inf
3 | 0 inf 0 0 0
4 | 0 0 inf 5 1
5 | inf 0 5 inf 0
6 | inf 0 1 0 inf

Maxs - 4 1

1 4 5 6
______________________________

3 | inf 0 0 0
4 | 0 inf 5 1
5 | inf 5 inf 0
6 | inf 1 0 inf

Maxs - 5 6 6 4

4 5 6
________________________

3 | inf 0 0
5 | 4 inf 0
6 | 0 0 inf

Maxs - 3 5 6 4

4 5
__________________

3 | inf 0
6 | 0 inf

Maxs - 6 4

4
____________

6 | 0

(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (5, 6) (3, 5) (6, 4)
Result: 41
Maxs - 3 5

5
____________

3 | 0

(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (5, 6) (6, 4) (3, 5)
Result: 41
Maxs - 3 5 5 6

5 6
__________________

3 | 0 0
5 | inf 0

Maxs - 5 6

6
____________

5 | 0

(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (6, 4) (3, 5) (5, 6)
Result: 41
Maxs - 3 5

5
____________

3 | 0

(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (6, 4) (5, 6) (3, 5)
Result: 41
Maxs - 2 8

2 3 4 5 6 7 8
________________________________________________

1 | 0 3 3 inf inf inf 1
2 | inf 1 inf inf inf inf 0
3 | 0 inf 0 0 0 inf 5
4 | inf 0 inf 5 1 2 inf
5 | inf 0 5 inf 0 inf 7
6 | inf 0 1 0 inf 1 inf
8 | 0 6 inf 8 inf 0 inf

Maxs - 3 2

2 3 4 5 6 7
__________________________________________

1 | inf 0 0 inf inf inf
3 | 0 inf 0 0 0 inf
4 | inf 0 inf 5 1 1
5 | inf 0 5 inf 0 inf
6 | inf 0 1 0 inf 0
8 | inf 0 inf 2 inf inf

Maxs - 1 4 8 5

3 4 5 6 7
____________________________________

1 | inf 0 inf inf inf
4 | 0 inf 5 1 1
5 | 0 5 inf 0 inf
6 | 0 1 0 inf 0
8 | inf inf 0 inf inf

Maxs - 6 7 8 5

3 5 6 7
______________________________

4 | inf 4 0 inf
5 | 0 inf 0 inf
6 | 0 0 inf 0
8 | inf 0 inf inf

Maxs - 4 5 5 3 5 6 8 5

3 5 6
________________________

4 | inf 0 inf
5 | 0 inf 0
8 | inf 0 inf

3 6
__________________

5 | 0 0
8 | inf inf

Bad road

5 6
__________________

4 | 0 inf
8 | 0 inf

Bad road

3 5
__________________

4 | inf 0
8 | inf 0

Bad road

3 6
__________________

4 | inf inf
5 | 0 0

Bad road
Maxs - 4 6 5 6 6 3 6 7

3 6 7
________________________

4 | inf 0 inf
5 | inf 0 inf
6 | 0 inf 0

3 7
__________________

5 | inf inf
6 | 0 0

Bad road

3 7
__________________

4 | inf inf
6 | 0 0

Bad road

6 7
__________________

4 | 0 inf
5 | 0 inf

Bad road

3 6
__________________

4 | inf 0
5 | inf 0

Bad road
Maxs - 1 4

3 4 6 7
______________________________

1 | inf 0 inf inf
4 | 0 inf 1 1
5 | inf 5 0 inf
6 | 0 1 inf 0

Maxs - 4 6 5 6 6 3 6 7

3 6 7
________________________

4 | inf 0 inf
5 | inf 0 inf
6 | 0 inf 0

3 7
__________________

5 | inf inf
6 | 0 0

Bad road

3 7
__________________

4 | inf inf
6 | 0 0

Bad road

6 7
__________________

4 | 0 inf
5 | 0 inf

Bad road

3 6
__________________

4 | inf 0
5 | inf 0

Bad road

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

Исходные файлы

Автор: 22116

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js