k-минималды жайылмалы ағаш (k MST) мәселесі: төмен құнмен k төбелі ағаш табу. NP-қиын, бірақ полиномдық уақытта жуықтауға болады. Графтар, алгоритмдер.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Теориялық компьютерлік ғылымда зерттелетін k ең кішкентай қамтитын ағаш мәселесі, дәл k төбесі бар және үлкен графтың ішкі графигін құрайтын ең төмен құнға ие ағашты табуды талап етеді. Ол k MST немесе қабырғалармен салмақталған k кардиналдылық ағашы деп те аталады. Мұндай ағашты табу NP-қиын мәселе, бірақ оны полиномиалдық уақытта тұрақты жуықтау қатынасымен жуықтауға болады.
The k minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly k vertices and forms a subgraph of a larger graph. It is also called the k MST or edge weighted k cardinality tree. Finding this tree is NP hard, but it can be approximated to within a constant approximation ratio in polynomial time.
Мәселе туралы мәлімдеме
Мәселеге кіретін дерек – шеттерінде салмағы бар бағытталмаған граф, ал шығыс – k төбесі және k-1 қабырғасы бар ағаш, мұнда шығыс ағашының барлық қабырғалары кіріс графқа жатады. Шығыстың құны – оның қабырғаларының салмақтарының қосындысы, ал мақсат – ең төмен құны бар ағашты табу. Бұл мәселені Ravi және басқалар тұжырымдады. Сонымен қатар, мәселенің геометриялық нұсқасы қарастырылды, оны граф мәселесінің ерекше жағдайы ретінде қарастыруға болады. Геометриялық k ең аз қамтитын ағаш мәселесінде кіріс – жазықтықтағы нүктелер жиынтығы. Тағы да, шығыс k нүктесін төбелері ретінде қамтитын ағаш болуы керек, оның қабырғаларының жалпы Эвклидтік ұзындығын азайту мақсатында. Яғни, бұл Эвклидтік қашықтықтарды салмақ ретінде қолданылатын толық графтың k ең аз қамтитын ағашы.
The input to the problem consists of an undirected graph with weights on its edges, and a The output is a tree with k vertices and k − 1 edges, with all of the edges of the output tree belonging to the input graph. The cost of the output is the sum of the weights of its edges, and the goal is to find the tree that has minimum cost. The problem was formulated by and by
Ravi et al. also considered a geometric version of the problem, which can be seen as a special case of the graph problem. In the geometric k minimum spanning tree problem, the input is a set of points in the plane. Again, the output should be a tree with k of the points as its vertices, minimizing the total Euclidean length of its edges. That is, it is a graph k minimum spanning tree on a complete graph with Euclidean distances as weights.
Есептеу күрделілігі
k тұрақты шама болғанда, k ең аз аралықтағы ағаш мәселесін полиномдық уақытта, барлық k төбелік жиынтықтарды қарастыратын қарапайым іздеу алгоритмі арқылы шешуге болады. Дегенмен, k айнымалы болғанда, k ең аз аралықтағы ағаш мәселесі Штайнер ағашы мәселесінен азайту арқылы NP-толық екені көрсетілген. Осыған ұқсас жағдай k ең аз аралықтағы ағаш мәселесі үшін де орынды. Жалпы мәселе үшін белгілі ең жақсы жуықтау 2 жуықтау коэффициентіне жетеді, және бұл жуықтау бастапқы-қос схемасына көп көлемде сүйенеді. Егер кіріс деректері Евклид жазықтығындағы нүктелерден тұрса (олардың кез келген екеуі ағашта олардың арақашықтығымен байланыстырылуы мүмкін), онда осы мәселені шешу үшін полиномдық уақытты жуықтау схемасы жасалған.
When k is a fixed constant, the k minimum spanning tree problem can be solved in polynomial time by a brute force search algorithm that tries all k tuples of vertices. However, for variable k, the k minimum spanning tree problem has been shown to be NP hard by a reduction from the Steiner tree problem. the same is true for the k minimum spanning tree problem. The best approximation known for the general problem achieves an approximation ratio of 2, and is by This approximation relies heavily on the primal dual schema of When the input consists of points in the Euclidean plane (any two of which can be connected in the tree with cost equal to their distance) there exists a polynomial time approximation scheme devised by .