Я столкнулся со следующей проблемой:

Дано

Ненаправленный граф, где каждое ребро E имеет:Et - время прохождения EEr - награда за прохождение E

Цель:

Проблема 1: Учитывая период времени T, найдите наиболее полезный путь на графикеПроблема 2: При заданном периоде времени T найдите самый полезный цикл на графике (после периода T агент должен снова оказаться в начальной точке).

Примечания:

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

Мои вопросы:

Является ли это известной проблемой (есть ли у нее имя? Было ли это изучено ранее?).Это NP-жесткий?Есть идеи как подойти?

Известные связанные проблемы:

Проблема ориентирования - Награды основаны на вершине (). В моем случае награды основаны на преимуществах.Выгодная задача Arc Tour - Цель состоит в том, чтобы найти набор циклов на графике, который максимизирует сбор прибыли за вычетом командировочных расходов.Редактировать: Проблема ненаправленной емкостной маршрутизации с прибылью - Очень похоже на мою проблему, но дается вершина депо (начало, конец каждого цикла), неравенство треугольника удовлетворяется, и задача обобщается на набор агентов, все из которых начинаются и заканчиваются в одном и том же депо).