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

            好友

            同學

            網友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久综合香蕉尹人综合网| 久久99热国产这有精品| 亚洲精品国产综合久久一线| 激情五月综合综合久久69| 色综合久久天天综线观看| 久久久久免费精品国产| 国产精品久久久久久搜索| 久久精品国产一区二区电影| 久久精品中文字幕一区 | 久久久免费观成人影院 | 天堂无码久久综合东京热| 国内精品九九久久精品| 91精品久久久久久无码| 久久婷婷五月综合成人D啪| 欧美综合天天夜夜久久| 99久久精品免费看国产一区二区三区| 久久精品人人做人人爽电影蜜月| 欧美激情精品久久久久久| 成人资源影音先锋久久资源网| 亚洲欧美久久久久9999| 93精91精品国产综合久久香蕉| 99久久精品国产一区二区| 久久综合精品国产一区二区三区 | 无码人妻久久一区二区三区免费丨 | 奇米影视7777久久精品| 久久91精品国产91| 大香网伊人久久综合网2020| 97久久精品无码一区二区| 精品人妻伦九区久久AAA片69 | 国产色综合久久无码有码| 一本一道久久a久久精品综合| 国产精品伦理久久久久久| 99久久中文字幕| 日本久久久精品中文字幕| 国产精品九九九久久九九| 久久精品国产久精国产思思| 久久人人爽人人爽人人AV| 中文字幕乱码久久午夜| 色欲综合久久躁天天躁蜜桃| 久久亚洲AV成人无码国产| 精品久久久久久成人AV|