• <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 閱讀(1475) 評論(0)  編輯 收藏 引用 所屬分類: 順序統計

            <2012年7月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導航

            統計

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學

            網友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲女久久久噜噜噜熟女| 亚洲综合久久夜AV | 久久久精品人妻一区二区三区四| 一本久久知道综合久久| 久久99精品久久久久久hb无码| 国产精品久久久久久搜索| 国产亚州精品女人久久久久久 | 精品久久久久久久久久中文字幕 | 色综合久久88色综合天天 | 久久亚洲精品无码aⅴ大香| 99久久无色码中文字幕| 亚洲国产小视频精品久久久三级 | 久久国产乱子伦免费精品| 国产国产成人久久精品| 亚洲精品无码成人片久久| segui久久国产精品| 久久精品人人做人人爽97| 久久无码精品一区二区三区| 亚洲国产精品高清久久久| 青青热久久国产久精品 | 国产精品久久毛片完整版| 久久久久久久精品成人热色戒| 久久亚洲国产中v天仙www| 久久人妻AV中文字幕| 色偷偷88欧美精品久久久 | 久久这里只精品国产99热| 久久久久免费看成人影片| 国产精品乱码久久久久久软件| 久久精品国产亚洲网站| 久久精品中文字幕无码绿巨人 | 久久国产免费直播| 亚洲国产成人久久精品影视| 欧美va久久久噜噜噜久久| 狠狠色狠狠色综合久久| 久久国产欧美日韩精品免费| 久久精品国产一区二区三区| 青青国产成人久久91网| 青青青青久久精品国产| 国产精品久久久天天影视香蕉| 日本久久久精品中文字幕| 伊人丁香狠狠色综合久久|