Selecting submatrix takes long

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

[Walter Roberson]

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]

numeric, I edited my question to clarify those.

Answer 1

[Jan]

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.