Покрытие множества почти последовательными подмножествами: различия между версиями

Экземпляры SET COVER встречаются, например, при оптимизации железнодорожного транспорта, где задача заключается в том, чтобы определить места построения новых железнодорожных станций. Каждая строка в этом случае соответствует существующему населенному пункту, а каждый столбец – точке на существующем пути, где можно было бы построить станцию. Столбец c покрывает строку r, если населенный пункт, соответствующий r, лежит в пределах заданного радиуса вокруг места, соответствующего c.