修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称：
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
用户中心
  • 基础信息
  • 证书
基础信息
  • 用户昵称：
  • 手机号：
  • 公司名称：
  • 公司邮箱:
  • 地区：
  • 语言：
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

找最长路径

回答此问题
解决
Pearl C2022-03-31

khop()可以找最短路径，有没有什么方法可以找最长路径？我就刚好有这样的需求

2 个回答

  • 4 点赞

    在微小的图上面找“最长路径”是有意义的。所谓微小图，100个点边的量级。

    在动辄千万级点边上，寻找“最长路径”意义不大。
    有几个点：
    1. 意义何在？运筹学、动态规划领域，永远都在找最短路径、加权最短路径，甚至是随机游走路径，但是并不关注最长路径。
    2. 算法复杂度：假设一张图中有100个点，1000条边，如果点、边是弱联通的（联通分量WCC=1），那么理论的最长路径是1000（假设顶点可以重复访问，边不可以重复），但是可能存在的最长路径有多少条呢？10**1000 （10的1000次方）。假设|E|代表边的数量，|V|代表顶点的数量，|E|/|V|代表点边比，遍历复杂度 ~= (|E|/|V|)**|E|。目前没有任何系统可以完成这种“量子计算”复杂度的运算。

    相比“最长路径”而言，更有意义的是找到图中的最长最短路径。Ultipa系统上有多重方法可以实现：
    1. khop()：一种笨方法是随机从任一顶点开始探索其最大K邻的步幅。更智能、便捷的是通过直接调用图算法来实现（如下）。

    2. 图算法：例如HyperANF、全图K-hop等 https://www.ultipa.cn/document/ultipa-graph-analytics-algorithms/advanced-graph-algorithm/v2.x 

    To summarize, 这个“最长路径”问题源自于学术界，但是因为学院派会用很多小图（10几个到几十个点边）来验证，但是忽略了大图上面的天文数字级的算法复杂度的挑战。注：找到1条“最长”路径或许并不复杂（有很大的随机性），但是找到所有的最短路径的复杂度就是个mission impossible了。


    Good_Architect 2022-03-31
    添加评论...

    取消
    提交
  • 2 点赞

    最长路径可以通过路径查询，将路径步数设为极大值来去获得，最长路径可能会包含重复的顶点。

    但是，最长路径在复杂图中（以欧拉路径的方式）进行查找，可能会存在不合理性，其返回结果可能会变得不可估计。最长路径在图的发展中有一些实际问题，比如“骑士问题”。

    在现实当中，很少出现最长路径的计算需求，这将变成如何能够尽量多的经过边或者顶点的问题。

    骑士问题不同棋盘大小下的具体计算结果量：



    apitlu 2022-03-31
    添加评论...

    取消
    提交

你的回答:

提交
取消
    创建新问题

    全部问题

    我发布的

    我收到的

    最近浏览