Selecting submatrix takes long

Question

Berlibur 2019-1-5

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/438418-selecting-submatrix-takes-long

回答： Jan 2019-1-7

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.

Berlibur 2019-1-6

numeric, I edited my question to clarify those.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jan 2019-1-7

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/438418-selecting-submatrix-takes-long#answer_355314

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.