計(jì)算機(jī)算法設(shè)計(jì)與分析--第7章隨機(jī)化算法-展示頁
2024-10-25 14:35本頁面
【正文】 od算法 ?消除最壞行為與特定實(shí)例的聯(lián)系 2021年 11月 12日 10 隨機(jī)化算法的性能分析 ?隨機(jī)化算法分析的特征 ?每次運(yùn)行實(shí)例僅依賴于隨機(jī)選擇 , 不依賴于輸入的分布 ?確定算法的平均復(fù)雜性分析 : 依賴于輸入的分布 ?對于每個輸入都要考慮算法的概率統(tǒng)計(jì)性能 ?隨機(jī)化算法分析的目標(biāo) ?平均時間復(fù)雜性 : 時間復(fù)雜性隨機(jī)變量的均值 ?獲得正確解的概率 ?獲得優(yōu)化解的概率 ?解的精確度估計(jì) 2021年 11月 12日 11 提綱 一、隨機(jī)化概率算法的基本思想 二、隨機(jī)數(shù) 三、數(shù)值隨機(jī)化算法 四、 舍伍德 （ Sherwood） 算法 五、拉斯維加斯（ Las Vegas）算法 六、蒙特卡羅（ Monte Carlo）算法 2021年 11月 12日 12 二、隨機(jī)數(shù) ? 在現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，因此在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)。 2021年 11月 12日 6 隨機(jī)化算法的基本特征 一般情況下，隨機(jī)化算法具有以下基本特征： （ 1）算法的輸入包括兩部分，一部分是原問題的輸入，另一部分是一個供算法進(jìn)行隨機(jī)選擇的 隨機(jī)數(shù)序列 ； （ 2）算法在運(yùn)行過程中，包括一處或若干處 隨機(jī)選擇 ，根據(jù)隨機(jī)值來決定算法的運(yùn)行； （ 3）算法的結(jié)果不能保證一定是正確的，但可以限定其出錯概率； （ 4）算法在不同的運(yùn)行中，對于 相同的輸入實(shí)例可以有不同的結(jié)果 ，因此，對于相同的輸入實(shí)例，概率算法的 執(zhí)行時間可能不同 。 2021年 11月 12日 5 隨機(jī)化算法的基本概念 例如，判斷表達(dá)式 f(x1, x2, …, xn)是否恒等于 0。計(jì)算機(jī)算法設(shè)計(jì)與分析 Design and Analysis of Computer Algorithms 第七章隨機(jī)化 (概率 )算法 Randomized Algorithms 2021年 11月 12日 2 提綱 一、隨機(jī)化算法的基本思想 二、隨機(jī)數(shù) 三、數(shù)值概率算法 四、 舍伍德 （ Sherwood） 算法 五、拉斯維加斯（ Las Vegas）算法 六、蒙特卡羅（ Monte Carlo）算法 2021年 11月 12日 3 提綱 一、隨機(jī)化算法的基本思想
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1