具有扭曲 - 最小停靠點數的圖遍歷算法

Question

我難以忍受這個作業問題。我想我有正確的答案，但我不確定如何證明它。我也不確定如何處理證明。問題如下：

蓋克科教授一直夢想在北達科他州進行直排輪滑。他計劃穿越美國2號公路，從美國明尼蘇達州東部邊界的大福克斯到位於蒙大拿州西部邊界附近的威利斯頓。教授可以攜帶兩升水，在水流失之前他可以滑行m英里。 （因爲北達科他州相對平坦，所以教授不必擔心上坡路段的飲用水量比平坦路段或下坡路段的飲用水量更高）教授將在大福克斯建造兩升全水。他的官方北達科他州地圖顯示了美國2號沿線的所有地方，他可以在這些地方補充水和這些地點之間的距離。

教授的目標是儘量減少水的數量沿着他在全州航線停止。給他一個有效的方法，他可以確定他應該停止停水。證明你的策略產生了一個最佳的解決方案，並給出它的運行時間。

我認爲他應該選擇他的擋板，以便在用完水之前將其移動到最大距離。也就是說，在每一站，如果他要繼續前進，他會在下一站之前用完水。

我不知道如何着手。我敢打賭，這是以前完成的，但我對這個CS領域頗爲陌生，可以使用一些指導。

Answer 1

你的算法是正確的。

試圖證明通過歸納如下傳遞站的數量。 通過每個水位後，沒有其他策略可以減少停站次數，而停站次數相同的站點，沒有其他策略可以爲您留下更多的水。

在0站所有的策略是平等的，所以證明這個陳述是微不足道的。

如果您在此策略下不停止飲酒，結果很容易證明。

如果你在停車時喝酒，由於上一站的聲明是真實的，你可以證明另一個策略是上次停車更多（因此它們不是站在前面，因爲你剛剛得到了水，所以不要在水面上前進），否則另一種策略也必須也有水（否則它們將在下一站之前用完水）。

這足以填寫感應證明。

如果你正在苦苦掙扎什麼需要一個正式的證據概念，以及如何做這些事，看到How I Do Proofs。我還在博客中介紹了我的使用經驗here。

Answer 2

這些各種各樣的問題，關鍵是要陳述問題，另一個問題了，你可以證明一些東西。

例如，對於這一個，你可以形成一個加權圖，其中站是節點，你有兩個節點之間的邊，如果有可能不停止它們之間旅行。然後，你所要做的就是找到圖中最短的路徑，然後你就可以走了。 如果在停止點之間行駛的距離相對較小，這很好，否則圖形變得非常密集。我懷疑有一個更好的問題可以減少，因爲你的路線是一條線。

Answer 3

我希望我的第一次嘗試是真正刪除。那是錯的。

證明素描：如果貪婪失敗了，那一定是最佳的採取一個城市不是一個貪婪的接近起點（進一步從終點線），在某些時候選擇了。忽略直到那個選擇的問題，並且看看兩個子問題：一個從貪婪選擇的城市開始，另一個 - 包括子問題中的貪婪點。爲了避免矛盾，距離終點較遠的城市必須具有較少跳躍的最優解，而不是從貪婪點開始的最優解。忽略這兩個子問題的最佳解決方案，只有它存在。由於非貪婪的起點包括貪婪的子問題，它必須具有相同的最佳子路徑跳數或更多（證明這一點，它可以通過歸納法完成，但我相信有一個更簡單的證據，即我也是如此厭倦考慮，也許你可以說它很明顯？）。如果他們是平等的，那麼貪婪的工作很好。如果他們更大，矛盾。