算法最邊緣交叉口

Question

（有人問之前，這不是功課。）

假設你有2個陣列y0和y1其中

y0 = [1,2,3,4,5,6]和 y1 = [2,1,6,3,4,5]

通知y0[0] = y1[1] = 1，這基本上意味着y0[0]連接到y1[1]。同樣，y0[2] = y1[3] = 3也是「連接」的。

（圖片提供：貝利薩留）

在一個陣列中的每個元件具有第二陣列中的相應條目。 想象陣列中的每個元素爲頂點，並且這些連接爲邊緣從一個陣列繪製到另一個陣列。

我需要找到一組邊緣（最大尺寸），以使「邊緣」（或線條）不會相交。

在上述示例中，通知，

1. Edge 1和Edge 2將相交。
2. Edge 6將與Edge 3, Edge 4, Edge 5相交。

因此，該解決方案可以是爲由於無那些線將相互交叉的1,3,4,5或2,3,4,5（大小= 4）。可以有多種解決方案，但我只需要一個解決方案。

我的問題，是否有任何已知的CS類似這樣的問題？我應該使用什麼算法？

我試着用一個例子來解釋我的問題，但是，如果它仍然不清楚，我會澄清任何疑問。 在此先感謝。

Answer 1

假設沒有元素在單個陣列中重複，這簡直是最長的子序列。

不失一般性，假設第一個數組A1僅爲[1, 2, 3, ..., n]。這個轉換可以在O（n）中用散列集來完成，或者用O（nlogn）用BST來完成。

請注意，我們的設置有交叉，如果只有它是否包含i和j與i < j但j第二列A2（我們知道，因爲這i < j在i A1 j之前出現）的出現i前後。

然後，如果一組沒有交叉，它顯然對應於A2的增加的子序列，反之亦然。

最長的增長子序列有一個簡單的O（n^2）解決方案和一個稍微複雜的O（nlogn）解決方案。

Answer 2

你所描述的是被稱爲 matching problem for bipartite graphs。我懷疑有什麼東西（至今沒有說明），這個問題很難解決。到目前爲止，您還沒有對可以使用哪些邊進行限制。假設有某些邊（不是全部）可用，那些「可能的」邊形成一個圖形，並且您決定使用的邊形成最大匹配。在圖中尋找最大匹配是一個多項式時間算法，並且對於二分情況編碼特別容易。

標題使聽起來好像情況可能會施加某些情況，以致「不相交」的邊緣可能不可行（「最小邊交點」）。也許你想要邊緣覆蓋（或1覆蓋），即每個頂點至少屬於一個邊緣。那麼，如果兩個「頂點」數組長度不同，就不會有「完美匹配」，即匹配也是一個封面。經典結果 Hall's Marriage Theorem表示何時在二分圖中存在完美匹配。如果圖是規則的（所有頂點具有相同的度數），那麼 König's Theorem告訴我們有完美的匹配（以及更多）。

補充：

這可能是值得說明的圖片，似乎要說什麼關於選擇邊緣的限制。兩組頂點的座標爲{（i，0）| i = 1，...，N}和{（j，1）| J = 1，...，N}。當y0 [i] = y1 [j]時，有N個可用邊，連接（i，0）和（j，1）的線段。儘管主題行稱「最小邊交點」，但解決方案是這些邊的最大子集，它不允許交集，最大的 planar straight-line graph包含在給定的 permutation graph中。

它與這裏考慮的2級交叉最小化問題：

An Alternative Method to Crossing Minimization on Hierarchical Graphs -- P. Mutzel

「我們建議......除去最小數量的邊緣，使得所得圖是K-水平平面。在本文中，我們解決了案例k = 2 ... [W] e解決了在給定的2級圖中提取最大權重的2級平面子圖的問題，這個問題是NP難的。

目前的問題在兩個頂點集合中強加了相同數量的點，基本圖形是1級正則，並且在點的編號或定位中不允許選擇。所以不可能斷定它與上述文章中描述的一樣難。然而，它確實將我們引向所謂的「分支和界限」方法，以精確解決這些問題。

讓我們考慮原始問題的「邊緣」作爲新圖的「節點」，如果原始邊相交，則兩個節點相鄰。 [這是一個交集圖的例子。]現在重新解決的問題是找到新圖的 a maximum independent set。這類問題總體上是NP難度的，但我們再次懷疑目前問題的嚴重程度可能不那麼普遍。

一個理由懷疑一個多項式時間算法可能存在是多項式時間近似算法用於平面凸集的有限集合相交曲線的最大獨立子集的可用性：

Independent Set of Intersection Graphs of Convex Objects in 2D -- P. Agarwal and M Mustafa

「在本文中，我們在平面中的線段和凸對象的相交圖上提出了獨立集問題的近似算法。「

關於目前問題的特殊性，似乎可以在多項式時間內解決這個問題還有一種觀察。 A circle graph是可以繪製爲圓的和絃的線段的交集圖。通過攝影論證，可以繪製置換圖的直線邊緣，而不會丟失或引入交叉點。

現在圈圖的最大獨立集問題可以用多項式時間求解。維基百科的文章上面鏈接給出了這樣的參考：

Nash, Nicholas; Gregg, David (2010), "An output sensitive algorithm for computing a maximum independent set of a circle graph", Information Processing Letters 116 (16): 630–634

我還發現，在谷歌圖書此引用：

Valiente, Gabriel (2003), "A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs", Algorithms and computation: 14th Symposium, ISAAC 2003 Kyoto

Answer 3

它基本上是計數反演問題的數量。[來源 - 第5.3節，算法設計，Kleinberg和Tardos。 http://books.google.co.in/books/about/Algorithm_Design.html?id=25p3mHu3ij8C]