Đường đi nhanh nhất với gia tốc tại các điểm

Question

Đây chỉ là thứ tôi tự nghĩ ra, nhưng có vẻ như đó là một vấn đề thú vị và nó khiến tôi bối rối.

Bạn có một tập hợp các điểm trong không gian hai chiều, với một điểm được chỉ định là "Bắt đầu" và một "Cuối". Mỗi điểm có tọa độ (tính bằng mét từ gốc), nhưng cũng là "số gia tốc" (tính bằng mét/giây của delta-V). Khi đạt đến một điểm (bao gồm cả bắt đầu), bạn có thể tăng tốc lên tới số gia tốc của điểm đó theo bất kỳ hướng nào. Chi phí cạnh phụ thuộc vào tốc độ hiện tại của bạn, nhưng bạn cũng phải di chuyển theo đúng hướng.

Có một thuật toán hiệu quả để tìm đường đi nhanh nhất đến điểm cuối không? Tôi đã không nghĩ ra bất cứ điều gì tốt hơn "Hãy thử mọi con đường và kiểm tra kết quả". Thuật toán đơn giản và khác của Djikstra không hoạt động, bởi vì bạn không thể dễ dàng nói rằng một đường dẫn đến điểm trung gian tốt hơn hoặc xấu hơn điểm khác, nếu bạn đến với vận tốc ban đầu khác nhau.

Nếu điều đó quá dễ, điều gì sẽ xảy ra nếu bạn thêm yêu cầu mà bạn phải dừng ở điểm kết thúc? (nghĩa là, bạn phải có ít hơn giá trị gia tốc của nó khi bạn đạt đến kết thúc.)

EDIT: Để rõ ràng, các vấn đề hướng. Bạn duy trì một vector tốc độ khi bạn đi qua biểu đồ và gia tốc có nghĩa là thêm một vectơ vào nó, có độ lớn được giới hạn ở số gia tốc của điểm đó. Điều này có nghĩa là có những tình huống mà việc xây dựng một vận tốc rất lớn là bất lợi, vì bạn sẽ đi quá nhanh để "chỉ đạo" đối với các điểm có giá trị khác/điểm đến của bạn.

Answer 1

Tôi nghĩ rằng yêu cầu mà bạn chỉ sử dụng gia tốc từ mỗi điểm một lần làm cho vấn đề này NP hoàn thành trong trường hợp chung. Hãy xem xét một đầu vào trông như thế này:

Nếu "khoảng cách rất lớn" giữa điểm cuối và phần còn lại của các điểm là đủ lớn để chiếm ưu thế chi phí của giải pháp cuối cùng, việc tìm kiếm một giải pháp tối ưu sẽ đun sôi xuống để tìm một cách để nhận được càng nhiều tăng tốc độ càng tốt từ đầu của đồ thị. Nếu bạn chỉ cho phép mỗi điểm được thông qua một lần, điều này sẽ tương đương với vấn đề đường dẫn Hamilton, đó là NP hoàn thành.

Điều đó nói rằng, vấn đề của bạn có một số quy tắc bổ sung trên đầu nó (khoảng cách là euclide, biểu đồ luôn hoàn tất) có thể sẽ làm cho vấn đề trở nên dễ dàng hơn.

Answer 2

Bạn có thể thử giải quyết vấn đề này ngược bằng cách truy tìm đường dẫn đệ quy từ đầu đến nút khác, sau đó chỉ định tốc độ tối đa dọc theo đường để có thể chuyển từ nút đó sang nút khác. Quy tắc hủy sẽ là nếu đường dẫn từ nút hiện tại sang nút tiếp theo tồn tại với vận tốc ít hơn và ít thời gian hơn từ kết thúc, điều này có nghĩa là đường dẫn khác tối ưu hơn theo mặc định vì nó có thể tiếp cận nhiều nút hơn và tốn ít thời gian hơn. Khi đường dẫn đến nút bắt đầu, nó sẽ được tính toán lại dựa trên tốc độ tối đa có thể đạt được khi bắt đầu và được lưu trữ. Sau đó, bạn thu thập con đường với ít thời gian hơn.

Bạn phải tìm kiếm bất kỳ đường dẫn nào có sẵn tại đây, vì các đường dẫn có sẵn trên biểu đồ của bạn phụ thuộc vào trạng thái trước đây với cơ chế gián tiếp, sử dụng tốc độ thấp hơn cho phép nhiều lựa chọn hơn.