Я пишу алгоритм перебора для решения покрытия вершин следующим образом:
BruteForceVertexCover( Graph G = (V,E) ){
for size= 1 ... |V|
vector<int> v = {0...size-1}
do{
if(test(G, v)) return v; //test if v covers G
}
while(v has next combinations of lenght size);
return empty vector<int>;
}
//this stops when find a answer, and it will find,
//since it tries all combinations of all sizes
где
bool test( Graph G = (V,E), vector<int> v ){
for each u in v:
for each w in G[u]
remove u from G[w] //this is linear in size of vector G[w]
clear G[v] //removed all (bidirectional) edges that have u
for i = 0 ... |V|
if(G[i] is not empty) return false;
return true;
}
Я пытаюсь сделать это на множестве графиков (но их максимальный размер составляет 20 вершин), и на это уходит десятилетие … Могу ли я оптимизировать эту грубую силу, чтобы она работала быстрее?
Задача ещё не решена.
Других решений пока нет …