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