一个算法思路,无法自拔

今天跟大家分享一个算是算法思路吧!因为这个,我们团队在公司折腾到凌晨4点。由于不方便直述业务内容,我在这做了概念转换,也便于大家理解领悟吧。

模型很简单,如下图有9个房间,每个房间都有文件,9把钥匙可以开打对应的房间取到对应文件。(如:钥匙A可以打开房间A,取到对应文件a)

上面这个比较好理解,那么我们加深一层模型,加一个单向通道,每个房间都能通往它的上级房间,如下图。我们暂且把这个称之为”房间网络层级图

那么,如果你有钥匙B就可以打开房间B,即可以取到文件a和文件b。

好的,已经有了个初步认知了,咱们来个快问快答:

问:你有钥匙D、E、F,请问能取到哪些文件?

答:a、b、c、d、e、f共6个文件。

问:你想取到b、f文件,请问需要拥有哪些钥匙?

答:至少需要拥有两把钥匙,B\D\E\G\H这5把需要持有其中一把,F\I这2把需要持有其中一把即可,所以说两把钥匙的组合就有5*2=10种情况。(满足这10种组合情况下,拥有更多的其他钥匙当然也可以取到文件。)

问:若想取到a文件,请问有需要拥有哪些钥匙?

答:持有任意一把钥匙即可。

 

好了,有了上面问答的热身之后,终极问题来了

小明拥有X把钥匙,共有N份文件,请设计算法,算出小明能取到哪些文件?

补充一下,

1.一个房间可以有多个文件,如:B房间有b1、b2、b3文件。

2.上图只是示例,实际情况房间的层级多样,但是单向通道规则是不变的哈。

 

在下目前能想到的算法:

算法一:【通过钥匙来匹配文件】

1.循环每把钥匙,把每把钥匙能通往的房间并集得出集合List。(向上搜索,找某点的所有父级)

2.根据所有文件所在的房间与集合List做交集,得出哪些文件有权限查看。

 

 

算法二:【通过文件来匹配钥匙】

1.循环每个文件,把可以取到这个文件的钥匙合并得出一个字典集合Dic,文件所在房间相同的无需重复计算。(向下搜索,找某点的所有子集)

(字典的key:文件b1,字典value:钥匙B、D、E、G、H)

2.循环字典Dic,将字典value与钥匙集合进行交集,存在交集的即为有权限查看的文件,最后得出哪些文件有权限查看。

 

这两种功能上都是可行的,But性能上会因为数据差异而相差甚远。

单单使用算法一、或者算法二都绝不为最佳方案,但我目前还未想明白该如何设计此最优算法,求大神们指教!

 

小分析下算法一、二的局限性吧!

我能想到的一些局限性:

1.【钥匙数远大于文件数时,算法一不可取】

假设你拥有100000把钥匙,但是文件数量才十几个甚至几个,还用算法一吗?

2.【房间网络层级图规模庞大时,若有文件在房间A,算法二有点慌】

假设有个文件所在房间就是顶点房间A,那么算法二就得遍历搜索他的所有子集,相当于遍历了整颗树,若这个房间网络层级图非常庞大,那这种算法也是可取吗?...

(或者说是房间B,也几乎要遍历整个房间网络层级图)

 

我认为应当考虑如下因素,但不知道如何进行平衡:

1.房间网络层级图的规模

2.拥有的钥匙数目

3.文件数量

 

如今终日陷入沉思中无法自拔,如果有好心人看到帮忙传播一下,若有大神解惑,必有重谢!”感恩的心,感谢有你~~“

8

发表评论

电子邮件地址不会被公开。 必填项已用*标注

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

一个算法思路,无法自拔
嘿!有什么能帮到您的吗?
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close