（N x M）圖解問題

我需要一個算法來（有效地）解決我寫的一些圖表軟件中出現的問題。（N x M）圖解問題

我有兩組節點，N和M.N中的每個節點n0與M中的唯一（對於n0）節點具有0到M個連接。這些節點組將被安排在兩條平行的水平線上， N個節點在M個節點的上方。該連接將被畫成直線，從N到M.

我需要做的是他們的水平線內重新排列N和M節點，以減少交叉。他們是否有辦法做到這一點，比僅僅列舉所有可能的安排，即O（N！* M！）更有效率？（實際上，它比它差得多，因爲每個連接都必須檢查穿越）。

參考相關文獻，歡迎此外，雖然一個解釋，爲什麼它的相關需要。

正如已經指出的那樣，在此可以被認爲是二分圖（集合N和M）平坦化算法的一般情況。然而，這個特定問題大大超過該限制的（我希望能使其更快），並需要產生的附加信息（這可能使慢），具體如下：

圖的限制是的連接必須被繪製爲直線從N等於M.在圖論中，這實際上意味着該連接不能去後面在N或者M的節點，僅在它們之間。因此，具有四個連接器的2x2機箱可以在一般的二分圖機箱中平面化，但在我的示意圖中，不能爲。
的附加信息，是，如果它不能被平坦化，我還需要一個最小的交叉溶液（或接近）。一般來說，最小交叉算法與僅平面化算法顯着不同。

你描述的模型叫做二分圖，你要求的是平面化算法。回答你的問題的最好方法是谷歌一點。

2011-04-10 12:46:12 iehrlich

是的，這是一個二分圖，感謝提醒。然而，繪圖和繪圖並不是完全相同的東西，這並不是嚴格意義上的平面化算法的要求，因爲繪圖約束顯着受限於此。 – RBarryYoung 2011-04-10 14:54:59

我理解這個問題，但我看到算法要求非常不通用，我只是指出了算法本身的缺陷方向。你可能會喜歡的是基於N個元素的M集覆蓋的N集合枚舉的平衡樹搜索算法（也許是貪婪的算法）。 – iehrlich 2011-04-10 15:06:11

我在考慮這個。任何想法多麼接近這樣的方法會達到一個最佳的解決方案，平均？ – RBarryYoung 2011-04-10 15:14:50

suddnely_me是正確的，但也許你並不需要一個完美的解決方案。你也可以嘗試一個非常簡單的貪婪算法。根據連接數排序所有節點。然後添加一個接一個水平線..通過雖然沒有想過..但可能會導致一個簡單的方法..

2011-04-10 13:04:40 duedl0r

任何想法多麼接近這樣的方法會達到最佳解決方案，平均而言？ – RBarryYoung 2011-04-10 15:14:03

嗯...可能不是那麼好..我無法證明它，我想這不是微不足道的:)這只是一種貪婪算法可能不會完全不好的感覺，因爲你說你連接性低。 – duedl0r 2011-04-10 18:24:56

我認爲你的問題相當複雜，所以你也可以選擇遺傳算法。缺點是，每次重新計算後，你的圖表看起來都不一樣:) – duedl0r 2011-04-10 18:26:39

如何大是N和M？有一種基於動態編程的解決方案，它的運行時間爲O（min（N，M）！* 2 ** max（N，M）* poly（N，M）），但我不確定這是否顯着改善在你看來，這是蠻橫的。

2011-04-10 16:56:32 zxc

通常在10到99的範圍內，並且它需要在典型的PC（圖2ghz）上運行5秒或更短的時間。好消息是平均連通性很低，大約2個節點（2 *（N + M））。所以，我可以吸收一些壞處（表現明智），但不是很多。 – RBarryYoung 2011-04-10 18:05:34

您的問題可以用武力圖形排列來解決，只要你不要求的節點保持一個特定位置上的線（即使你需要一些改變，你可以把它關閉）

您需要更改的主要是使力對準1D而不是2D，僅在X和Y的排列在X節點軸，而不是對準節點

該算法的前提是，你有力量作用於節點，所以節點具有斥力作用於它們，使它們彼此遠離地移動，但是彼此連接的節點具有作用於它們的吸引力這比排斥更大。在每一個循環中，你都會增加力量，使得彼此吸引的節點相互靠近，而不是相互排斥的節點，當總和低於某個閾值的總力量時，就會完成對齊，類似於0.001。

2012-10-21 03:20:09

回答