Минимальная стоимость посещения только выбранных городов и возврата к началу?

Question

Минимальная стоимость посещения только выбранных городов и возврата к началу?

Я понимаю проблему коммивояжера. Предположим, если я хочу посетить только выбранные города и вернуться, чтобы начать, как это сделать?

Допустим, моя матрица затрат

Если я хочу посетить все города и вернуться к А. Мой кратчайший путь будет A->B->C->D и минимальное расстояние будет 4,

Предположим, скажем, если я хочу посетить только B и D. Как я могу найти минимальное расстояние?

Это модифицированная проблема коммивояжера? Может ли кто-нибудь помочь мне в этом деле?

0

brute-force c++traveling-salesman

Решение

Другие решения

У меня нет удобного кода, но вот несколько советов и псевдокодов, которые помогут вам в этом:
Я бы решил это, сохранив вектор, а также вашу матрицу расстояний в памяти. Что-то вроде:

struct Location{
bool visited;
bool mustVisit;
}

Vector<Location> locationVec;

Заполните вектор местоположениями вашей проблемы, отметив, нужно ли их посещать, и всегда устанавливая посещение как ложное. Затем начинается самое интересное! Вам нужно создать перестановки locationVec. Я бы сделал это рекурсивно, что-то вроде:

void addLocation(int & curLength, int & maxLength, int & curDistance, Vector<Location> &locationVec, Location* lastVisited)
if(curLenth == maxLength){
//check if currentDistance is less than the previously generated best difference, if so
//replace it
lastVisited->visited=0;
return;
}

//Add the next location
for (int& i : locationVec){
//Check if the location has been visited, and if it must be visited.
//If so: mark as visited, point lastVisited to it, and break
//Also add from lastVisited to the new location to your curDistance
curLength++;
}

addLocation(curLength, maxLength, curDistance, locationVec, lastVisited);
return;
}

Это должно начать вас. Не забудьте вычесть из currentDist, когда вы переходите с посещения = 1 на посещение = 0, потому что вы, по сути, «не посещаете» город. Возможно, вам также придется отслеживать последнее посещение, в зависимости от вашей конкретной реализации.

Если вам нужно ускорить его (и вы, вероятно, это сделаете, путешествуя с продавцом очень медленно), посмотрите на Branch and Bound: http://en.wikipedia.org/wiki/Branch_and_bound

0

Источник

Accepted Answer

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

Так как коммивояжер — NP NPN, для сложности не важно, что вы управляете Floyd-Warshall до этого.

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

1