TL; DR Мне нужно найти все возможные способы прохождения неориентированного циклического, возможно, несвязного графа, чтобы найти все наборы связанных узлов, которые удовлетворяют определенным критериям.
Существует график узлов, где каждому узлу присваивается значение, а ребра представляют совместимые узлы.
Совместимые узлы могут быть объединены в набор, но только если каждый из узлов совместим со всеми остальными. Например, приведен следующий график, представленный в виде списка соответствия:
0: 2, 3
1:
2: 0, 4, 6, 7
3: 0, 4, 6, 7
4: 2, 3, 5, 6
5: 4, 7
6: 2, 3, 4, 6
7: 2, 3, 5, 6
Узлы {4, 5} могут образовывать набор вместе как узлы {3, 4, 6}, в то время как узел 1 может формировать только один набор элементов.
Теперь, учитывая, что каждый узел содержит значение, найдите n наборов с наибольшим объединенным значением. Для приведенного выше примера, если узлы имеют следующие значения:
0: 4
1: 6
2: 4
3: 5
4: 6
5: 3
6: 3
7: 5
Решением для n = 2 являются множества {3, 4, 6} и {2, 7} с объединенным значением 23.
Подход, который я начал, заключается в использовании модифицированной версии DFS, в которой стек заполнен только узлами, которые до сих пор совместимы со всеми узлами в текущем наборе. Если таких узлов нет, мы создаем новый набор и продолжаем работу с узлами, которые еще не были посещены.
псевдокод:
// As long as we have any unvisited nodes
while(visited.contains(false))
{
// Take first unvisited node and push it onto a stack
stack.push(find_first(visited, false));
// Modified DFS
while (!stack.empty())
{
Node n = stack.pop();
// Add the node to the set (this will always be either first or compatible node)
temp_set.add(n);
// Find all compatible nodes by finding intersection of the adjecency list of the nodes
// already in the set
compatibleNodes = find_all_compatible_nodes(set);
// Add the first compatible, unvisited node we find to the stack
for(c : compatibleNodes)
{
if(!visited[c])
{
stack.push(c);
visited[c] = true;
break;
}
}
}
// Once we run out of compatible nodes for this set, we add it to candidate solution and start with a new one
candidateSolution.add(temp_set);
temp_set.clear();
}
// Once we've visited all the nodes, we have a candidate solution where two sets with the highest score are the possible answer
Теперь это работает для единственного возможного решения, но не в состоянии исследовать различные пути прохождения. По сути, он строит дерево, в котором каждая ветвь представляет набор и в который включены все узлы графа. Мне нужно найти все возможные деревья, которые можно построить, чтобы найти дерево с наибольшим количеством очков.
Мне кажется, я понимаю, что мне нужно делать дальше. Начиная с последнего решения, вернитесь к точке, где можно было бы выбрать альтернативный путь, и постройте новое решение оттуда. Затем продолжайте делать это, пока я не вернусь к первому узлу и не останется больше узлов для посещения. Однако я не могу обернуть голову вокруг реализации. Любая помощь приветствуется.