廣度優先搜索算法方程

我試圖設想像在下面的例子中問題的解決方案：廣度優先搜索算法方程

A != B 
B != C 
D != B 
C != B 
E != D 
E != A

多少個變量是真，多少是假的？據我發現，我應該嘗試使用廣度優先搜索，但我的問題是從哪裏開始，並且該圖將是一個面向對象的事實（我將xi連接到!xj，其中存在相等關係）。有人能指引我朝着正確的方向嗎？

來源

2011-05-14 DDD

繼續這個問題：http://stackoverflow.com/questions/6000632/whats-the-approach-to-solving-this-kind-of-logic-problem和這個問題：http://stackoverflow.com/questions/6003098/boolean-system-for-cc-java – forsvarir 2011-05-14 19:59:11

您誤解了解決方案。它不會是有向圖。！xj不會是一個節點。 xj會。 – 2011-05-14 20:12:45

這是一個圖2着色問題。頂點：A, B, C, …邊緣(u, v)在這個無向圖存在當且僅當u != v。

2着色是廣度優先搜索的應用之一。見：http://en.wikipedia.org/wiki/Breadth-first_search#Testing_bipartiteness

來源

2011-05-14 19:57:20

我不認爲你需要在這裏搜索。如果存在約束xi =！xj，則考慮將約束看作連接頂點xi和xj的圖。取圖的連通分量（即連接每對頂點的路徑）。假設你的約束是一致的（即，不同時指定xi = xj和xi =！xj），那麼你可以選擇組件中的任何頂點xi，並立即確定任何連接的頂點xj是否等於xi或！xi。然後直接計算出需要最大化或最小化真實變量數量的分配。

來源

2011-05-14 22:24:08 Rafe

廣度優先搜索算法方程

回答

相關問題