Набор от най-кратки пътища с много начало и много край

Имам проблем с най-краткия път в насочена претеглена графика. Познавам Dijkstra, BFS, DFS. Имам обаче a set of vertices S за начални точки и a set of vertices E to end. S и E не се припокриват. И така, как мога да намеря набора от ръбове с минимална сума от теглото на ръбовете? Наборът от ръбове не трябва да включва всички върхове в S, но трябва да reach all vertices in E. Трябва ли да започна с Dijkstra при всички пермутации на {Si, Ei} и да оптимизирам или пропускам някакъв важен алгоритъм, който трябва да знам? Или дори прекалявам с мислите...


optimization algorithm computer-science shortest-path dijkstra
person ZhijieWang    schedule 01.05.2014    source източник
comment
Добавете два върха, начало, свързано с всички върхове в S, и край, като всички върхове в E са свързани с. Пуснете Dijkstra на нова графика.   -  person user58697    schedule 01.05.2014
comment
най-краткият път (набор) обаче ще достигне End, но не е задължително да достигне всички върхове в E.   -  person ZhijieWang    schedule 01.05.2014
comment
Ако пътят е най-кратък от началото до края, той е най-краткият сред всички пътища от {S} до {E}. Освен ако не съм прочел съвсем грешно въпроса.   -  person user58697    schedule 01.05.2014
comment
Ако приемем, че има E1 и E2 в набор E. Може да стигнете до End през E1 и напълно да пропуснете E2.   -  person ZhijieWang    schedule 01.05.2014

Отговори (1)


arrow_upward
3
arrow_downward

Ако ви разбирам правилно, искате да намерите дървото с минимално тегло в графиката, което съдържа всички върхове на E и поне един връх от S.

Проблемът се нарича общо дърво на Steiner и е NP-твърд. Така че най-доброто, на което вероятно можете да се надявате, е алгоритъм с експоненциално време или някакъв вид приближение (минимално обхващащо дърво на цялата графика идва на ум, може би след премахване на някои ненужни поддървета).

Има просто DP решение, което работи в O(2^n * (n + m)): Нека f(S) е цената на минималното дърво в графиката, което обхваща всички възли в S. Може да се покаже, че има такова дърво T, така че теглото на T \ {x} е f(S \ {x}) за някои x, така че преходът може да се извърши в O(n + m).

person Niklas B.    schedule 01.05.2014
comment
@user1505108 Добре тогава, не е много очевидно, но проблемът е труден. - person Niklas B.; 01.05.2014
comment
@user1505108 Добавих O(2^n * (n + m)) DP алгоритъм, ако това е полезно. Поне не зависи експоненциално от броя на ръбовете. - person Niklas B.; 01.05.2014