概率算法ppt課件(編輯修改稿)
2025-05-28 02:28 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 點(diǎn)中有一半同時(shí)具有 i+1級(jí)指針。為了維持跳躍表的平衡性，可以事先確定一個(gè)實(shí)數(shù) 0p1，并要求在跳躍表中維持在具有 i級(jí)指針的結(jié)點(diǎn)中同時(shí)具有 i+1級(jí)指針的結(jié)點(diǎn)所占比例約為 p。為此目的，在插入一個(gè)新結(jié)點(diǎn)時(shí)，先將其結(jié)點(diǎn)級(jí)別初始化為 0，然后用隨機(jī)數(shù)生成器反復(fù)地產(chǎn)生一個(gè) [0， 1]間的隨機(jī)實(shí)數(shù) q。如果 qp，則使新結(jié)點(diǎn)級(jí)別增加 1，直至 q?p。由此產(chǎn)生新結(jié)點(diǎn)級(jí)別的過(guò)程可知，所產(chǎn)生的新結(jié)點(diǎn)的級(jí)別為 0的概率為 1p，級(jí)別為 1的概率為p(1p)， … ，級(jí)別為 i的概率為 pi(1p)。如此產(chǎn)生的新結(jié)點(diǎn)的級(jí)別有可能是一個(gè)很大的數(shù)，甚至遠(yuǎn)遠(yuǎn)超過(guò)表中元素的個(gè)數(shù)。為了避免這種情況，用 作為新結(jié)點(diǎn)級(jí)別的上界。其中 n是當(dāng)前跳躍表中結(jié)點(diǎn)個(gè)數(shù)。當(dāng)前跳躍表中任一結(jié)點(diǎn)的級(jí)別不超過(guò) np/1lognp/1log13 拉斯維加斯 ( Las Vegas )算法 拉斯維加斯算法的一個(gè)顯著特征是它所作的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。 public static void obstinate(Object x, Object y) {// 反復(fù)調(diào)用拉斯維加斯算法 LV(x,y)，直到找到問(wèn)題的一個(gè)解 y boolean success= false。 while (!success) success=lv(x,y)。 } 設(shè) p(x)是對(duì)輸入 x調(diào)用拉斯維加斯算法獲得問(wèn)題的一個(gè)解的概率。一個(gè)正確的拉斯維加斯算法應(yīng)該對(duì)所有輸入 x均有 p(x)0。 設(shè) t(x)是算法 obstinate找到具體實(shí)例 x的一個(gè)解所需的平均時(shí)間 ,s(x)和 e(x)分別是算法對(duì)于具體實(shí)例 x求解成功或求解失敗所需的平均時(shí)間，則有： 解此方程可得： ))()())((1()()()( xtxexpxsxpxt ????)()( )(1)()( xexp xpxsxt ???14 n后問(wèn)題 對(duì)于 n后問(wèn)題的任何一個(gè)解而言，每一個(gè)皇后在棋盤(pán)上的位置無(wú)任何規(guī)律，不具有系統(tǒng)性，而更象是隨機(jī)放置的。由此容易想到下面的 拉斯維加斯算法 。 在棋盤(pán)上相繼的各行中隨機(jī)地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至 n個(gè)皇后均已相容地放置好，或已沒(méi)有下一個(gè)皇后的可放置位置時(shí)為止。 如果將上述隨機(jī)放置策略與回溯法相結(jié)合，可能會(huì)獲得更好的效果?？梢韵仍谄灞P(pán)的若干行中隨機(jī)地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個(gè)解或宣告失敗。隨機(jī)放置的皇后越多，后繼回溯搜索所需的時(shí)間就越少，但失敗的概率也就越大。 stopVegas p s e t 0 5 12 15 整數(shù)因子分解 設(shè) n1是一個(gè)整數(shù)。關(guān)于整數(shù) n的因子分解問(wèn)題是找出 n的如下形式的惟一分解式： 其中， p1p2…p k是 k個(gè)素?cái)?shù)， m1,m2,…,m k是 k個(gè)正整數(shù)。 如果 n是一個(gè)合數(shù)，則 n必有一個(gè)非平凡因子 x， 1xn，使得 x可以整除 n。 給定一個(gè)合數(shù) n，求 n的一個(gè)非平凡因子的問(wèn)題稱(chēng)為整數(shù) n的因子分割問(wèn)題。 kmkmm pppn ?21 21?private static int split(int n) { int m = (int) (((double)n))。 for (int i=2。 i=m。 i++) if (n%i==0) return i。 return 1。 } 事實(shí)上，算法 split(n)是對(duì)范圍在 1～ x的所有整數(shù)進(jìn)行了試除
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1