• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2011年12月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            統計

            • 隨筆 - 182
            • 文章 - 1
            • 評論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            算法設計4——貪心算法(3)

            1 聚類問題:最大間隔的K聚類。我們定義一個K聚類的間隔是處在不同聚類中的任意一對點之間的最小距離。一個自然的目標是尋求具有最大可能間隔的k聚類。

            這個問題的算法與Kruskal算法非常相似,首先每一個點都是一個聚類,然后依次按照Kruskal進行計算。。。相當于在Kruskal中刪除了k-1條最貴的邊。

            2  假設給定一個連通圖G,假定邊的費用都是不同的,G有n個頂點和m條邊,指定了G的一條特定的邊e,給出一個運行時間在O(m+n)的算法來確定e是否包含在G的一棵最小生成樹里。

            算法現在就已經很顯然了,我們通過從G中刪除所有權比e大的邊,(包括e)然后使用看一下e中的兩個端的是否聯通。當前僅當沒有這樣一條路徑的時候,e屬于一棵最小生成樹。

            3 看一下最小生成樹的兩個性質: 

            割性質:當e是從某個集合S跨到補集V-S的最便宜的邊,那么它在每一顆最小生成樹里。

            圈性質:如果e是某個圈C上最貴的邊,那么它不在最小生成樹里。

            4 一個課后問題:

            給定一個最短路問題,但是邊權是一個到達時間的函數(邊權統一為時間的量綱, 函數單調遞增),此時仍然是Dijkstra算法,Dijkstra 算法實質就是一個寬度優先搜索。

            QQ截圖20121115145333

            5 給定一棵完全二叉樹,然后每個邊有權值。要求修改邊,然后使得跟到每個葉子節點的距離相同,要求修改的和最小?給出一個算法,這個在電路設計中就是同時性的要求。

            這個是個非常不錯的算法。還是一個遞歸的過程:

            T0G6CYQEEWAT$ZESUY3J(L6

              給定一個連通圖,他的邊的費用都是不同的,證明G有唯一的一棵最小生成樹。

            如果G有兩棵最小生成樹,則T 和P,必然有不同的邊,把T與P不同的邊加入到P中,必然形成圈。

            posted on 2012-11-15 16:38 Sosi 閱讀(664) 評論(0)  編輯 收藏 引用

            統計系統
            国产精品久久久亚洲| 久久久久波多野结衣高潮| 久久久一本精品99久久精品88| 人妻无码久久一区二区三区免费| 日韩乱码人妻无码中文字幕久久| 99久久无色码中文字幕| 久久青青草原精品国产不卡| 亚洲成色WWW久久网站| 国产亚州精品女人久久久久久 | 久久精品国产亚洲AV无码麻豆| 久久精品人人做人人爽电影蜜月| 久久精品国产99久久香蕉| 99久久免费国产精品特黄| 久久久久国产精品| 亚洲精品无码久久千人斩| 久久精品国产一区| 伊人久久综合成人网| 久久激情亚洲精品无码?V| 久久精品无码午夜福利理论片| 日本加勒比久久精品| 国产成人精品久久二区二区| 欧美日韩精品久久免费| 久久精品无码一区二区三区日韩| 亚洲国产精品成人久久| 日产精品久久久久久久| 人妻无码久久精品| 久久精品无码av| 国产亚洲精午夜久久久久久| 99国产欧美久久久精品蜜芽| 97精品国产97久久久久久免费 | 亚洲性久久久影院| 久久国产高清字幕中文| 国产精品无码久久久久久| 麻豆亚洲AV永久无码精品久久| 久久亚洲精品无码aⅴ大香| 亚洲国产一成久久精品国产成人综合 | 久久久久亚洲AV无码专区首JN | 精品国际久久久久999波多野| 久久亚洲日韩精品一区二区三区| 伊人久久综合精品无码AV专区| 久久久久久精品免费看SSS|