分治法求最近点对问题

没时间更新了,放一波伪代码,有空再补吧。

遍历函数:遍历所有点

//traverse(set):遍历set中所有的点,做差
traverse(set):
    flag <- set[0].sub(set[1])
    for i 0 to (set.size() - 1) by 1 do:
        for j i + 1 to set.size() ny 1 do:
            if set[i].sub(set[j]) < flag then:
                flag <- set[i].sub(set[j])
        end
    end
    return flag

分治函数:作用是进行分治以及递归,将求出的最小的flag带入到合并函数,返回最终的flag。

//merge(set):分治函数
merge(set):
    if set.size() > 3 then:
        //数量大于3时,使用分治法
        middle <- set.size() / 2
        //将set切分为leftSet以及rightSet,分别进行递归
        leftFlag = merge(leftSet)
        rightFlag = merge(rightSet)
        //完成递归后筛选出最小值
        flag = min{leftFlag, rightSet}
        //将最小值传入合并函数
        flag = merge(leftSet, rightSet, flag)
    else
        //数量小于3时,调用蛮力法
        flag <- traverse(set);
    return flag

合并函数:将leftSet∈(index – flag, index)与rightSet∈(index, index + flag)做差,若有值小于flag,则覆盖flag。

//merge(leftSet, rightSet, flag)
merge(leftSet, rightSet, flag) :
    //将index设为中值
    newFlag <- flag;
    for i (leftSet.size() - 1) to 0 by -1 do:
        //筛选出leftSet中属于[index - flag, index]中的值
        if leftSet[i].getX() > index - flag:
            exit
        //for循环遍历rightSet中的每项
        for j : rightSet:
            //筛选出rightSet中属于[index, index + flag]中的值
            if j.getX() < index + flag:
                exit
            if leftSet[i].sub(j) < newFlag:
                newFlag <- leftSet[i].sub(j)
        end
    end
    return newFlag
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇