Вот моя формулировка проблемы:
У меня есть куб с указанными размерами. со временем в этом кубе генерируются несколько шаров. Я смоделировал координаты (местоположение x, y, z), время генерации и размер шаров. Теперь мне нужно найти кратчайший путь перекрывающихся шаров, соединяющих верхнюю сторону куба с нижней, и найти время, за которое этот путь пройден.
До сих пор я думал о том, чтобы найти парное евклидово расстояние между всеми точками и парную сумму радиусов шара. Затем сравните расстояние с суммой, чтобы найти матрицу перекрытия. Затем найдите все объекты наверху, у которых z-размер меньше 0 и z + размер больше глубины куба, а затем я должен найти путь. Я ценю любую помощь и идею заранее.
Например, рассмотрим следующие данные и код, который я разработал до сих пор:
offspr_x = [1 3 5 1 2]
offspr_y = [3 3 1 8 2]
offspr_z = [1 4 5 3 2]
size = [2 1 4 6 3]
time = [2 5 6 3 8]
Pos= [offspr_x' offspr_y' offspr_z']
dd=pdist(Pos,'euclidean')
ddm = squareform(dd)
% compute similar matrix based on sum of object sizes (assumes size is radius)
drad = meshgrid(size)+ meshgrid(size)';
dadj = ddm.*(ddm <= drad);
Теперь мне нужно преобразовать матрицу перекрытия в объект графа и попытаться найти кратчайший путь между теми точками, у которых offspr_z-size ‹ 0 (все объекты вверху имеют z-size меньше 0) и offspr_z+size > 5 (объекты внизу z+size больше 5):
starts = find(offspr_z-size < 0)
ends = find(offspr_z+size > 5)
ОБНОВЛЕНИЕ: как предложил @beaker, я также попробовал Floyd-Warshall, и вот код, который я использовал:
function D = FastFloyd(D)
n = size(D, 1);
for k=1:n
i2k = repmat(D(:,k), 1, n);
k2j = repmat(D(k,:), n, 1);
D = min(D, i2k+k2j);
end
end
Следовательно, для:
dadj(dadj==0)=Inf
D = FastFloyd(dadj)
Я получил следующий результат:
D =
3.4641 4.1815 6.0000 5.3852 1.7321
4.1815 4.8990 3.0000 5.4772 2.4495
6.0000 3.0000 6.0000 8.3066 4.3589
5.3852 5.4772 8.3066 10.7703 6.1644
1.7321 2.4495 4.3589 6.1644 3.4641
Но мне нужно найти кратчайший (скорейший) путь между начальным и конечным векторами (точками, которые перекрывают верхнюю и нижнюю поверхности куба). Я говорю скорее, потому что меня интересует не наименьшее расстояние, а наименьшее время генерации...
dadj(dadj==0)=Inf
. - person beaker   schedule 28.09.2015