• <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年3月>
            26272829123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            導航

            統計

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學

            網友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久人人爽人人爽人人片AV东京热 | 国产午夜久久影院| 欧美一区二区三区久久综合 | 久久免费大片| 少妇无套内谢久久久久| 99久久777色| 伊人久久大香线蕉综合5g| 国产精品女同久久久久电影院| 国产精品久久久久AV福利动漫| 国产成人综合久久久久久| 欧美牲交A欧牲交aⅴ久久| 91精品国产综合久久香蕉| 午夜久久久久久禁播电影| 久久激情亚洲精品无码?V| 三上悠亚久久精品| 日韩人妻无码一区二区三区久久99| 欧洲成人午夜精品无码区久久| 久久精品成人影院| 久久久青草久久久青草| 亚洲国产精品无码久久一区二区| 国产精品无码久久四虎| 99精品久久精品| 久久久久亚洲av无码专区喷水| 中文字幕无码久久精品青草| 99久久精品费精品国产| 久久Av无码精品人妻系列| 久久午夜福利无码1000合集| 久久亚洲国产成人影院网站| 久久精品国产亚洲av水果派| 久久久久av无码免费网| 青青草国产97免久久费观看| 国产成人久久久精品二区三区| 97久久超碰国产精品旧版| 久久99精品久久久久子伦| 99久久夜色精品国产网站| 久久久国产打桩机| 久久精品国产亚洲AV忘忧草18| 久久久久女教师免费一区| 久久久精品日本一区二区三区| 97久久精品人人做人人爽| 国内精品伊人久久久久影院对白 |