三维匹配问题
三維匹配（縮寫3DM）是六个经典NP完全问题之一，是经典穩定婚姻問題的推广，婚姻问题是：有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格，问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚？ 在三维匹配问题中，可以用集合W，X和Y对应于“三个”不同的性别，M属于WXY。用集合M中的每一个三元组对应一对这三个成员都能接受的“三方婚姻”。普通的婚姻问题可以在多项式时间内解决，而3D…
标签：#NP完全问题
共 35 篇文章
多重序列比對
，以多個生物個體的酸性核醣體蛋白P0（acidic ribosomal protein P0；L10E）的前90個位置所作的多重序列比對。]] 多重序列比對（Multiple sequence alignment；MSA）是對三個以上的生物學序列（biological sequence），如蛋白質序列、DNA序列或RNA序列所作的序列比對。一般來說，是輸入一組假定擁有演化關係的序列。從MSA的結果可推導出序列的同源性，而種系發生關係也可…
點亮
）]] 點亮（、明かり，），又稱作數燈、點燈遊戲，是由出版的二進制邏輯益智遊戲。首次出現於解謎刊物《》2001年第95期的〈製作有趣解謎遊戲〉（『オモロパズルのできるまで』）單元，並從第102期開始定期發布。 遊戲規則 ）]] 在由白色與黑色格子組成的矩形網格上進行遊戲。玩家將燈泡（用圓圈標記）填入白格中，確保兩個燈泡不會相互照射，直到整個網格都被點亮（每個謎題皆為唯一解）。燈泡只會往水平與垂直方向發射光線，照亮整個行和列，除非它的光線…
數獨
數獨（）是一種數學邏輯遊戲，遊戲由9×9個格子組成，玩家需要根據格子提供的數字推理出其他格子的數字。遊戲設計者會提供最少17個數字使得解答謎題只有一個答案。 這種遊戲只需要邏輯思維能力，與數字運算無關，所以數學不好的人也很適合。雖然玩法簡單，但提供的數字卻千變萬化，所以不少教育者認為數獨是鍛鍊腦筋的好方法。 數獨遊戲由美国自由拼图发明者于1979年发明，日本出版商Nikoli於1986年發展，意思為「獨身最適數字」。 历经多年，數獨遊戲…
集装优化
集装优化，又名裝箱問題是一個利用作業研究去解決實際生活的的經典問題。簡單來說，就是把大量小盒子裝進大箱子並塞滿的學問。但現實中要如何才能裝得多又快？而物體的重量、性質、保存條件等都不相同，加上取出的順序要能有效提高速度，又不會使運輸工具失去重心，因此裝箱最佳化在效率至上運輸界中是十分重要的。 傳統上，數學家開發的演算法是啟發式演算法，也就是基於一些準則，比如兩個小箱子一樣寬，將把寬的一邊對齊，這樣的好處是算得快，缺點是很多可能性（或者叫…
NP完全
, NP, NP完全，以及NP困难之间关系的欧拉图]] -{zh:NP完全或NP完备; zh-hans:NP完全或NP完备; zh-tw:NP完備或NP完全; zh-hk:NP完全或NP完備}- （NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NP完备是NP与NP困难問題的交集，是NP中最難的決定性問題，所有NP問題都可以在多項式時間內被歸約（reduce to）為NP完備問題。倘若任何NP…
哈密頓路徑
在圖論中，哈密顿路径（）是在無向圖或有向圖中，恰好能將圖中所有頂點各拜訪一次的路徑。與之相近的概念為哈密顿环（），即該路徑在拜訪完圖中所有頂點後會回到出發點，而構成一個環。要確定圖中是否存在哈密顿路徑或哈密顿環的問題稱為哈密顿路径问题，這個問題是一個NP完全的問題。哈密顿路徑有時會跟尤拉路徑一起討論，因為哈密顿路徑要求通過所有頂點（哈密顿路径问题）而尤拉路徑要求通過所有邊（一筆畫問題）。 定義 哈密顿路徑是一個拜訪過某圖所有頂點的路徑，…
背包问题
背包问题（）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。 背包问题历史悠久，甚至可以追溯到1897年。“背包问题”…
踩地雷
{{About|游戏类型|电子角色扮演游戏中“-{踩地雷}-”的遇敌方式|随机遇敌|微软开发的扫雷|微軟踩地雷}} 的扫雷版本，图为专家模式下获胜的情景]] 扫雷游戏（）是一类逻辑谜题类电子游戏。游戏界面由一系列可点击的方块组成，某些方块中隐藏着「地雷」。玩家需打开所有无雷方块，但不能触发地雷。已打开方块上显示的数字展现了周围地雷数量。 在基本玩法之上，还衍生出了许多其他版本，例如《Minesweeper X》、《Crossmines》…
最长路径问题
在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的简单路径。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路径问题（不含负权环）可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P = NP，否则对应于任意的图，没有办法在多项式时间内解决该问题。更强的结果表明这个问题也難以近似地得出答案。但是，有一个线性时间的方法可以用…
數方
數方（英語：Shikaku）是一個和面積有關的遊戲，由尼科利發佈的邏輯謎題。 歷史 該遊戲由京都大學的數學系學生安福義直於1989年發明，並且以「Shikaku」之名由日本遊戲雜誌尼科利出版。 規則 國際象棋是在矩形網格上進行的。網格中標有一些數字。遊戲的目標是將網格分割成多個長方形和正方形，使得每一個長方形和正方形都有包含剛好一個數字，有數字且只有一個數字，那個數字是長方形和正方形的面積，在數方還要看裡面的數字來決定橫邊和直邊的長度，…
最长公共子序列
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的問題。这与查找最長公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。 定義 一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已…
分区问题
分区问题（）是数论和计算机科学领域的问题，目的是把一个多重集S分为S_1和S_2两个子集，要求S_1和S_2这两个集合中所有数的和相等。尽管分区问题属于NP完全问题，但是依然存在伪多项式时间的动态规划解法，而且在很多情况下也存在启发式的解法，能够求出最优解或近似最优解。正是基于这一点，这类问题也被称为“最简单的难题”。 分区问题存在一个最佳化問題，该问题是将S分为S_1和S_2，要求S_1中元素的和与S_2中元素的和相差最小。这一问题属…
哈密顿图
又稱漢密頓圖，是指存在哈密頓環的無向圖，由哈密顿爵士提出。 定義 下列定義，既適用於無向圖，亦適用於有向圖。 ;哈密頓路徑:圖的一條路，經過每個頂點恰好一次。 ;哈密頓環:在一條哈密頓路的基礎上，再有一條邊將其首尾連接，所構成的圈。注意，若有一個哈密頓圈，則移除其任一條邊，皆可得到一條哈密頓路，但反之則不然，即給定一條哈密頓路，不一定能延伸成哈密頓圈，因為該路徑的首尾兩頂點之間，不一定有邊相連。 ;哈密頓圖:有哈密頓圈的圖。 ;半哈密頓…
俄羅斯方塊
《俄羅斯方塊》（），是1980年末期至1990年代初期風靡全世界的電腦遊戲，是落下型益智遊戲的始祖，電子遊戲領域的代表作之一，為蘇聯首個在美國發佈的娛樂軟體。此遊戲最初由阿列克謝·帕基特諾夫在蘇聯設計和編寫，於1984年6月6日首次發佈，當時他正在蘇聯科學院電算中心工作。此遊戲的名稱是由希臘语數字「四」的前綴「tetra-」（因所有落下方块皆由四块组成）和帕基特諾夫最喜歡的運動網球（「tennis」）拼接而成，華語地區則因遊戲為俄羅斯人…
图着色问题
图着色问题（，簡稱），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图G=(V, E)，其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。 图色数 有两个相关的术语： 图色数（chromatic number），也被称为顶点色数（vertex chromatic number），指将一张图上的每个顶点染色，使得相邻的两个点颜色不同，最小…
旅行推销员问题
旅行商问题（，縮寫：TSP）是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每對城市之间的距离，求解访-{}-问每座城市一次并回到起始城市的最短回路。” TSP是与车辆路径问题的一种特殊情况。 作为计算复杂性理论中一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最…
子集和問題
子集和問題（），又称子集合加總問題，是計算複雜度理論和密碼學中一個很重要的問題。问题可以描述为：給一個整數集合，問是否存在某個非空子集，使得子集内中的數字和為某个特定数值。例：給定集合{−7, −3, −2, 5, 8}，是否存在子集和为0的集合?答案是YES，因為子集{−3, −2, 5}的數字和是0。這個問題是NP完全问题，且或許是最容易描述的NP完全問題。 一個等價的問題是：給一個整數集合和另一個整數s，問是否存在某個非空子集，使…
集合覆盖问题
集合覆盖问题（Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。 集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。 定义 给定全集\mathcal{U}，以及一个包含n个集合且这n个集合的并集为全集的集合\mathcal{S}。集合覆盖问题要找到\mathcal{S}的一个最小的子集，使得他们的并集等于全集。 例如\mathcal{U} = \{1, 2, 3, 4, 5\…
數字推盤遊戲
數字推盤遊戲（n-puzzle）是一種最早的滑塊類遊戲，常見的類型有十五數字推盤遊戲和八數字推盤遊戲等，因其遊玩的方式與另一個推盤遊戲華容道類似，故數字推盤也常被稱為數字華容道。也有以圖畫代替數字的推盤遊戲。可能Noyes Palmer Chapman在1874年發明十五數字推盤，但薩姆·勞埃德則在1891年也宣稱為其發明。 八數字推盤（又名重排九宮）則同樣是Noyes Palmer Chapman在1870年代發明，並且馬丁·加德納在…