最大割問題
最大割問題（）是指，給定一張圖，求一種分割方法，將所有頂點（）分割成两群，同时使得被切斷的邊（）數量最大。该问题是一个NP完备问题。 此問題還有另一個變形的版本：每條邊上有各自的權重，要使得被切斷的邊的權重之和最大。 多項式時間的演算法 雖然最大割問題是 NP-hard 問題，但如果圖本身滿足一些條件之下，是存在多項式時間的演算法的。 圖沒有正邊時（權重都是負的） 可以將圖中所有邊都變號（乘上-1），將最大割問題轉成最小割問題。再使用求…
标签：#NP完全问题
共 35 篇文章
哈密顿路径问题
上的哈密顿环（红色）。]] 图论中的经典问题（Hamiltonian path problem）与（Hamiltonian cycle problem）分别是来确定在一个给定的图上是否存在哈密顿路径（一条经过图上每个顶点的路径）和哈密顿环（一条经过图上每个顶点的环）。两个问题皆为NP完全。 哈密顿环问题与哈密顿路径问题之间的关系 哈密顿环问题与哈密顿路径问题之间有着很简单的关系： 给定图G ,通过加入新顶点v 并将新顶点与所有其他顶点连…
数和
）]] 数和（英：Cross Sums；日：）是一种数学智力游戏。数和把填字游戏和数独巧妙地结合在一起，采用填字游戏式的棋盘，解题时在空格中填上1-9的数字。这种游戏不仅需要逻辑思维能力，还需要一点加法运算。 规则 方形空格中填入1～9的整数。 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格中数字之和，左下角的数字等于其下方邻接之连续方格中数字之和。 无论是横向还是纵向，连续方格中的数字不能重复。 数和的命题也有一些惯例，如只…
數織
數織是一種邏輯遊戲，以猜謎的方式繪畫黑白點陣圖。在一個網格中，每一行和列都有一組數，玩家需根據它們來填滿或留空格子，最後就可以由此得出一幅圖畫。例如，「4 8 3」的意思就是指該行或列上有三條獨立的線，分別佔了4、8和3格，而每條線最少要由一個空格分開。傳統上，玩家是以黑色填滿格子，和以「×」號標記一定不需要填充的格子。數織是一個NP完全的問題。 數織是在1987年由日本人發明的。數織的日文名稱是「*'」，意思是「繪畫邏輯」。數織初見於…
二次剩余
在数论中，特别在同余理论裏，一个整数X对另一个整数p的二次剩余（）指X的平方X^2除以p得到的余数。 當存在某個X，式子X^2 \equiv d \pmod{p}成立時，稱「d是模p的二次剩余」 當对任意X，X^2 \equiv d \pmod{p}不成立時，稱「d是模p的二次非剩余」 研究二次剩余的理论称为二次剩余理论。二次剩余理论在实际上有广泛的应用，包括从噪音工程学到密码学以及大数分解。 前几个自然数的二次剩余 下表列出了1至25…
珠璣妙算
Mastermind（珠璣妙算）是一種可供兩名玩家遊玩的密碼破譯棋盤遊戲。在1970年由以色列郵政和電信專家Mordecai Meirowitz發明。 遊戲早期一種利用鉛筆和紙進行的遊戲，名為「公牛和母牛」，可能追溯到一個世紀或更長時間前。 參看 智力遊戲 猜數字 外部連結 * [https://mastermindgame.net/#/ 珠玑妙算在线版]
独立集
独立集（英语：Independent set）是图论中的概念。一个独立集（也称为稳定集）是一个图中一些两两不相邻的顶点所形成的集合。换句话说，独立集S由图中若干顶点组成，且S中任两个顶点之间没有边。等价地，图中的每条边至多有一个端点属于S。一个独立集的基数是它包含顶点的数目。 如果往图G的独立集S中添加任一个顶点都会使独立性丧失（亦即造成某两点间有边），那么称S是极大独立集。如果S是图中所有独立集之中基数最大的，那么称S是最大独立集，且…
精确覆盖问题
在一个全集X中若干子集的集合为S，精确覆盖是指，S的子集S，满足X中的每一个元素在S中恰好出现一次。 在计算机科学中，精确覆盖问题指找出这样的一种覆盖，或证明其不存在。这是一个NP-完全问题。 定义 满足以下条件的集合为一个精确覆盖： S中任意两个集合没有交集，即X中的元素在S中出现最多一次 S中集合的全集为X，即X中的元素在S中出现最少一次 合二为一，即X中的元素在S中出现恰好一次。 举例 令 \mathcal{S} = {N, O,…
四色方柱问题
四色方柱问题是由有四個顏色的立方体組成的問題。由四色（通常是红色，蓝色，绿色和白色）將立方體着色，用四个立方体组成方柱。问题是如何将这些立方体排成一列，使得排成的长方体的每一側(前、后、左、右)都有四种颜色。 四色方柱问题可以转化为图着色问题来解决。 解法 希望通过给定的四个立方体，构造一张图，并通过解决图着色问题得到排列方式。图的构造方式如下： 图最初由4个点构成，四个点的颜色与四色方柱的四种颜色相同（红绿蓝黄）。 对每个立方体，考虑…
中国邮递员问题
中国邮递员问题（也称路线检查问题，Route Inspection Problem）是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑，且此路徑需通過所有邊至少一次。现实意义中，中国邮递员问题就是在一個已知的地區，郵差要設法找到一條最短路徑，走過此地區所有的街道，且最後要回到出發點。 此問題是圖遍歷問題的一種。无向图的中国邮递员问题是容易解决的，是P问题；而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在…
數迴
數迴（英：slither link；日：）為数学智力游戏的一種，由棋盤格與位於棋盤格內的數字所構成。解题时必須透過數字所提供的線索，在棋盤格線上連出一條不間斷的封閉環圈。 规则 在相同點距大小的棋盤上，用直線或橫線將兩相鄰點連接起來，目標是要讓所有連接線形成一個封閉環圈； 位於四點之間的數字，表示這四點所構成方格上的邊線數目。而沒有數字的地方則代表周圍的邊線數目未知； 劃線時，不能讓最後連出來的整條線上出現交叉或分支； 也不能出現兩個以…
填字游戏
填字游戏是一种常见的紙上益智遊戏。 游戏一般给出一个矩形的表格。这个表格被分割为若干个大小相同的方格，方格的颜色有白色与黑色两种。白色的方格组成一些交叉的行与列，行列的长度不等。 玩家根据题目所提供的有关信息，将答案填入这些行与列之中，每个白色方格中只能填入一个字。 例子 下列就是一个英式填字游戏的例子： 横行 1. 羊声 (3) 2. 不是气体或液体 (5) 3. 幽默 (3) 直列 A. 交通工具 (3) B. 应许 (5) C. …
布尔可满足性问题
可滿足性（英語：Satisfiability）是用來解決給定的真值方程式，是否存在一组变量赋值，使問題为可满足。布尔可滿足性問題（Boolean satisfiability problem；SAT ）屬於決定性問題，也是第一个被证明屬於NP完全的问题。此問題在電腦科學上許多的領域皆相當重要，包括電腦科學基礎理論、演算法、人工智慧、硬體設計等等。 直观描述 对于一个确定的逻辑电路，是否存在一种输入使得输出为真。 参见 NP-comple…
车辆路径问题
车辆路径问题（VRP）是一个组合优化和（回答了“为了交付给定的一组客户，车辆车队的最佳路线集是什么？”）。它概括了众所周知的旅行推销员问题（TSP）。它最初出现在1959年George Dantzig和John Ramser的论文中。这篇论文首先编写了算法，并将其应用于汽油交付。通常，这个问题的背景是将位于中央仓库的货物交付给已经订购此类货物的客户。 VRP的目标是最小化总路由成本。 1964年，Clarke和Wright使用一种称为储…
Set packing
Set packing 问题是复杂性理论和组合数学中一个经典的NP完全问题，是卡普的二十一個NP-完全問題之一。 题目描述 给定一个有限集合 S 和一些 S 的子集，求问是否可以其中的 k 个子集，他们两两不相交。 形式化的定义：给定全集\mathcal{U}，和\mathcal{U}的一组子集\mathcal{S}。packing指一个集合\mathcal{C}满足\mathcal{C}\subseteq\mathcal{S}且\ma…