как извлечь тур TSP из неупорядоченного списка входящих в него поездок - PullRequest
Новая
       59

как извлечь тур TSP из неупорядоченного списка входящих в него поездок

1 голос
/ 27 мая 2020

Вот исходный код: 

n = 5;
trips = nchoosek(1:n,2);
x_tsp=[0;1;1;0;1;0;1;0;0;1];

Итак, нам дается неупорядоченный список составных поездок некоторого тура. Теперь нам нужно перевести его в реальный тур, то есть упорядоченный обход городов в стиле TSP. Код ниже делает это. Но, похоже, используется for l oop и повторяется. Можно ли векторизовать это в меньшем количестве строк? 

x_tsp = logical(round(x_tsp));
relevant_trips=trips(x_tsp,:);
tour=zeros(n+1,1);
r=randi(n);
tour(1)=relevant_trips(r,1);
tour(2)=relevant_trips(r,2);
tour(end)=tour(1);
for i=3:n
    relevant_trips(r,:)=[];
    [~,next_ind]=ismember(tour(i-1),relevant_trips);
    [r,c] = ind2sub(size(relevant_trips),next_ind);
    if c==2
        tour(i)=relevant_trips(r,1);
    else
        tour(i)=relevant_trips(r,2);
    end
end
...