Selecting submatrix takes long
3 ビュー (過去 30 日間)
古いコメントを表示
I am working on a TSP tour construction algorithm, where distances are saved in a distance matrix D, and the tour is represented as a permutation of the n cities.
It starts with a partial tour of two nodes, and from then on it keeps adding an unvisited city until the partial tour contains all cities.
To decide which city to add to the current partial tour, I need a submatrix from the D distance matrix. However, this operation, as it turns out, takes about 90% of full running time. Is there any way to speed this up?
Here is part of my code: (the line that takes most time is the one that defines 'searchArea'
while numel(tour) < n-1
searchArea = D(nodesLeft,tour); %submatrix that needs to be investigated
addCity = findCity(searchArea); %find the city that should be added
addCity = nodesLeft(addCity); %convert 'addCity' from an idx to city number
tour = insertCity(D,tour,addCity); %insert city in partial tour appropriately
nodesLeft = nodesLeft(nodesLeft~=addCity);% update which cities are left over
end
EDIT:
nodesLeft is a shrinking vector containing all numbers not yet in tour.
similarly tour is a growing vector containing all numbers 1:n except for what is in nodesLeft
2 件のコメント
Walter Roberson
2019 年 1 月 6 日
Are nodesLeft and tour numeric or logical?
My tests suggest that logical indexing is typically faster than numeric indexing, but that the timing for logical indexing can be pretty irregular.
採用された回答
Jan
2019 年 1 月 7 日
The growing and shrinking of array is expensive, because Matlab has to allocate new arrays each time and copy the old contents (except for the deleted element). Usually it is cheaper to use arrays with constant sizes and a logical vector, which contain a true for cities, which are selected.
This might forward the creation of submatrices to the subfunctions, such that it depends on the implementation of the not shown functions like findCity. Without seeing the full code, it is hard to guess, if the "90%" can be avoided or to suggest working code.
0 件のコメント
その他の回答 (0 件)
参考
カテゴリ
Help Center および File Exchange で Logical についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!