Понятие исчерпывающего перебора. Решение задачи коммивояжера. - EcsFlash/DataTypes GitHub Wiki

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

Задача Коммивояжера

Надо найти такой кратчайший путь по заданным n городам, чтобы каждый город посещался только один раз и конечным пунктом оказался город, с которого началось путешествие. Эту задачу легко смоделировать при помощи взвешенного графа, вершины которого представляют города, а веса ребер определяют расстояния.

int naiveTSP(int start) {
	start -= std_offset;
	int sum = INT_MAX;
	set<int> wasIn{ start };
	for (int i = 0; i < kernel.size(); i++) {
		if (kernel[start][i] != 0) {
			int temp = ntsp(i, wasIn, start) + kernel[start][i]; //длина пути от непосещеной вершины до конца + длина от текущей до непосещенной
			if (temp < sum) {
				sum = temp;
			}
		}
	}
	return sum;
}
int ntsp(int start, set<int> wasIn, int realStart) {
	if ( kernel.size() - wasIn.size() == 1) {
		return kernel[start][realStart];
	}
	wasIn.insert(start);
	for (int i = 0; i < kernel.size(); i++) {
		if (wasIn.count(i) == 0 && kernel[start][i] != 0) {
			return ntsp(i, wasIn, realStart) + kernel[start][i];//длина пути от непосещеной вершины до конца + длина от текущей до непосещенной
		}
	}
}

Рассмотрим пример:

Начнем путь с вершины под номером 1. Из нее мы можем попасть в вершины 2, 3, 4. Соответственно рекурсивно продолжаем строить наши пути. Из вершины 2 мы можем попасть в вершины 3 и 4. А из вершины 3 только в 4. Когда дойдем до вершины 4, непосещенных на данном маршруте вершин не останется. Соответственно необходимо просто вернуться в начальную. То есть на каждом шаге алгоритм выстраивает маршрут, попутно вычисляя его длину.