Me enfrento con el siguiente problema:

Dado

Un gráfico no dirigido, donde cada borde E tiene:Et - el tiempo que lleva atravesar EEr - la recompensa por atravesar E

Gol:

Problema 1: Dado el período de tiempo T, encuentra la ruta más gratificante en el gráficoProblema 2: Dado el período de tiempo T, encuentre el ciclo más gratificante en la gráfica (después del período T, el agente debe estar nuevamente en el punto de inicio).

Notas:

Si un borde se recorre parcialmente, la recompensa es proporcional a la porción recorridaLa recompensa se puede reclamar solo una vez por cada borde atravesado (o parte de)Un camino / ciclo puede comenzar en cualquier punto dado (ya sea en un vértice, oa lo largo de un borde)

Mis preguntas:

¿Se trata de un problema conocido (tiene un nombre? ¿Se ha estudiado antes?).¿Es NP-duro?¿Alguna idea de cómo abordarla?

Problemas relacionados conocidos:

El problema de la orientación. - Las recompensas están basadas en vértices (). En mi caso, las recompensas están basadas en el borde.Problema rentable del viaje del arco - El objetivo es encontrar un conjunto de ciclos en el gráfico que maximice la recolección de ganancias menos los costos de viaje.Editar: El problema de enrutamiento de arco capacitado no dirigido con ganancias - Bastante similar a mi problema, pero se da un vértice de depósito (inicio, final de cada ciclo), se satisface la desigualdad del triángulo y el problema se generaliza a un conjunto de agentes, todos comenzando y terminando en el mismo depósito).