讲师中心 微信公众号

工具推荐

视频效率加速
AniShort
AniShort

AI短剧协同制作平台

Seko
Seko

AI短剧一键生成成片

立刻MV
立刻MV

低成本歌曲 MV、视频生成

Laper
Laper

剧本策划到成片协作

生成所有满足不相容性与子集关系的布尔组合矩阵

星枫小哥_4673

星枫小哥_4673

发布时间:2026-11-22 11:21:50

|

291人浏览过

|

来源于php中文网

原创

生成所有满足不相容性与子集关系的布尔组合矩阵

本文介绍如何基于给定的不相容矩阵(d)和子集矩阵(s),结合逻辑约束建模,系统性地生成所有合法的事件组合向量——即满足“互斥事件不可同时为真”“子集事件发生则其父事件必发生”等语义规则的完整解空间。

本文介绍如何基于给定的不相容矩阵(d)和子集矩阵(s),结合逻辑约束建模,系统性地生成所有合法的事件组合向量——即满足“互斥事件不可同时为真”“子集事件发生则其父事件必发生”等语义规则的完整解空间。

在概率建模、事件系统仿真或知识图谱推理中,常需从一组原子事件出发,枚举所有逻辑上自洽的联合状态。例如网球比赛中,“A以60–0获胜”隐含“A获胜”且排斥“B获胜”“B发球直接得分”等事件。这类约束可形式化为两类结构化矩阵:

  • 不相容矩阵 D:D[i, j] == 1 表示事件 i 与事件 j 互斥(不能同时为真);
  • 子集矩阵 S:S[i, j] == 1 表示事件 i 是事件 j 的子集(若 i 发生,则 j 必发生)。

但仅靠 D 和 S 不足以唯一确定解空间——还需补充第三类逻辑关系:否定蕴含(negation implication)。例如,“A未获胜”应推出“B获胜”,这无法由 D 或 S 直接导出,而需显式建模为矩阵 N:N[i, j] == 1 表示 ¬i → j。

以下提供一个健壮、可扩展的实现方案,使用 sympy 进行符号逻辑求解,并封装为通用函数:

import numpy as np
from sympy import symbols, And, Or, Not, Implies, satisfiable

def generate_valid_combinations(D: np.ndarray, S: np.ndarray, N: np.ndarray = None) -> np.ndarray:
    """
    基于不相容(D)、子集(S)及否定蕴含(N)矩阵,生成所有合法布尔组合。

    Parameters:
    -----------
    D : (n, n) ndarray
        D[i,j] = 1 ⇒ 事件 i 与 j 互斥(i ∧ j → False)
    S : (n, n) ndarray  
        S[i,j] = 1 ⇒ 事件 i 是 j 的子集(i → j)
    N : (n, n) ndarray, optional
        N[i,j] = 1 ⇒ ¬i 蕴含 j(¬i → j);若为 None,则自动推导为 D 的对称补(见说明)

    Returns:
    --------
    (m, n) ndarray of int
        每行是一个合法的 n 维布尔向量,共 m 种可能组合。
    """
    n = D.shape[0]
    assert D.shape == S.shape == (n, n)
    if N is None:
        # 启用启发式:若 D 对称,则 N[i,j] = D[j,i](即 ¬i → j ≡ j → ¬i)
        # 实际应用中建议显式提供 N,避免歧义
        N = D.T.copy()

    # 定义符号变量 x0, x1, ..., x_{n-1}
    variables = symbols(f"x0:{n}")

    # 构建逻辑约束表达式
    constraints = []

    # 1. 不相容约束:D[i,j] == 1 ⇒ x_i → ¬x_j
    for i in range(n):
        for j in range(n):
            if D[i, j]:
                constraints.append(Implies(variables[i], Not(variables[j])))

    # 2. 子集约束:S[i,j] == 1 ⇒ x_i → x_j
    for i in range(n):
        for j in range(n):
            if S[i, j]:
                constraints.append(Implies(variables[i], variables[j]))

    # 3. 否定蕴含约束:N[i,j] == 1 ⇒ ¬x_i → x_j
    for i in range(n):
        for j in range(n):
            if N[i, j]:
                constraints.append(Implies(Not(variables[i]), variables[j]))

    # 合并所有约束
    full_expr = And(*constraints)

    # 求解所有满足模型
    solutions = list(satisfiable(full_expr, all_models=True))

    # 转换为 NumPy 矩阵
    if not solutions:
        return np.zeros((0, n), dtype=int)

    result = []
    for sol in solutions:
        row = [int(sol.get(v, False)) for v in variables]
        result.append(row)

    return np.array(result, dtype=int)

# 示例:复现问题中的网球场景
D = np.array([
    [0, 1, 0, 0, 0],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 1, 1],
    [0, 1, 1, 0, 0],  # 已修正:D[3,2]=1 表示 A wins 60-15 ⇒ ¬(A wins 60-0)
    [0, 0, 1, 0, 0]
])

S = np.array([
    [0, 0, 1, 1, 0],  # A wins ⇒ A wins 60-0 & A wins 60-15(注意:原题 S 定义反了,此处按语义校正)
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
])

N = np.array([
    [0, 1, 0, 0, 0],  # ¬A wins ⇒ B wins
    [1, 0, 0, 0, 0],  # ¬B wins ⇒ A wins
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
])

X = generate_valid_combinations(D, S, N)
print("共找到 {} 种合法组合:".format(len(X)))
print(X)

✅ 关键说明与注意事项:

  • 矩阵语义必须严格一致:S[i,j] = 1 应表示 事件 i 是事件 j 的子集(即 i → j),而非相反;原始问题中 S 的定义方向易引发混淆,代码中已按标准逻辑惯例校正。
  • N 矩阵不可省略:仅用 D 和 S 无法推导出 ¬a → b 类约束,会导致解空间膨胀(如错误包含 [0,0,...] 全零向量)。显式提供 N 是保证完备性的关键。
  • 性能提示:当事件数 n > 20 时,穷举 2^n 状态不可行。此时建议改用 SAT 求解器(如 pysat)或引入剪枝策略(如增量约束传播)。
  • 验证建议:对输出结果 X,可反向验证每行是否满足:
    # 验证 D:无互斥事件同时为 1
    assert not np.any((X @ D * X.T).diagonal())
    # 验证 S:若 X[i]==1,则 X[j] 必为 1(当 S[i,j]==1)
    for i, j in zip(*np.where(S)):
        assert np.all(X[:, i] <= X[:, j])

该方法将领域知识(事件关系)精准映射为可计算的逻辑公式,兼顾可读性、正确性与工程可维护性,适用于各类基于约束的组合生成任务。

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
函子Zion

一款支持AI搭建、可视化编辑和多端发布的全栈无代码开发平台。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

Atoms
Atoms Hot

Atoms是一款AI智能体工具,第一支自动构建真实业务的 AI 团队。

Loomy
Loomy Hot

一款AI工具,主要用于科大讯飞发布的桌面级 AI 助理,比 OpenClaw 更易用、更安全!,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

超级简历WonderCV

一款AI办公效率工具,主要用于免费求职简历模版下载制作,应届生职场人必备简历制作神器,适合需要提升相关任务效率的用户。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

笔灵降AI

一款AI论文写作工具,主要用于论文降AI神器,适配知网及维普!一键降至安全线,100%保留原文格式;无口语化问题,文风更学术,降后字数控制最佳!,适合需要提升相关任务效率的用户。

墨刀AI
墨刀AI Hot

一款AI图像与设计工具,主要用于产品经理的专属智能体,适合需要提升相关任务效率的用户。

相关专题

更多
python打包成可执行文件
python打包成可执行文件

本专题为大家带来python打包成可执行文件相关的文章,大家可以免费的下载体验。

1971

2023.07.20

python能做什么
python能做什么

python能做的有:可用于开发基于控制台的应用程序、多媒体部分开发、用于开发基于Web的应用程序、使用python处理数据、系统编程等等。本专题为大家提供python相关的各种文章、以及下载和课程。

5664

2023.07.25

format在python中的用法
format在python中的用法

Python中的format是一种字符串格式化方法,用于将变量或值插入到字符串中的占位符位置。通过format方法,我们可以动态地构建字符串,使其包含不同值。php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

1929

2023.07.31

python教程
python教程

Python已成为一门网红语言,即使是在非编程开发者当中,也掀起了一股学习的热潮。本专题为大家带来python教程的相关文章,大家可以免费体验学习。

34817

2023.08.03

python环境变量的配置
python环境变量的配置

Python是一种流行的编程语言,被广泛用于软件开发、数据分析和科学计算等领域。在安装Python之后,我们需要配置环境变量,以便在任何位置都能够访问Python的可执行文件。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

4047

2023.08.04

python eval
python eval

eval函数是Python中一个非常强大的函数,它可以将字符串作为Python代码进行执行,实现动态编程的效果。然而,由于其潜在的安全风险和性能问题,需要谨慎使用。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

4067

2023.08.04

scratch和python区别
scratch和python区别

scratch和python的区别:1、scratch是一种专为初学者设计的图形化编程语言,python是一种文本编程语言;2、scratch使用的是基于积木的编程语法,python采用更加传统的文本编程语法等等。本专题为大家提供scratch和python相关的文章、下载、课程内容,供大家免费下载体验。

1303

2023.08.11

python合并两个列表
python合并两个列表

Python是一种强大的编程语言,具有许多方便的功能和工具。在Python中,有多种方法可以合并两个列表。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

636

2023.08.10

Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

0

2026.11.20

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn