Каким алгоритм сделать остов неориентированного взвешенного графа с весами на ребрах и вершинах?
Добрый день. Вопрос задан некорректно, может быть, но все же. Есть значит граф неориентированный. Представим, что это точки на карте. Веса на ребрах - расстояния меж ними. НО. У каждой точки будет, скажем, коэффициент приоритетности от 1 до 10. Так же у меня есть бюджет, который позволяет обойти не все точки. В итоге нужен алгоритм, который бы построил остов графа учитывая расстояние меж точками + важность данной точки? Пробежался по основным алгоритмам (Краскала, Прима, Борувки), но они не учитывают "важность точки", которую нужно посетить.
Да, я же говорю, не очень корректно задан вопрос, не знаю как максимально правильно его задать. Но у меня как раз тот случай, когда важность вершить должна колыхать..
longclaps, да, тут я) Ну, примерно вот такой результат хочется получать. Я так подумал, что раз у меня такие запросы, то мне этот коэффициент важности, так сказать, и расстояния меж графами нужно сводить к одним единицам (ну, допустим, если я считаю деньги, то расстояние должно быть так же в денежном эквиваленте, допустим)
SmaiL, смотрите: честного решения (кроме прямого перебора) я тут не жду. Причина в том, что алгоритмы построения мин. остовного дерева - они, грубо говоря, минимизируют метры, а вы хотите, удерживаясь в бюджете метров, максимизировать килограммы.
Минимизировать можно что-то одно, но как привести метры к килограмам?
Есть идея некоторой эвристики. Идея этой идеи в том, чтобы мелкие, малоценные вершины вытеснить на периферию графа, в листья, и там их можно помаленьку обрывать, не нарушая связности оставшегося дерева.
Припишем каждой вершине вес, ценной - маленький, бросовой - большой (о величинах позже). Добавим к весу каждого ребра сумму весов его вершин. На полученном графе построим остовное дерево. Вернём оставшимся граням исходные веса. Ну и будем обрывать малоценные листья, пока не влезем в бюджет.
