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₁X₂..... X_nortedonde costo c_yodenota el costo de viajar desde la ciudad x_iax_j. El problema del vendedor ambulante consiste en encontrar una ruta que comience y termine en x.₁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:

cómo cambiar el nombre de un directorio en Linux

Solución: La matriz de costos-adyacencia del gráfico G es la siguiente:

costo_yo=

El recorrido comienza desde la zona H.₁y luego seleccione el área de costo mínimo alcanzable desde H₁.

mi grillo vivo en

Marcar área H₆porque es el área de costo mínimo alcanzable desde H₁y luego seleccione el área de costo mínimo accesible desde H₆.

Marcar área H₇porque es el área de costo mínimo alcanzable desde H₆y luego seleccione el área de costo mínimo accesible desde H₇.

imprimir matriz en java

Marcar área H₈porque es el área de costo mínimo alcanzable desde H₈.

Marcar área H₅porque es el área de costo mínimo alcanzable desde H₅.

Marcar área H₂porque es el área de costo mínimo alcanzable desde H₂.

Marcar área H₃porque es el área de costo mínimo alcanzable desde H₃.

Marcar área H₄y luego seleccione el área de costo mínimo alcanzable desde H₄es H₁Entonces, usando la estrategia codiciosa, obtenemos lo siguiente.

 4 3 2 4 3 2 1 6 H<sub>1</sub> &#x2192; H<sub>6</sub> &#x2192; H<sub>7</sub> &#x2192; H<sub>8</sub> &#x2192; H<sub>5</sub> &#x2192; H<sub>2</sub> &#x2192; H<sub>3</sub> &#x2192; H<sub>4</sub> &#x2192; <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:

cómo encontrar el tamaño del monitor

1. S es un conjunto finito.
2. 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.
3. 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) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

para cualquier A ∈ S.