| comment
| - 集合被覆問題（しゅうごうひふくもんだい）は、集合 U とその部分集合の族 S1,...,Sm が与えられたとき、U の要素を全てカバーするように部分集合の族から最小個数の部分集合を選ぶ問題。ここで、S1,...,Sm の和集合は、U に等しくなるものとする。 各部分集合 Si に対し重み wi が与えられ、選択した部分集合の重みの和を最小化する問題のことを指す場合もある。このような場合、重み付き集合被覆問題 と区別して呼ぶことも多い。全ての i について wi が等しいとき、重み無し集合被覆問題と等価なので、重み無し集合被覆問題は、重み付き集合被覆問題の特殊な場合とも言える。 重み無し・重み付きを問わず、この問題はNP困難であることが知られている。そのため、集合に制約を加えた問題や近似アルゴリズムの研究がさかんである。
- Gegeven een verzameling U (de universele verzameling), en anderzijds een verzameling S van deelverzamelingen van U, waarvan de vereniging gelijk is aan U. Een verzamelingenoverdekking (set cover) van U bestaat uit een of meer verzamelingen uit S zodanig dat hun vereniging ook gelijk is aan U. In het vervolg van dit artikel wordt overal overdekking gebruikt in plaats van verzamelingenoverdekking.
- Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным.
- 集合覆盖问题（ Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。 集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。
- El problema del Set Covering, también conocido por sus siglas SCP es un problema clásico en combinatoria, ciencias de la computación y teoría de la complejidad computacional. Es un problema que ha llevado al desarrollo de técnicas fundamentales para el campo de los algoritmos de aproximación. También es uno de los problemas de la Lista de 21 problemas NP-completos de Karp cuya NP-completitud fue demostrada en 1972.
- 집합 덮개 문제(set cover)는 전산학과 복잡도 이론에서 다루는 오랜 문제로, 어떠한 전체집합과 그 집합의 부분집합들이 주어졌을 때, 부분집합들 중에서 가능한 한 적은 집합을 골라서 그 집합들의 합집합이 원래 전체집합이 되도록, 즉 그 집합들이 원래 전제집합을 '덮도록' 집합을 선택하는 문제이다. 이때 집합을 가능한 한 적게 골라내는 것이 목표이다. 이 문제의 결정 문제판은 리처드 카프가 NP-완전임을 증명했던 최초의 21문제 중 하나이다. 엄밀히 정의하면, 전체집합 와 의 부분집합으로 이루어진 집합족 가 있을 때, 어떠한 부분집합족 에 대해 에 속하는 집합들의 합집합이 가 된다면, 를 덮개라고 정의한다. 이때 집합 덮개 문제의 결정 문제판은 쌍과 정수 가 입력될 때, 이하인 집합 덮개가 있는지 묻는 문제이다. 최적화 문제판의 경우 입력이 쌍뿐이고, 집합 수가 가장 적은 덮개를 찾는 문제가 된다. 이 문제는 결정 문제의 경우 NP-완전, 최적화 문제의 경우 NP-난해에 속한다.
- Задача про покриття множини є класичним питанням інформатики і теорії складності. Ця задача узагальнює NP-повну задачу про вершинне покриття (і тому є NP-складною). Попри те, що задача про вершинне покриття подібна до цієї, підхід, використаний у наближеному алгоритмі, тут не працює. Замість цього ми розглянемо жадібний алгоритм. Отриманий за ним розв'язок буде гіршим від оптимального в логарифмічне число разів. Із зростанням розміру задачі якість розв'язку погіршується, але все ж досить повільно, тому такий підхід можна вважати корисним.
- The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. More formally, given a universe and a family of subsets of , a cover is a subfamily of sets whose union is . In the set covering decision problem, the input is a pair and an integer ; the question is whether there is a set covering of size or less. In the set covering optimization problem, the input is a pair , and the task is to find a set covering that uses the fewest sets.
- Das Mengenüberdeckungsproblem (oft mit set-covering-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik. Es fragt, ob zu einer Menge und Teilmengen von und einer natürlichen Zahl eine Vereinigung von oder weniger Teilmengen existiert, die der Menge entspricht (Überdeckung). Als Optimierungsproblem formuliert, wird eine Überdeckung mit möglichst kleiner Anzahl der Teilmengen gesucht oder, falls den Teilmengen Kosten zugeordnet sind, eine Überdeckung mit geringsten Kosten.
- O problema de cobertura de conjuntos é uma questão clássica em combinatória, ciência da computação, pesquisa operacional e teoria da complexidade computacional . É um dos 21 problemas NP-completos de Karp mostrado ser NP-completo em 1972. É um problema "cujo estudo levou ao desenvolvimento de técnicas fundamentais para todo o campo" dos algoritmos de aproximação . A versão de decisão da cobertura do conjunto é NP-completa, e a versão de otimização / busca da cobertura do conjunto é NP-difícil .
- En informatique théorique, le problème de couverture par ensembles (Set Cover problem en anglais) est un problème d'algorithmique particulièrement important car c'est l'un des 21 problèmes NP-complets de Karp. Étant donné un ensemble A, on dit qu'un élément e est couvert par A si e appartient à A. Étant donné un ensemble U et une famille S de sous-ensembles de U, le problème consiste à couvrir tous les éléments U avec une sous-famille de S la plus petite possible. Une version plus générale consiste à assigner des poids aux éléments de S, et à chercher la sous-famille de poids minimal.
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
