• <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)  編輯 收藏 引用

            統計系統
            亚洲AV日韩精品久久久久久久| 久久久久无码精品国产app| 久久久噜噜噜久久| 伊人久久大香线蕉亚洲| 久久99国产综合精品女同| 国产高清美女一级a毛片久久w| 久久久久久久91精品免费观看| 一本色道久久HEZYO无码| 久久99国内精品自在现线| 久久夜色精品国产亚洲| 亚洲色欲久久久综合网东京热| 麻豆成人久久精品二区三区免费| 日本亚洲色大成网站WWW久久| 国产精品久久永久免费| av无码久久久久久不卡网站| 久久精品亚洲精品国产欧美| 久久久久久久久久久久中文字幕 | 伊人久久大香线蕉av不卡| 久久免费线看线看| 久久综合精品国产二区无码| 一本综合久久国产二区| 欧美激情精品久久久久久| 99久久综合狠狠综合久久止| 欧美日韩精品久久久免费观看| 久久人做人爽一区二区三区| 日韩欧美亚洲国产精品字幕久久久 | 久久99精品久久只有精品| 色综合久久夜色精品国产| 久久综合色区| 久久亚洲国产成人影院网站| 亚洲乱亚洲乱淫久久| AA级片免费看视频久久| av无码久久久久不卡免费网站 | 色婷婷综合久久久中文字幕| 亚洲第一永久AV网站久久精品男人的天堂AV| 久久91亚洲人成电影网站| 青青青国产成人久久111网站| 久久亚洲精品国产精品| 久久精品国产乱子伦| 一本一本久久a久久精品综合麻豆| 亚洲国产成人精品91久久久 |