¿Cuál es la diferencia entre el problema del vendedor ambulante y el problema del árbol de expansión mínima?

TSP: Dado un gráfico ponderado dirigido, ¿hay alguna manera de visitar todos los vértices en el gráfico EXACTAMENTE una vez? Este es el problema de decisión. Si la respuesta es SÍ, ¿cuál es el costo mínimo de tal recorrido? Este es un problema de optimización.

Se ha demostrado que ambos son “duros”. Es decir, la solución de tiempo polinomial para ellos probablemente no existe (noboby lo sabe).

MST: Dado un gráfico ponderado conectado, encuentre el árbol de expansión de manera que el costo total de todos los bordes en el árbol de expansión sea lo más pequeño posible. Si el gráfico está conectado, puede decir CON SEGURIDAD que existe un árbol de expansión. Hay algoritmos eficientes como Prim, Kruskal, por nombrar algunos para encontrar MST.

El árbol de expansión no necesita ser el camino. Puede tener ramas.

Nota: existen definiciones técnicas para duro, eficiente, etc.

Problema de vendedor ambulante

Dado un conjunto de ciudades y el costo del viaje entre cada par de ellas, el problema del vendedor ambulante (TSP) es encontrar la forma más barata de visitar todas las ciudades y regresar a su punto de partida.

La simplicidad de la declaración del problema es engañosa. TSP es uno de los problemas más intensamente estudiados en matemática computacional y, sin embargo, no se conoce ningún método de solución efectivo para el caso general. De hecho, la resolución del TSP resolvería el problema P versus NP y obtendría un premio de $ 1,000,000 del Clay Mathematics Institute.

Puedes ver una historia de TSP aquí.

Problema de árbol de expansión mínimo (MST)

Considere este problema: dado un conjunto de ciudades, ¿cómo puede conectar todas las ciudades de manera que se minimicen las distancias entre ellas? Es bastante obvio que las ciudades pueden tener múltiples rutas que las conectan. Para resolver esto, podemos utilizar el enfoque del algoritmo codicioso.

Ampliando esta idea: en la teoría de grafos, un árbol de expansión de un gráfico no dirigido es un subgráfico, que es un árbol, que incluye todos los vértices de G, con el mínimo número posible de aristas.

Un gráfico puede tener múltiples árboles de expansión. Y el problema nos pide que encontremos el que tenga costos mínimos de borde.

Fuentes / referencias

Problema de vendedor ambulante

Árbol de expansión mínimo – Wikipedia

Árbol de expansión – Wikipedia

Algoritmo de Prim – Wikipedia

Programación dinámica – Wikipedia

Editar

Una buena pregunta puede ser si podemos usar el árbol de expansión mínimo para resolver el problema del vendedor ambulante.

Trataré de responder esto en base a mi comprensión. Las entradas y correcciones son bienvenidas.

Considere el enfoque que utilizamos para resolver el problema MST. Utilizamos algoritmos codiciosos como el algoritmo Prims.

Un algoritmo codicioso es un paradigma algorítmico que sigue la heurística de resolución de problemas de hacer la elección óptima local en cada etapa con la esperanza de encontrar un óptimo global – Wiki

Para el problema del vendedor ambulante, queremos obtener la solución más óptima de todas las soluciones posibles. Una forma es pensar en utilizar un enfoque de programación dinámica.

La programación dinámica es un método para resolver un problema complejo dividiéndolo en una colección de subproblemas más simples, resolviendo cada uno de esos subproblemas una sola vez y almacenando sus soluciones – Wiki

Por lo tanto, podemos utilizar el enfoque MST, pero puede que no sea la solución más óptima.

¿Has leído la declaración del problema,

se dice con claridad que

‘Tsp’ pide un camino que cubra cada vértice mientras que (el camino) es el más corto. La dirección tiene un valor en su evaluación.

‘Mst’ pide un conjunto de bordes para que el árbol así formado sea de mín. Peso, sin valor de dirección en su evaluación.

More Interesting

¿Por qué usar un diagrama de flujo es una mala práctica en la programación?

¿Es cierto que no debería importarme tanto aprender lenguajes de programación sino construir una gran base de estructuras de datos y algoritmos?

¿Cuáles son los mejores algoritmos de partición de gráficos para gráficos grandes?

¿Cómo puedo mover puntos colocados al azar con un radio de 'visión' en una línea para cubrir completamente la línea y minimizar la distancia total recorrida?

¿Qué es el conocimiento estructurado?

¿La programación se trata de definiciones de variables, para bucles, ifs y estructuras de datos?

¿Cuáles son algunos de los recursos disponibles para los estudiantes de informática en predicción de la estructura secundaria de ARN?

Cómo evitar que el algoritmo de google para 'quiso decir' afecte mi sitio

¿Por qué obtener más puntos de datos soluciona el problema de la alta variación en un algoritmo de aprendizaje automático?

¿Cómo funciona la recursividad en el árbol de búsqueda binaria en orden? ¿Cómo se pueden explicar las llamadas recursivas, sin resumirlas como llamadas de pila?

¿Cómo se debe verificar si él / ella ha entendido el algoritmo de Paxos?

¿Por qué deberíamos instanciar una matriz en una línea diferente?

¿Qué tan difícil es la entrevista de Google? ¿Qué tipo de algoritmos y preguntas de ingenio espero?

Conozco la implementación básica de diferentes estructuras de datos como árboles, gráficos, colas y muchos más para inserción, eliminación, recorrido. Ahora, ¿cómo procedo a construir un sistema operativo?

¿Cómo está negando este código todos los números en mi matriz?