這只是我自己想出的東西，但它看起來像一個有趣的問題，它讓我難倒了。加速點最快的路徑
您在二維空間中有一組點，一個點指定爲「開始」和一個「結束」。每個點都有座標（距離原點的米），還有一個「加速度數」（以米/秒爲單位）。在達到一個點（包括開始點）後，您可以在任何方向上加速到該點的加速度數。邊緣成本取決於您當前的速度，但您也必須朝正確的方向移動。
是否有一種有效的算法來查找到達終點的最快路徑？我還沒有想出比「嘗試每條路徑並檢查結果」更好的東西。 Djikstra和其他簡單算法不起作用，因爲如果他們以不同的初始速度到達，您不能輕易說到中間點的一條路徑比另一條路徑更好或更差。
如果這太容易了，如果您添加了必須停止在終點的要求會怎麼樣？ （即當你到達最後時，你必須小於加速度值。）
編輯：爲了清楚，方向很重要。您在遍歷圖時維護速度矢量，加速度表示向其添加矢量，其大小限制在該點的加速度數上。這意味着在某些情況下，建立巨大的速度是有害的，因爲你將太快以至於不能「轉向」其他有價值的點/目的地。
我認爲你只需要使用每個點的加速度就可以使這個問題在一般情況下完成。想想看，像這樣的輸入：
如果最終點和點的其餘部分之間的「巨大的距離」大到足以稱霸最終解決方案的成本，找到一個最佳的解決方案歸結爲找到一種方法來從圖表的開頭儘可能多地提高速度。如果您只允許每個點傳遞一次，這將相當於哈密爾頓路徑問題，這是NP完整的。
也就是說，你的問題有一些額外的規則（距離是歐幾里得，圖總是完整的），這可能最終導致問題變得更容易。
我不認爲這是哈密頓路徑問題（它可能更難，並不容易），因爲不能保證訪問每個點都是最好的。加速的速度不僅僅是加速......所以如果你不得不改變方向來擊中每一個點，那麼你可能會比它移動得慢得多，如果你擊中了4或5，與你的大致共線目的地。 –
嗯......我想你可能需要明確指定模式，然後在模型中物理如何工作。當我讀到它時，我瞭解到加速度是一個簡單的「速度提升」，使得任何未來邊緣的遍歷都更便宜。 – hugomg
好的，編輯問題使其更清晰。我一直認爲這個方向很重要（所以如果你的速度足夠高，它實際上不會是一個完整的圖）。我認爲我同意在你描述的問題中，在某些情況下它可以歸結爲哈密爾頓路徑。 –
您可以嘗試通過遞歸地追蹤從末端到其他節點的路徑來解決此問題，然後指定沿着該線路的最大速度以便能夠從該節點轉向任何其他節點。如果從當前節點到下一個節點的路徑以較低速度存在，並且從末端花費的時間較少，則這將意味着其他路徑默認情況下更加優化，因爲它可以到達更多節點並且花費更少的時間。一旦路徑達到開始節點，應該根據開始時可達到的最大速度重新計算並存儲。然後你花費更少的時間收集路徑。
您必須在此搜索任何可用路徑，因爲圖上的可用路徑依賴於間接機制的過去狀態，使用更少的速度允許更多選擇。
我不確定我是否理解你的所有答案......介意澄清一些看起來可能對我錯誤的事情？ 「指定沿該線路的最大速度以便能夠從該節點轉向任何其他」聽起來像它失去了太多信息，因爲你可能能夠到達一些節點而不是其他節點，或者到達一些節點，但僅在速度範圍阻止你到達其他人等等。在「如果從當前節點到下一個節點的路徑以較低速度存在，並且從結束花費的時間較少」，那麼選擇規則將會是什麼，你認爲「較低速度」是什麼意思？有時速度很好。 –
關於「最大速度」 - 它可以是每個節點，接近矢量的節點將允許更高的速度。 「較低速度」意味着如果你正在查詢路徑AB，確定在A轉向B時可以達到什麼樣的速度，發現B有一條來自A的路徑，但花費較少的時間到達B AND的速度較慢AB，這意味着你當前的路徑滯後，可以被丟棄。 – Vesper
但我想到了一個警告：如果你從A開始並能夠訪問A來加速，該怎麼辦？如果在A後面有一個節點，那麼這個算法會失敗。Imagine config：B --- A --- C，源碼是A，目標是C，你可以在A處加速5個，在B處加速10個AC很長。正確的道路可能會導致ABAC，比如說，如果你從A到B旅行4，從B到A返回6，然後從A到C返回11，這將比從A直接到C的5快，比去ABC更快。 – Vesper
你將不得不提供更多細節。你的「加速」概念如何工作？它是否通過「加速度數」減少沿路徑的所有邊緣成本？如果你將「加速數」積累得遠遠超過了邊緣成本？引入像「加速度」這樣的概念表明，最好引入相應的摩擦/拖曳概念，否則可能會導致「未檢查的速度」。到目前爲止，我認爲你的問題不足以讓我們制定出適當的解決方案，但是我認爲這很有趣。 – lightalchemist
我懷疑有這個問題的分析解決方案。我首先解決一個更簡單的問題：以給定順序獲得點的最快路線。 （這個搜索空間的維數等於中間點的數量，我看不到比退火更好的方法。）一旦你有了這個方法，你就可以創建一個修改後的Dijkstra。 – Beta
@lightalchemist「加速度」，我的意思是「速度變化」。 （所以，邊緣成本=歐幾里德距離/速度，但只有當你在正確的方向行駛時才允許...所以）未檢查的速度是好的（這是一個數學難題，而不是一個模擬...雖然我做了最初設想它是用來拾取燃料緩衝器的太空船，所以摩擦仍然不會成爲現實。） –