在优化问题中,我在队列中保留了许多候选解决方案,我根据它们的优先级来检查.
每次我处理一个候选人时,它会从队列中删除,但它会产生几个新的候选人,使得候选人数呈指数级增长.为了处理这个问题,每当候选人被添加到队列中时,我就为每个候选人分配一个相关性,如果没有更多的空间可用,我用新的候选者替换(如果适当的话)队列中当前最不相关的候选人.
为了有效地做到这一点,我保留了一个大的(固定大小)数组与候选和两个链接的间接二进制堆:一个以递减的优先级顺序处理候选,另一个以递增的相关性处理候选.
这对我的目的来说足够有效,并且所需的补充空间大约是4个投注/候选人,这也是合理的.然而,编码很复杂,而且看起来并不是最佳的.
我的问题是,如果您知道更合适的数据结构或更自然的方式来执行此任务而不会降低效率.