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 x1X2..... Xnortedonde costo cyodenota el costo de viajar desde la ciudad xiaxj. El problema del vendedor ambulante consiste en encontrar una ruta que comience y termine en x.1que 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:
costoyo=
El recorrido comienza desde la zona H.1y luego seleccione el área de costo mínimo alcanzable desde H1.
mi grillo vivo en
Marcar área H6porque es el área de costo mínimo alcanzable desde H1y luego seleccione el área de costo mínimo accesible desde H6.
Marcar área H7porque es el área de costo mínimo alcanzable desde H6y luego seleccione el área de costo mínimo accesible desde H7.
imprimir matriz en java
Marcar área H8porque es el área de costo mínimo alcanzable desde H8.
Marcar área H5porque es el área de costo mínimo alcanzable desde H5.
Marcar área H2porque es el área de costo mínimo alcanzable desde H2.
Marcar área H3porque es el área de costo mínimo alcanzable desde H3.
Marcar área H4y luego seleccione el área de costo mínimo alcanzable desde H4es H1Entonces, 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:
cómo encontrar el tamaño del monitor
- 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.