Problema del vendedor ambulante
Los problemas del viajante se rigen por un vendedor y un conjunto de ciudades. El vendedor tiene que visitar cada una de las ciudades comenzando por una determinada (por ejemplo, la ciudad natal) y regresar a la misma ciudad. El desafío del problema es que el viajante de comercio necesita minimizar la duración total del viaje.
Supongamos que las ciudades son x 1 X 2 ..... X norte donde costo c yo denota el costo de viajar desde la ciudad x i ax j . El problema del vendedor ambulante consiste en encontrar una ruta que comience y termine en x. 1 que abarcará todas las ciudades con el mínimo coste.
Ejemplo: Un periodista deja caer el periódico diariamente en el área asignada de tal manera que tiene que cubrir todas las casas en el área respectiva con un costo de viaje mínimo. Calcule el costo mínimo de viaje.
El área asignada al agente donde debe dejar el periódico se muestra en la figura:
Solución: La matriz de costos-adyacencia del gráfico G es la siguiente:
costo yo =
El recorrido comienza desde la zona H. 1 y luego seleccione el área de costo mínimo alcanzable desde H 1 .
Marcar área H 6 porque es el área de costo mínimo alcanzable desde H 1 y luego seleccione el área de costo mínimo accesible desde H 6 .
Marcar área H 7 porque es el área de costo mínimo alcanzable desde H 6 y luego seleccione el área de costo mínimo accesible desde H 7 .
Marcar área H 8 porque es el área de costo mínimo alcanzable desde H 8 .
Marcar área H 5 porque es el área de costo mínimo alcanzable desde H 5 .
Marcar área H 2 porque es el área de costo mínimo alcanzable desde H 2 .
Marcar área H 3 porque es el área de costo mínimo alcanzable desde H 3 .
Marcar área H 4 y luego seleccione el área de costo mínimo alcanzable desde H 4 es H 1 Entonces, usando la estrategia codiciosa, obtenemos lo siguiente.
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
Por tanto, el coste mínimo del viaje = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroides:
Una matroide es un par ordenado M(S, I) que satisface las siguientes condiciones:
- S es un conjunto finito.
- I es una familia no vacía de subconjuntos de S, llamados subconjuntos independientes de S, tales que si B ∈ I y A ∈ I. Decimos que I es hereditario si satisface esta propiedad. Tenga en cuenta que el conjunto vacío ∅ es necesariamente miembro de I.
- Si A ∈ I, B ∈ I y |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
Decimos que una matroide M (S, I) está ponderada si hay una función de peso asociada w que asigna un peso estrictamente positivo w (x) a cada elemento x ∈ S. La función de peso w se extiende a un subconjunto de S por suma :
w (A) = ∑<sub>x∈A</sub> w(x)
para cualquier A ∈ S.
