Минимальное связующее дерево между местом начала и набором нужных узлов

Question

Я пытаюсь определить оптимальный случай поиска, чтобы сравнить с алгоритмом поиска, который я написал.

У меня есть набор узлов с пометкой «обязательный» и узел с надписью «start», остальные обозначены «необязательно». Я хочу найти оптимальное количество узлов, которые мне нужно будет расширять, чтобы обнаружить все необходимые узлы, учитывая, что я первый раз расширяю узел «start».

• Я считаю, что я ищу, это минимальное остовное дерево, но обрезка всех ветвей, которые не заканчиваются на «требуемом» узле. Это Steiner tree problem?
• Если мой график невзвешен, это размер дерева Штейнера и Минимальное связующее дерево - то же самое?
• Что, если что-нибудь могу сказать о размере дерева? то есть что-то вроде (размер минимального размера spanning tree = средний короткий путь * # требуемые узлы ... Я не думаю, что это правда, но было бы неплохо вычислить среднее значение, основанное на связности или что-то еще).

Несколько замечаний:

1. Это не проблема путешествия продаж, потому что я не нужен путь существовать между каждым узлом требуется, я просто хочу, чтобы открыть каждый нужный узел.
2. Мой граф неориентированный и невзвешенное (или в равной степени взвешенным по этому вопросу)
3. Мой график имеет в среднем около 100 требуемых узлов, и, возможно, тысячи дополнительных узлов

Answer 1

У меня есть набор узлы с пометкой «требуется» и узел с пометкой «старт», остаток отмечены «необязательно». Я хочу найти оптимальное количество узлов Мне нужно было бы расширить, чтобы обнаружить все необходимые узлы, заданные , что я первый раз расширяю узел «start».

Если стоимость расширения узла может быть произвольной, то это узел-взвешенного Штайнер проблема дерева, которое, под благовидным сложностями теоретико-предположению, не имеет алгоритма аппроксимации полинома времени с отношением, что это о (log n).

Я считаю, что я ищу это минимальное покрывающее дерево, но подрезают всех ветвей, которые не заканчиваются на «требуется» узел.

Нет, это вообще не оптимально. Так, например, с графиком

 s 
     /|\ 
    /| \ 
    * | * 
/ | \ 
/ | \ 
r1----*----r2, 

один из возможных МСТ выглядит как /|\ или /\ при обрезке, но оптимальное решение выглядит как _|_.

Что делать, если что-нибудь могу сказать о размере дерева?

Теоретически вы можете получить нижнюю границу путем решения двойного релаксации LP целочисленной программы для дерева Штейнера (фактически с графиком размера, о котором вы думаете, это не удивило бы если бы решатель мог определить оптимальное дерево Штейнера прямо вверх).

Практически говоря, это не то, как люди оценивают алгоритмы поиска.