在兩條折線之間有最小面積的網格

Question

我有兩條折線分別爲v和u，分別在3D中有n和m頂點。我想連接v[0]到u[0],v[n-1]到u[m-1]，並且內部頂點也可以以某種方式獲得具有最小表面積的三角形網格條。

我最初的解決方案是通過隨後添加最小對角線來獲得接近最佳的初始網格，然後在每個四邊形中切換對角線（如果它產生更小的區域直到不再可能）。

但恐怕我可以在當地最低，而不是全球的結束。實現最小網格的更好選擇是什麼？

Answer 1

這可以通過動態程序來解決。

讓我們想象的問題作爲一個表，其中列表示第一折線的頂點和所述行表示第二折線的頂點：

0 1 2 3 ... n-1 -> v 
0 
1 
2 
... 
m-1 

每個小區表示折線之間的邊緣。您從(0, 0)開始，並希望通過採取(+1, 0)或(0, +1)步驟來找到到(n-1, m-1)的路徑。你所做的每一步都有一個成本（三角形的面積），並且你想找到導致最小成本的路徑。所以你可以迭代地（僅僅是動態編程的風格）計算到達任何單元所需的成本（通過比較兩個可能的入局方向的結果成本）。記住你選擇的方向，最後你會有一個完整的最低成本路徑。整體運行時間將爲O(n * m)。

如果您知道您的頂點或多或少地分佈得很好，您可以將表格的計算限制爲靠近對角線的幾個條目。這可以使運行時間降至O(k * max(n, m))，其中k是圍繞對角線的可變半徑。但是，如果假設頂點分佈不成立，您可能會錯過最佳解決方案。

你也可以採用類似A *的策略，只在你認爲它可以屬於最小路徑時（在一些啓發式的幫助下）計算一個單元格。