由對(duì)稱(chēng)性解2-sat問(wèn)題(已修改)
2025-08-01 03:33 本頁(yè)面
【正文】 由對(duì)稱(chēng)性解 2SAT問(wèn)題 2SAT: ? 2SAT就是 2判定性問(wèn)題，是一種特殊的邏輯判定問(wèn)題。 ? 2SAT問(wèn)題有何特殊性？該如何求解？ ? 我們從一道例題來(lái)認(rèn)識(shí) 2SAT問(wèn)題，并提出對(duì)一類(lèi) 2SAT問(wèn)題通用的解法。 Poi 0106 Peaceful Commission [和平委員會(huì) ] ? 某國(guó)有 n個(gè)黨派，每個(gè)黨派在議會(huì)中恰有 2個(gè)代表。 ? 現(xiàn)在要成立和平委員會(huì) ，該會(huì)滿(mǎn)足： ? 每個(gè)黨派在和平委員會(huì)中有且只有一個(gè)代表 ? 如果某兩個(gè)代表不和，則他們不能都屬于委員會(huì) ? 代表的編號(hào)從 1到 2n，編號(hào)為 2a 2a的代表屬于第 a個(gè)黨派 ? 輸入 n（黨派數(shù)）， m（不友好對(duì)數(shù)）及 m對(duì)兩兩不和的代表編號(hào) ? 其中 1≤n≤8000， 0≤m ≤20220 ? 求和平委員會(huì)是否能創(chuàng)立。 ? 若能，求一種構(gòu)成方式。 例：輸入： 3 2 輸出： 1 1 3 4 2 4 5 分析： ? 原題可描述為： 有 n個(gè)組，第 i個(gè)組里有兩個(gè)節(jié)點(diǎn) Ai, Ai39。 。需要從每個(gè)組中選出一個(gè)。而某些點(diǎn)不可以同時(shí)選出（稱(chēng)之為不相容）。任務(wù)是保證選出的 n個(gè)點(diǎn)都能兩兩相容。 ?（在這里把 Ai, Ai39。 的定義稍稍放寬一些，它們同時(shí)表示屬于同一個(gè)組的兩個(gè)節(jié)點(diǎn)。也就是說(shuō)，如果我們描述 Ai，那么描述這個(gè)組的另一個(gè)節(jié)點(diǎn)就可以用 Ai39。） 初步構(gòu)圖 ? 如果 Ai與 Aj不相容，那么如果選擇了 Ai，必須選擇Aj‘ ；同樣，如果選擇了 Aj，就必須選擇 Ai’ 。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1