¿Un algoritmo del camino más corto para grafos dirigidos ponderados por nodos que tienen nodos "AND-OR"?

Question

Estoy tratando con grafos dirigidos que constan de dos tipos de nodos (con ponderación única no negativa), los nodos "OR" y los nodos "AND". Dado un único origen y un único destino, quiero encontrar el camino más corto (con un peso mínimo) entre ellos.

Los nodos "OR" son nodos regulares: pueden ser visitados si al menos uno de sus padres ha sido visitado primero. Los nodos "AND" tienen una restricción: todos sus padres deben haber sido visitados primero.

Ahora bien, cuando se trata de encontrar el camino más corto hacia un nodo "AND", la simple suma del peso de los padres del nodo no funcionará, ya que podrían tener antepasados en común, lo que llevaría a que el peso de los antepasados se contabilizara varias veces.

¿Alguien conoce un algoritmo que solucione esto? Y si es así, ¿cuál sería su complejidad? No he podido encontrar mucho en la literatura. Probablemente no estoy utilizando la terminología correcta. ¿O?

¡Muchas gracias!

Answer 1

Podemos reducir el problema del vendedor viajero (que es fuertemente NP-duro) a su problema. Para comprobar cuál es el mejor camino que empieza y termina en $v$ , añade un vértice ficticio $v_\mathrm{and}$ de tipo "y" con aristas a todos los vértices de $V$ y siendo sus longitudes iguales a las distancias respectivas en $G$ y a continuación, ejecute una consulta para su problema entre $v$ y $v_\mathrm{and}$ . Mínimo sobre las respuestas para todos los vértices de $V$ será la respuesta al problema del TSP.

Espero que esto ayude $\ddot\smile$

Editar: Se ha eliminado la parte de la cobertura de los vértices, que era incorrecta.