改进的模拟退火算法求解规则可满足性问题

对于随机k-SAT问题,限定每个变元出现的次数恰好出现d次,形成随机规则(k,d)-SAT问题,目前国内外对该问题的相关研究较少,且研究随机规则(k,d)-SAT问题比研究k-SAT问题更为具体。文中给出一种随机规则(k,d)-SAT问题的生成实例模型——RRIG(N,k,d)模型,并用改进的模拟退火算法SARSAT求解规则随机规则(k,d)-SAT问题。将变元出现次数d加入到扰动策略中,利用变元出现次数和子句间约束关系中的启发信息对候选解中的赋值选择性改动,加快算法收敛至较优解的速度;同时,模拟退火算法中的Metropolis接受准则和改进后的退火策略保证了算法能够有效跳出局部最优解,最后使用RRIG(N,k,d)模型生成不同参数的测试实例,并与其他相关算法进行比较,结果表明SARSAT算法能有效解决规则可满足问题。

ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM

Consider a computer assisted trading system in which the needs and the products of the traders are compared by a computer system and the trading proceeds without attaching a dollar price to each commodity. In such a system the computer serves as aii 'intelligent' communication link between traders, enhancing the ability of producers and consumers to exchange goods. In this paper, we examine one computational aspect of such computerized trading schemes:Given a list of trading proposals (each proposal specifying the quantities of the commodities to be traded),how should one arrange the trades so that the maximum number of trades can be made in the market? We show that this maximum trade problem is computationally hard; it is NP-complete (Nondeterministic Polynomial Time Complete). We then describe some related open questions and potential solutions.