《算法設(shè)計(jì)與分析》第七章隨機(jī)算法及計(jì)算復(fù)雜性.ppt

第 七 章 隨 機(jī) 算 法 及 NP完 全 問 題 l 7.1 隨 機(jī) 算 法 引 言l 7.2 隨 機(jī) 算 法 的 類 型l 7.3 隨 機(jī) 數(shù) 發(fā) 生 器l 7.4 數(shù) 值 概 率 算 法l 7.5 舍 伍 德 (Sherwood)算 法l 7.6 拉 斯 維 加 斯 （ Las Vegas） 算 法l 7.7 蒙 特 卡 羅 （ Monte Carlo） 算 法l 7.8 NP完 全 問 題 7.1 隨 機(jī) 算 法 引 言l 確 定 性 的 算 法 ： 算 法 的 每 一 個(gè) 計(jì) 算 步 驟 都 是 確 定 的 ， 對 于 相 同 的 輸 出 ， 每 一 次 執(zhí) 行 過 程 都 會(huì) 產(chǎn) 生 相 同 的輸 出 。l 隨 機(jī) 算 法 ： 非 形 式 描 述 隨 機(jī) 算 法 為 使 用 隨 機(jī) 函 數(shù) 產(chǎn) 生 器 的 算 法 。 算 法 中 的一 些 判 定 依 賴 于 隨 機(jī) 函 數(shù) 產(chǎn) 生 器 的 輸 出 。 隨 機(jī) 算 法 對 于 相 同 的 輸 入 ， 在 不 同 的 運(yùn) 行 過 程 中 會(huì)得 到 不 同 的 輸 出 。 對 于 相 同 的 輸 入 ， 隨 機(jī) 算 法 的 執(zhí) 行 時(shí) 間 也 可 能 隨 不同 的 運(yùn) 行 過 程 而 不 同 。 8.1 隨 機(jī) 算 法 引 言l 隨 機(jī) 算 法 的 優(yōu) 點(diǎn) ： 1、 執(zhí) 行 時(shí) 間 和 空 間 ， 小 于 同 一 問 題 的 已 知 最 好 的 確 定 性 算 法 ； 2、 實(shí) 現(xiàn) 比 較 簡 單 ， 容 易 理 解 。 l 很 多 確 定 性 的 算 法 ， 其 性 能 很 壞 。 可 用 隨 機(jī) 選 擇 的 方法 來 改 善 算 法 的 性 能 。l 某 些 方 面 可 能 不 正 確 ， 對 特 定 的 輸 入 ， 算 法 的 每 一 次運(yùn) 行 不 一 定 得 到 相 同 結(jié) 果 。 出 現(xiàn) 這 種 不 正 確 的 可 能 性很 小 ， 以 致 可 以 安 全 地 不 予 理 睬 。 7.2 隨 機(jī) 算 法 的 類 型 l 數(shù) 值 概 率 算 法l 拉 斯 維 加 斯 （ Las Vegas） 算 法l 蒙 特 卡 羅 （ Monte Carlo） 算 法l 舍 伍 德 （ Sherwood） 算 法 。 7.2 隨 機(jī) 算 法 的 類 型l 1、 數(shù) 值 概 率 算 法 ： 用 于 數(shù) 值 問 題 的 求 解 。 所得 到 的 解 幾 乎 都 是 近 似 解 ， 近 似 解 的 精 度 隨 著計(jì) 算 時(shí) 間 的 增 加 而 不 斷 地 提 高 。l 2、 舍 伍 德 （ Sherwood） 算 法 ： 很 多 具 有 很 好的 平 均 運(yùn) 行 時(shí) 間 的 確 定 性 算 法 ， 在 最 壞 的 情 況下 性 能 很 壞 。 引 入 隨 機(jī) 性 加 以 改 造 ， 可 以 消 除或 減 少 一 般 情 況 和 最 壞 情 況 的 差 別 。 7.2 隨 機(jī) 算 法 的 類 型l 3、 拉 斯 維 加 斯 （ Las Vegas） 算 法 ： 要 么 給出 問 題 的 正 確 答 案 ， 要 么 得 不 到 答 案 。 反 復(fù) 求解 多 次 ， 可 使 失 效 的 概 率 任 意 小 。l 4、 蒙 特 卡 羅 （ Monte Carlo） 算 法 ： 總 能 得 到問 題 的 答 案 ， 偶 然 產(chǎn) 生 不 正 確 的 答 案 。 重 復(fù) 運(yùn)行 ， 每 一 次 都 進(jìn) 行 隨 機(jī) 選 擇 ， 可 使 不 正 確 答 案的 概 率 變 得 任 意 小 。 7.3 隨 機(jī) 數(shù) 發(fā) 生 器 l 產(chǎn) 生 隨 機(jī) 數(shù) 的 公 式 ： 產(chǎn) 生 065535的 隨 機(jī) 數(shù) 序 列 ， b、 c、 d為 正 整 數(shù) ， 稱 為 所 產(chǎn) 生 的 隨 機(jī) 序 列 的 種 子 。 常 數(shù) b、 c， 對 所 產(chǎn) 生 的 隨 機(jī) 序 列 的 隨 機(jī) 性 能 有 很 大 的關(guān) 系 ， b通 常 取 一 素 數(shù) 。 , 21 aa,2,165536/ 10 nda cdbd dd nn nn 7.3 隨 機(jī) 數(shù) 發(fā) 生 器l #define MULTIPLIER 0 x015A4E35L;l #define INCREMENT 1;l static unsigned long seed;l void random_seed(unsigned long d)l l if (d=0)l seed = time(0);l elsel seed = d; l l unsigned int random(unsigned long low,unsigned long high)l l seed = MULTIPLIER * seed + INCREMENT;l return (seed 16) % (high low) + low);l 7.4 l 設(shè) 有 一 半 徑 為 r的 圓 及 其 外 切 四 邊 形 。 向 該 正方 形 隨 機(jī) 地 投 擲 n個(gè) 點(diǎn) 。 設(shè) 落 入 圓 內(nèi) 的 點(diǎn) 數(shù) 為 k。由 于 所 投 入 的 點(diǎn) 在 正 方 形 上 均 勻 分 布 ， 因 而 所投 入 的 點(diǎn) 落 入 圓 內(nèi) 的 概 率 為 。 所 以 當(dāng) n足 夠 大 時(shí) ， k與 n之 比 就 逼 近 這 一 概 率 。 從 而44 22 rrnk4 7.4 l public double darts(int n)l / 用 隨 機(jī) 投 點(diǎn) 法 計(jì) 算 值l int k=0;l for (int i=1;i =n;i+) l double x=dart.fRandom();l double y=dart.fRandom();l if (x*x+y*y)=1) k+;l l return 4*k/(double)n; l 一 、 確 定 性 算 法 的 平 均 運(yùn) 行 時(shí) 間l TA(x) ： 確 定 性 算 法 對 輸 入 實(shí) 例 的 運(yùn) 行 時(shí) 間 。l Xn ： 規(guī) 模 為 的 所 有 輸 入 實(shí) 例 全 體 。l 算 法 的 平 均 運(yùn) 行 時(shí) 間 ：l 存 在 實(shí) 例 ， 。l 例 ： 快 速 排 序 算 法l 當(dāng) 輸 入 數(shù) 據(jù) 均 勻 分 布 時(shí) ， 運(yùn) 行 時(shí) 間 是 。l 當(dāng) 輸 入 數(shù) 據(jù) 按 遞 增 或 遞 減 順 序 排 列 時(shí) ， 算 法 的 運(yùn) 行 時(shí)間 變 壞 |/)()( nXx AA XxTnT nnXx )()( nTxT AA )log( nn 二 、 舍 伍 德 算 法 的 基 本 思 想 消 除 不 同 輸 入 實(shí) 例 對 算 法 性 能 的 影 響 ， 使 隨 機(jī) 算 法 對規(guī) 模 為 的 每 一 個(gè) 實(shí) 例 ， 都 有 ：三 、 期 望 運(yùn) 行 時(shí) 間 ：l 當(dāng) s(n)與 相 比 很 小 可 以 忽 略時(shí) ， 舍 伍 德 算 法 有 很 好 的 性 能 。l 對 所 有 輸 入 實(shí) 例 而 言 ， 運(yùn) 行 時(shí) 間 相 對 均 勻 。 時(shí) 間 復(fù) 雜 性與 確 定 性 算 法 的 時(shí) 間 復(fù) 雜 性 相 當(dāng) . )()()( nsnTxT AB |/)()( nXx BB XxTnT n)()()( nsnTnT AB )( nT A l 隨 機(jī) 快 速 排 序 算 法 l 算 法 9.1 隨 機(jī) 選 擇 樞 點(diǎn) 的 快 速 排 序 算 法l 輸 入 ： 數(shù) 組 A,數(shù) 組 元 素 的 的 起 始 位 置 low,終 止 位 置 highl 輸 出 ： 按 非 降 順 序 排 序 的 數(shù) 組 Al 1. template l 2. void quicksort_random(Type A,int low,int high)l 3. l 4. random_seed(0);/* 選 擇 系 統(tǒng) 當(dāng) 前 時(shí) 間 作 為 隨 機(jī) 數(shù) 種 子 */l 5. r_quicksort(A,low,high);/* 遞 歸 調(diào) 用 隨 機(jī) 快 速 排 序 算 法 */l 6. l 1. void r_quicksort(Type A,int low,int high)l 2. l 3. int k;l 4. if (low0， 使 得 對 的 所 有 實(shí) 例 p， 都 有p(x)= ， 則 失 敗 的 概 率 小 于 1- 。l 連 續(xù) 運(yùn) 行 k次 ， 失 敗 的 概 率 降 低 為 (1- )k。l k充 分 大 ， (1- )k趨 于 0。 7.6 拉 斯 維 加 斯 （ Las Vegas） 算 法l 例 ： 識(shí) 別 重 復(fù) 元 素l 考 慮 一 個(gè) 有 n個(gè) 數(shù) 字 的 數(shù) 組 a， 其 中 有 n/2個(gè) 不同 的 元 素 ， 其 余 元 素 是 另 一 個(gè) 元 素 的 拷 貝 ， 即數(shù) 組 中 共 有 （ n/2） +1個(gè) 不 同 的 元 素 。 問 題 是要 識(shí) 別 重 復(fù) 的 元 素 。l 確 定 性 算 法 ：至 少 需 要 （ n/2） +2個(gè) 時(shí) 間 步 。 7.6 拉 斯 維 加 斯 （ Las Vegas） 算 法l 拉 斯 維 加 斯 （ Las Vegas） 算 法 int RepeatedElement(Type a,int n)while (1)int i=random()%n+1;int j= random()%n+1;if(i!=j) 7.6 拉 斯 維 加 斯 （ Las Vegas） 算 法l while循 環(huán) 則 任 何 一 次 迭 代 中 退 出 的 概 率 為p= .當(dāng) n 10時(shí) ， p 1/5,則 不 退 出 的 概 率 4/5。l 算 法 在 前 calogn(c為 固 定 常 數(shù) )次 迭 代 內(nèi) 不 退 出 的概 率 (4/5) calogn=n-calog(4/5),若 取 c 1/log(5/4),則 其值 n-a,l 因 此 ， 算 法 在 calogn次 迭 代 以 內(nèi) 終 止 的 概 率 1- n -a。 每 次 迭 代 花 費(fèi) O(1)的 時(shí) 間 ， 算 法 的 執(zhí) 行 時(shí) 間為 O(logn)。2 )12(2 nnn 7.7 蒙 特 卡 羅 （ Monte Carlo） 算 法 l 蒙 特 卡 羅 算 法 則 在 一 般 情 況 下 可 以 保 證 對 問 題的 所 有 實(shí) 例 都 以 高 概 率 給 出 正 確 解 ， 但 是 通 常無 法 判 定 一 個(gè) 具 體 解 是 否 正 確 。l 設(shè) p是 一 個(gè) 實(shí) 數(shù) ， 且 1/2p1。 如 果 一 個(gè) 蒙 特卡 羅 算 法 對 于 問 題 的 任 一 實(shí) 例 得 到 正 確 解 的 概率 不 小 于 p， 則 稱 該 蒙 特 卡 羅 算 法 是 p正 確 的 ，且 稱 p-1/2是 該 算 法 的 優(yōu) 勢 。l 如 果 對 于 同 一 實(shí) 例 ， 蒙 特 卡 羅 算 法 不 會(huì) 給 出 2個(gè) 不 同 的 正 確 解 答 ， 則 稱 該 蒙 特 卡 羅 算 法 是 一致 的 。 7.7 蒙 特 卡 羅 （ Monte Carlo） 算 法l 數(shù) 組 的 主 元 素 問 題 一 、 問 題ln個(gè) 元 素 的 數(shù) 組 A， A中 元 素 x， 若 A中 一 半 以 上 元 素與 x相 同 ， 稱 x是 A的 主 元 素 。l例 ： 序 列 1,3,2,3,3,4,3中 ， 元 素 3是 主 元 素 。二 、 一 般 方 法l每 個(gè) 元 素 和 其 它 元 素 比 較 ， 并 計(jì) 數(shù) 。 如 果 計(jì) 數(shù) 值 大于 n /2， 該 元 素 就 是 的 主 元 素 。 l元 素 比 較 次 數(shù) 為 。 )( 2n 7.7 蒙 特 卡 羅 （ Monte Carlo） 算 法l 三 、 蒙 特 卡 羅 算 法l 1、 隨 機(jī) 選 擇 元 素 Ai進(jìn) 行 測 試 ， 若 返 回 true， Ai就 是 主 元 素 ； 否 則 不 是 主 元 素 。 7.7 蒙 特 卡 羅 （ Monte Carlo） 算 法l 算 法 9.7 求 數(shù) 組 A的 主 元 素l 輸 入 ： n個(gè) 元 素 的 數(shù) 組 Al 輸 出 ： 數(shù) 組 A的 主 元 素 BOOL majority(Type A,Type random_seed(0); i = random(0,n-1) ; k = 0;for (j=0;jn/2) x = Ai; return TRUE; else return FALSE; 7.7 蒙 特 卡 羅 （ Monte Carlo） 算 法l 2、 如 果 存 在 主 元 素 ， 以 大 于 1/2的 概 率 返 回true， 小 于 1/2的 概 率 返 回 false。l 連 續(xù) 運(yùn) 行 k次 ， 返 回 的 概 率 減 少 為 2-k， 算 法 錯(cuò)誤 的 概 率 為 2-k 。l 希 望 錯(cuò) 誤 概 率 小 于 ， 則 令 ： 2-k = l k=log(1/ )l 算 法 修 改 為 ： 7.7 蒙 特 卡 羅 （ Monte Carlo） 算 法l BOOL majority_monte(Type A,Type BOOL flag = FALSE;l random_seed(0); s = log(1/e);l for (t=1;t=s;t+) l i = random(0,n-1) ; k = 0;l for (j=0;jn/2) x = Ai; flag = TRUE; break; l l return flag;l l 算 法 的 錯(cuò) 誤 概 率 小 于 所 給 參 數(shù) e。 算 法 的 運(yùn) 行 時(shí) 間 為 O(nlog(1/e) 。 7.7 蒙 特 卡 羅 （ Monte Carlo） 算 法l 素 數(shù) 測 試 一 、 一 般 方 法 被 測 試 的 數(shù) 除 以 2到 的 數(shù) ， 余 數(shù) 為 0， 是 合 數(shù) ，否 則 是 素 數(shù) 。二 、 蒙 特 卡 羅 算 法 n ：對于給定的正整數(shù)n，判定n是一個(gè)素?cái)?shù)的充要條件是(n-1)! -1(mod n)。：如果p是一個(gè)素?cái)?shù)，且0ap，則ap-1(mod p)。 ：如果p是一個(gè)素?cái)?shù)，且0 xp，則方程x21(mod p)的解為x=1，p-1。int power(int a, int p, int n) / 計(jì)算 ap mod n，并實(shí)施對n的二次探測 int x, result; if (p=0) result=1; else x=power(a,p/2,n); / 遞歸計(jì)算 result=(x*x)%n; / 二次探測 if (result=1) if (p%2)=1) / p是奇數(shù) result=(result*a)%n; return result; boolean prime(int n) / 素?cái)?shù)測試的蒙特卡羅算法 rnd = new Random(); int a, result; composite=false; a=rnd.random(n-3)+2; result=power(a,n-1,n); if (composite|(result!=1) return false; else return true;算法prime是一個(gè)偏假3/4正確的蒙特卡羅算法。通過多次重復(fù)調(diào)用錯(cuò)誤概率不超過(1/4)k。這是一個(gè)很保守的估計(jì)，實(shí)際使用的效果要好得多。 7.8 NP難 與 NP完 全 問 題l 一 、 易 解 的 問 題 和 難 解 的 問 題l存 在 多 項(xiàng) 式 時(shí) 間 算 法 的 問 題 ， 稱 為 易 解 的 問 題l指 數(shù) 時(shí) 間 算 法 或 排 列 時(shí) 間 算 法 的 問 題 ， 稱 為 難 解 的問 題l 二 、 難 解 問 題 的 計(jì) 算 相 關(guān) 性l計(jì) 算 相 關(guān) ： 某 類 問 題 可 以 歸 約 為 另 一 類 問 題l計(jì) 算 相 關(guān) 的 問 題 ， 若 它 們 之 一 可 用 多 項(xiàng) 式 時(shí) 間 求 解 ，則 其 它 同 類 問 題 也 可 用 多 項(xiàng) 式 時(shí) 間 求 解 ； 若 它 們 之一 肯 定 不 存 在 多 項(xiàng) 式 時(shí) 間 算 法 ， 則 同 類 的 其 它 問 題 ，也 肯 定 不 會(huì) 找 到 多 項(xiàng) 式 時(shí) 間 算 法 。 7.8 NP難 與 NP完 全 問 題P類 和 NP類 問 題 l 定 義 12.1 是 問 題 的 一 個(gè) 算 法 。 如 果 在 處 理 問題 的 實(shí) 例 時(shí) ， 在 算 法 的 整 個(gè) 執(zhí) 行 過 程 中 ， 每 一步 只 有 一 個(gè) 確 定 的 選 擇 ， 就 說 算 法 是 確 定 性 的算 法 。 l 定 義 12.2 如 果 對 某 個(gè) 判 定 問 題 ， 存 在 著 一 個(gè)非 負(fù) 整 數(shù) k， 對 輸 入 規(guī) 模 為 n的 實(shí) 例 ， 能 夠 以O(shè)( nk)的 時(shí) 間 運(yùn) 行 一 個(gè) 確 定 性 的 算 法 ， 得 到y(tǒng)es或 no的 答 案 ， 則 該 判 定 問 題 是 一 個(gè) p類 判定 問 題 。 7.8 NP難 與 NP完 全 問 題 P類 和 NP類 問 題 l 定 義 12.5 如 果 對 某 個(gè) 判 定 問 題 ， 存 在 著 一 個(gè)非 負(fù) 整 數(shù) k， 對 輸 入 規(guī) 模 為 n的 實(shí) 例 ， 能 夠 以O(shè)( nk)的 時(shí) 間 運(yùn) 行 一 個(gè) 非 確 定 性 的 算 法 ， 得 到y(tǒng)es或 no的 答 案 ， 則 該 判 定 問 題 是 一 個(gè) NP類判 定 問 題 。l 特 性 ：存 在 確 定 性 的 算 法 ， 能 夠 以 多 項(xiàng) 式 時(shí) 間 ， 來 檢查 和 驗(yàn) 證 在 推 測 階 段 產(chǎn) 生 的 答 案 。 7.8 NP難 與 NP完 全 問 題NP難 問 題l NP難l 定 義 12.6 令 是 一 個(gè) 判 定 問 題 ， 如 果 對 NP中的 每 一 個(gè) 問 題 NP ， 有 ， 就 說判 定 問 題 是 一 個(gè) NP難 題 。 p 7.8 NP難 與 NP完 全 問 題NP完 全 問 題l NP完 全 問 題 l 定 義 12.7 令 是 一 個(gè) 判 定 問 題 ， 如 果 ：l (1) NP ， 并 且 ：l (2) 對 NP中 的 所 有 問 題 NP ， 都 有 ；則 稱 判 定 問 題 是 NP完 全 的 。 p 7.8 NP難 與 NP完 全 問 題l NP難 題 和 NP完 全 問 題 的 差 別l 是 NP完 全 問 題 ， 是 NP難 題 ，l 則 必 定 在 NP類 中 ， 而 不 一 定 在 NP類 中 。 7.8 NP難 與 NP完 全 問 題l 1、 歸 約 的 傳 遞 性 l 定 理 12.3 令 、 和 是 三 個(gè) 判 定 問 題 ，滿 足 ， 及 ， 則有 。 p p p 7.8 NP難 與 NP完 全 問 題l NP完 全 問 題 的 特 性 l 定 理 12.4 令 和 是 NP中 的 兩 個(gè) 問 題 ，使 得 。 如 果 是 NP完 全 的 ，則 也 是 NP完 全 的 。 p 7.8 NP難 與 NP完 全 問 題l NP完 全 問 題 的 證 明 ： l 證 明 下 面 兩 件 事 情 ： l (1) ， 并 且 ： l (2) 存 在 一 個(gè) NP完 全 問 題 ， 使 得 ； NP p 7.8 NP難 與 NP完 全 問 題l 定 理 12.5（ Cook定 理 ） 可 滿 足 性 問 題SATISFIABILITY是 NP完 全 的 。l Cook定 理 的 意 義 ：l Cook定 理 給 出 了 第 一 個(gè) NP完 全 問 題 ， 使 得 對任 何 問 題 ， 只 要 能 夠 證 明 ， 并 且SATISFIABILITY ， 那 么 ， 就 是NP完 全 的 NP p 7.8 NP難 與 NP完 全 問 題 l 部 分 的 NP完 全 問 題 樹 7.8 NP難 與 NP完 全 問 題l 通 常 認(rèn) 為 的 P、 NP、 NP Complete、 NP Hard問 題 的 關(guān) 系 ：P NP NP Complete NP Hard 7.8 NP難 與 NP完 全 問 題l NP完 全 問 題 的 特 性 為 ： 當(dāng) 且 僅 當(dāng) 所 有 其 它 NP完 全 問 題 可 以 在 多 項(xiàng) 式 時(shí) 間 內(nèi) 求 解 ， 該 問 題 可以 在 多 項(xiàng) 式 時(shí) 間 內(nèi) 求 解 。l 如 果 一 個(gè) NP難 問 題 可 以 在 多 項(xiàng) 式 時(shí) 間 內(nèi) 求 解 ，則 所 有 的 NP完 全 問 題 都 可 以 在 多 項(xiàng) 式 時(shí) 間 內(nèi)求 解 。l NP完 全 和 NP難 問 題 都 不 是 多 項(xiàng) 式 時(shí) 間 可 解 的 。