最小化凸多邊形三角剖分對角線總和的算法？

將三角測量的成本定義爲已添加的對角線長度的總和。給定一個凸多邊形，其最便宜的三角剖分的成本是多少？如果我們將多邊形視爲一組n個座標：v_1 = x_1，y_1，...，v_n = x_n，y_n且解決方案必須有n-3個對角線（因爲是三角測量而不重疊）最小化凸多邊形三角剖分對角線總和的算法？

我一直試圖獲得這個動態編程問題的復原，但我似乎無法找到一個好的。我並不真正認識到次優結構找到復發。任何人都可以幫我一個忙嗎？

來源

2015-11-29 John DIT

你能解釋一下這和C++有什麼關係嗎？ –

對不起，我試圖找到一個使用C++的解決方案，但我是新來的，只是如果有人想給我一個嘗試，它更熟悉C++ –

這是一個關於算法的問題。無論是用C++，Java，Python，Perl，PHP，Basic還是任何其他圖靈完整編程語言編碼，問題的答案都是一樣的。在弄清楚算法是什麼後，嘗試用C++編寫解決方案，並且遇到某種問題，那麼這將成爲一個C++問題。但不是在那之前。 –

最簡單的方法將遍歷每一個點，得到前一個點和下一個點之間的距離，並與沒有當前點的多邊形遞歸;例如爲五邊形 ABCDE，這將是：

距離 EB +與四邊形 BCDE
距離交流 +遞歸與四邊形 CDEA
距離 BD +遞歸遞歸與四邊形 DEAB
距離 CE +與四邊形 EABC
距離達 +與四邊形 ABCD

爲了不計算相同的解決方案不止一次遞歸，你應該拋棄遞歸任何已經檢查過的點沒有對角線的解決方案;例如當在步驟3中用四邊形 deab遞歸時，具有對角線 eb的解決方案是重複的，因爲在第一步中已經檢查了使用三角形 abe的解決方案。根本沒有重複的計算可能會使這種方法變得複雜。

另一種方法是選擇一個點（以紅色表示在下面的圖），然後枚舉每溶液作爲數量的數字，其總和是 N - 2，其中n是數點。其中每對角穿過所選擇的點的解決方案將是溶液11111然後，通過求和每個組合運行，以 N - 2：11111，1112，1121，113，1211，122，131，14，2111，212 ，221,23,311,32,41和5.大於1的數字表示組合2個或更多分段，並且從其第一個到最後一個點添加對角線。當數字大於2時，此對角線將與您遞歸的左邊多邊形（用粉紅色表示）相鄰。

的動畫顯示的迭代和遞推算法經過爲7點多邊形，直至在那裏它與6點多邊形遞歸的點。

這兩種方法提供記憶化和製表可能性，但它不會是簡單的。一旦你開始遞歸，從b點開始的五邊形不一定是 bcdef;它很可能是 bdfhj。因此，檢索存儲的中間結果可能會有點複雜。

來源

2015-11-30 04:29:27 m69

謝謝！我也在考慮第一種方法，但是我很難像你說的那樣檢索結果。如果我達到目標，我會用我的解決方案進行更新 –

最小化凸多邊形三角剖分對角線總和的算法？

回答

相關問題