8.5.1. Постановка задачи

Многие комбинаторные оптимизационные задачи сводятся к задаче о кратчайшем покрытии, которая ставится следующим образом. Пусть даны некоторое множество А = {a₁, a₂, …, a_n} и совокупность его подмножеств В₁, В₂, …, В_т, т. е. B_i  A, i = 1, 2, …, m, причем В₁  В₂  …  В_т = А. Требуется среди данных подмножеств выделить такую совокупность , … ,с минимальнымk, чтобы каждый элемент из А попал хотя бы в одно из (j = 1, 2, …, k), т. е. .

Одной из интерпретаций этой задачи является задача о переводчиках. Из некоторого коллектива переводчиков, число которых т и каждый из которых владеет несколькими определенными языками, требуется скомплектовать минимальную по числу членов группу, такую, чтобы она смогла обеспечить перевод с любого из заданного множества языков, число которых п. Здесь А – множество языков, перевод с которых требуется обеспечить, а В_i – множество языков, которыми владеет i-й переводчик.

Удобно рассматривать матричную формулировку данной задачи, при которой совокупность В₁, В₂, …, В_т задается в виде булевой матрицы, строки которой соответствуют подмножествам из данной совокупности, а столбцы – элементам множества А. Элемент i-й строки и j-го столбца имеет значение 1, если и только если a_j  B_i. В этом случае говорят, что i-я строка покрывает j-й столбец. Требуется найти такое множество строк данной матрицы, чтобы каждый ее столбец имел единицу хотя бы в одной строке из этого множества, и при этом мощность выбранного множества должна быть минимальной.