0

这是问题:

考虑体育联赛调度问题的以下规则和定义:

  • N(偶数)支球队,每两支球队在赛季中恰好交手一次。
  • 赛季持续 (N-1) 周。
  • 每支球队在赛季的每个星期都打一场比赛。
  • 每周有 N/2 个时段或时段;每个时段都安排在一场比赛中。

(a) (25 分) 将体育联赛调度问题编码为布尔可满足性问题。提示:

  • 为了模拟两个不同的球队在给定的插槽中互相比赛,将每个插槽分成两个子插槽。对于每周,我们有 N 个子插槽。采用这样的惯例,即两支球队打连续的子时段——一个奇数的子时段,然后是一个偶数的子时段——实际上是在互相比赛。
  • 变量 Xijk 被分配为真,当且仅当球队 i 在第 k 周在子槽 j 中比赛时
  • 变量 Yijk 被赋值为真,当且仅当当队 i 在第 k 周与队 j 比赛时

有一个问题:给出说明每个子槽中只有一支球队参加比赛的条款。有多少条语句?

我的问题:这里的“条款”实际上是什么意思?我发布这个问题是希望有人能告诉我这个问题想问什么,我不是在寻找直接的解决方案。

谢谢,如果有人可以帮忙。

4

2 回答 2

1

就 CNF SAT 而言,“子句”是文字的有限析取,其中文字是变量或其否定

阅读维基百科上的条款以获得更详细的描述。

大多数现代布尔 SAT 求解器都接受 CNF 公式作为输入。

于 2013-10-21T23:53:34.827 回答
0

您正在寻找 SAT 的介绍。Don Knuth 今年早些时候在 JKU 做了一次演讲,很好地介绍了这个话题。在讲座中,他还提供了指向 TAOCP 中 SAT 章节预览版的链接。在这里找到讲座的录音:

讲座(和书籍章节)涵盖了 SAT 求解的基本术语、如何使用 CNF 子句对各种问题进行编码以及 SAT 求解器如何工作。

于 2013-10-22T10:44:28.973 回答