Atanmış yolda seyahat ederken harcanan zaman azalır.

Question

Bu soru this one ile ilgili olup, bir dizi puan üzerindeki yolu optimize etmekten kaynaklanmıştır. Buradaki durum şu şekildedir: Bir nesne, 2B noktaların bir listesini içeren belirlenmiş bir yolu taşır. (Daha fazla Ds mümkündür, ancak her dönüş teknik olarak 2B olduğu için, iki boyut için çözme yapacaktır.) Her noktada bu nesne hızını, maksimum uzunluğun önceden belirlendiği bir vektörle değiştirebilir (bir noktaya atanmış). Yolun sonunda hızın önemi yoktur. Soru şu, bu yolu seyahat etmek için harcanan asgari süreyi nasıl belirleyecek? Bu görev için etkili bir algoritma var mı? Açgözlü bir algoritma, nesneyi özel olarak hazırlanmış veriler durumunda bir taramayı yavaşlatmaya ya da nesneyi bir sonraki belirlenen noktaya dönüştürebilmek için yavaşlatabilir. Geriye dönük açgözlü bir algoritma da aynı hata ile kusurludur, maksimum hızda sonuna ulaşmak her zaman iyi değildir.

Bir örnek: Nokta vektörü: {(0,0), (0,1), (1,1), (2,2)} ve en fazla uzunluk vektörü {2.0, 2.0, 3.0}. Bu nokta örneğin (0,sqrt(2))'da p1'den p2'ye, daha sonra (sqrt(2),0)'da p2'den p3'e ve (s,s)'da maksimum hızda s'un p3'den p4'e doğru hareket eder. Ve bu, suboptimal bir çözüm olabilir, p1'den p2'ye 0,01 kadar yavaşladığınızı, p2'den p3'e kadar bir hızla hızlanmaya başladığınızı, sonra da p3'ten p4'e başka bir parçaya geçebileceğinizi, olası toplam sürenin bundan daha az olduğunu söyleyebiliriz. hız kümesi.

Answer 1

Bu, ortak doğrusal olmayan optimizasyon kitaplıkları tarafından çözülebilen bir dışbükey optimizasyon problemidir. SciPy:

import numpy as np 
from scipy import optimize 

points = np.array([[0., 0.], [0., 1.], [1., 1.], [2., 2.]]) 
movements = np.diff(points, axis=0) 
lengths = np.linalg.norm(movements, axis=1) 
directions = movements/lengths[:, np.newaxis] 
max_acceleration = np.array([2., 2., 3.]) 

fun = lambda x: np.sum(lengths/x) 
x0 = np.repeat(.5 * np.amin(max_acceleration), len(movements)) 
bounds = [(0., max_acceleration[0])] + [(0., None)] * (len(movements) - 1) 
constraints = [ 
    dict(
     type='ineq', 
     fun=lambda x, j: max_acceleration[j + 1] - np.linalg.norm(x[j] * directions[j] - x[j + 1] * directions[j + 1]), 
     args=(i,)) for i in range(len(movements) - 1) 
] 
x = optimize.minimize(fun, x0, bounds=bounds, constraints=constraints).x 
print(x)