• <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>

            郵局位置問題 和 帶權中位數

            帶權中位數定義如下:


            郵局位置問題定義如下: 



               上一篇文章輸油管道問題里面證明了,當權值Wi都為1的時候,中位數就是最佳的解。但是,現在Wi已經不一定是1了。所以,現在
            需要證明在任意Wi的取值情況下,帶權中位數能夠成為郵局位置的最佳解。假設,所有Wi都是1的倍數,如果是小數的話,可以所有的
            Wi都乘以一定的倍數。那么wi*d(p,pi) = Σ(p,pi)(i從1到wi),這個意思是把距離乘以了wi倍。
               但是,現在可以換一種看法,換成了pi位置有wi個重合的點,且每一個點的權值都是1,那么其和也是wi*d(p,pi)。那么對所有的pi
            都這樣分解,就把問題重新轉換成了輸油管道問題了
            。輸油管道問題的最優解就是中位數,那么郵局問題的最優解就是轉換之后的
            這些點的中位數點
            。而這個點一定存在于帶權中位數那個點分解出的一堆點中。
               二維郵局問題的解法是把x和y分開求2次一維郵局問題,然后把解組和起來,得到答案。

               求帶權中位數的算法比較簡單,直接的做法是,先把n個點按照位置排序,然后按點的位置從小到大遍歷,找到滿足要求的點即可。
               不算排序點位置的預處理,因為很多時候點應該就是按順序給出的,所以其時間復雜度是O(n)。
               要求:

            posted on 2012-03-11 19:36 yx 閱讀(1464) 評論(0)  編輯 收藏 引用 所屬分類: 順序統計

            <2012年9月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            30123456

            導航

            統計

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學

            網友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久91精品国产一区二区三区| 色播久久人人爽人人爽人人片aV| 亚洲午夜久久久影院| 99蜜桃臀久久久欧美精品网站 | 国内精品伊人久久久久网站| 97久久精品人人做人人爽| 蜜桃麻豆www久久国产精品| 久久精品成人欧美大片| 91超碰碰碰碰久久久久久综合| 久久久久久无码国产精品中文字幕| 一本一本久久a久久精品综合麻豆| 久久久久亚洲AV成人网人人网站| 青青草原综合久久大伊人精品| 一本久久免费视频| 久久国产精品一区二区| 精品国产乱码久久久久软件 | 77777亚洲午夜久久多喷| 久久精品国产亚洲精品| 久久ZYZ资源站无码中文动漫| 久久无码精品一区二区三区| 精品国际久久久久999波多野| 久久综合伊人77777麻豆| 秋霞久久国产精品电影院| 亚洲综合日韩久久成人AV| 精品国产综合区久久久久久| 成人国内精品久久久久一区| 久久精品国产亚洲AV忘忧草18| 久久久久久国产精品美女 | 久久精品国产只有精品2020| 久久久久久综合网天天| 久久无码国产| 九九久久精品无码专区| 色综合久久最新中文字幕| 亚洲国产精品久久电影欧美| 久久久久av无码免费网| 思思久久99热只有频精品66| 思思久久99热免费精品6| 国内精品久久久久久久涩爱| 国产精品久久久久久久午夜片| 久久精品视频免费| 99久久婷婷国产一区二区|