首页 > 编程语言 >【计算机算法】【图论】【最优匹配与点云对准问题】最(极)大团算法

【计算机算法】【图论】【最优匹配与点云对准问题】最(极)大团算法

时间:2024-03-12 18:24:10浏览次数:35  
标签:__ prime 图论 set cli graph 算法 点云 顶点

问题

团与最大团的定义

图顶点集的子集满足任意两个顶点相邻,称该子集是该图的一个团。图的所有团中顶点最多的,即最大的一个或多个,称为图的最大团或极大团。

图的最大团的实际应用问题

CVPR2023最佳论文之一用最大团算法实现鲁棒的点云对准,有效解决外点问题。顾名思义有矛盾:点云对准,即3D-3D点匹配,是各自独立的关联,最大团中顶点是两两关联,乍一看最大团算法无法适用。原论文作者们将候选匹配点对作为图的顶点,顶点相邻关系被定义为匹配点对之间满足匹配一致性约束,两帧点云中有两对匹配点 x − x ′ x-x^{\prime} x−x′、 y − y ′ y-y^{\prime} y−y′,如设一致性约束为距离阈值d
a b s ( ∣ ∣ x − y ∣ ∣ − ∣ ∣ x ′ − y ′ ∣ ∣ ) < d abs(||x-y||-||x^{\prime}-y^{\prime}||)< d abs(∣∣x−y∣∣−∣∣x′−y′∣∣)<d
如何求图的最大团?

求解图最大团

启发式思路:遍历顶点,对每个顶点查找其相邻顶点,构建初始团,遍历该团的顶点,对其相邻顶点,若已经在团内的跳过,判断可否加入团,保存极大团;比较各次结果的大小。
例,

Python代码实现

# 检查重复的团
def isNotRepeat(all, a):
    for i in all:
        s = set(i)
        sa = set(a)
        if sa.issubset(s):
            return False
    return True


def findMaxClique(graph):
    print("Start")
    clique_set = []
    # 遍历该团的顶点,
    for a in graph.keys():
        # 遍历顶点,对每个顶点查找其相邻顶点,构建初始团
        cli_can = [a, graph[a][random.randrange(0, len(graph[a]))]]
        # 跳过已经被结果中的某个团包含的种子团
        if isNotRepeat(clique_set, cli_can):
            for i in cli_can:
                # 对其相邻neighbour顶点,若已经在团内的跳过,判断可否加入团,
                nb = graph[i]
                for j in nb:
                    if j in cli_can:
                        continue
                    else:
                        is_memb = True
                        for ii in cli_can:
                            if j not in graph[ii]:
                                is_memb = False
                                break
                        if is_memb:
                            cli_can.append(j)
            clique_set.append(cli_can)
    n_max = 0
    mc = None
    # 比较各个团的大小。
    for c in clique_set:
        num = len(c)
        if num > n_max:
            n_max = num
            mc = c
    return mc
if __name__ == "__main__":
    Gc = {
        1: [2, 5],
        2: [1, 3, 4, 5, 6],
        3: [2, 4, 6],
        4: [2, 3, 5, 6],
        5: [1, 2, 4],
        6: [2, 3, 4],
    }
    print("Max Clique Problem")
    print(findMaxClique(Gc))

BronKerbosch算法

标签:__,prime,图论,set,cli,graph,算法,点云,顶点
From: https://blog.csdn.net/CSUzhangpeike/article/details/136643138

相关文章

  • 【图论】最小生成树与Prim、Kruskal算法
    求图的最小生成树的Prim、Kruscal算法,其实都是由最小生成树的性质推来的,掌握了该性质,便能较容易地推导出这两种算法。最小生成树的性质无向图G的顶点集为VVV,设......
  • 代码随想录算法训练营第四十三天 | 474.一和零,● 494. 目标和 ,1049. 最后一块石头的
     1049.最后一块石头的重量II 已解答中等 相关标签相关企业 提示 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,......
  • TSINGSEE青犀视频AI方案:数据+算力+算法,人工智能的三大基石
    背景分析随着信息技术的迅猛发展,人工智能(AI)已经逐渐渗透到我们生活的各个领域,从智能家居到自动驾驶,从医疗诊断到金融风控,AI的应用正在改变着我们的生活方式。而数据、算法和算力,正是构成人工智能技术的三大核心要素,它们之间相互关联、相互影响,共同推动着人工智能的发展。1、数据......
  • 【算法】【线性表】【数组】在排序数组中查找元素的第一个和最后一个位置
    1 题目给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1,-1]。你必须设计并实现时间复杂度为 O(logn) 的算法解决此问题。示例1:输入:nums=[5,7,7,8,8,......
  • RC4Drop算法的工作原理揭秘:加密技术的进步之路
    RC4Drop算法起源:RC4Drop算法是RC4算法的一种改进版本,旨在解决RC4算法在长时间加密过程中可能出现的密钥流偏置问题。RC4算法由RonRivest于1987年设计,是一种流密码算法,而RC4Drop算法则在此基础上加入了丢弃密钥字节的步骤,以增强安全性和随机性。RC4Drop加密解密|一个覆盖......
  • 人脸识别算法
    人脸识别已经成为了计算机视觉与生物识别领域被研究最多的主题之一人脸检测 :提取图像中的人脸,划定边界;人脸对齐 :使用一组位于图像中固定位置的参考点来缩放和裁剪人脸图像;人脸表征 :人脸图像的像素值会被转换成紧凑且可判别的特征向量,或称模板;人脸匹配 :选取并计算两个模板......
  • 代码随想录算法训练营第四十四天|完全背包 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ
    完全背包题目链接:52.携带研究材料(第七期模拟笔试)(kamacoder.com)思路:完全·背包问题和01背包的区别在于同一个物品可以被重复放入,在代码里的区别就是内部遍历背包的for循环由倒序变成了正序。而且如果我们压缩了一维的话,如我的做法,两个for循环的顺序也是无所谓的。#include<i......
  • C++新U4-贪心算法2
    [【贪心算法(二)】分发饼干]    【题意分析】将饼干分发孩子手上,并且使得满足的孩子数量最多【思路分析】为了尽可能满足最多数量的孩子,按照孩子想要获得的饼干大小从小到大的顺序依次满足每个孩子,且对于每个孩子,应该选择可以满足这个孩子的胃口且尺寸最小的饼......
  • 代码随想录算法训练营第七天| 454. 四数相加 II 383. 赎金信
    454.四数相加IIhttps://leetcode.cn/problems/4sum-ii/description/、publicintfourSumCount(int[]nums1,int[]nums2,int[]nums3,int[]nums4){intres=0;HashMap<Integer,Integer>map=newHashMap<>();for(inti:nu......
  • 傅里叶变换算法和Python代码实现
    傅立叶变换是物理学家、数学家、工程师和计算机科学家常用的最有用的工具之一。本篇文章我们将使用Python来实现一个连续函数的傅立叶变换。我们使用以下定义来表示傅立叶变换及其逆变换。设f:ℝ→ℂ是一个既可积又可平方积分的复值函数。那么它的傅立叶变换,记为f̂,是由以......