Proyecto Final (secretaria de riesgo)

[geyo89]

La secretaría de riesgos del Ecuador (SRE) quiere evitar que las lluvias del próximo fenómeno del niño causen que las ciudades del Ecuador queden aisladas entre si. Esto requiere tener planes de contingencia para reparar las vías cortadas por el desbordamiento de los ríos. Idealmente, cuando una carretera se daña se envía un equipo caminero para repararla desde un centro de control. Lamentablemente,la SRE solo tiene presupuesto para instalar dos centros de control. Para decidir en que ciudades instalar cada centro de control la SRE ha estudiado cual es la probabilidad de que una carretera dada sea cortada por la lluvia (números mas grandes implican mayor riesgo). Esto se resume en una matriz de riesgo. También ha estimado el costo de reparación ( un número mayor implica mayor gastos) para reparar una carretera. Esto se resume en una matriz de costos. Adicionalmente, el costo de mover un equipo caminero es proporcional a la distancia en Kilómetros del la carretera dañada. Esto se resume en una matriz de distancia.

En base a esta información se quiere determinar:

1)¿Donde debería la SRE colocar los centros de control para mantener la red de carreteras tan conectada como sea posible al menor costo?

2) Si se dañan las carreteras a una taza de una carretera por día a partir del inicio del fenómeno de niño, cuando deberían comenzar las reparaciones.

[DarK_FirefoX]

Ajá...¿Y que has hecho?

Aquí no se resuelven tareas ni proyectos.

Debes intentar hacerlo y preguntar dudas puntuales. En tal caso te podremos ayudar. No esperes a que te lo hagamos todo.

Salu2s

PD: http://foro.elhacker.net/reglas.htm

[geyo89]

obvio, es primera vez que uso el foro. mande el tema pero olvidé hacer preguntas.. obvio aparte de las que tengo que responder en la tarea jajaja

[geyo89]

yo se que e algoritmo de kruskal me haya el árbol de expansión mínima para un grafo G. pero si me dicen que debo de encontrar un vertice optimo donde colocar el centro control donde minimicen costos, y me dan tres grafos diferentes la verdad me pierdo...   

[DarK_FirefoX]

- No hagas doble post

yo se que e algoritmo de kruskal me haya el árbol de expansión mínima para un grafo G. pero si me dicen que debo de encontrar un vertice optimo donde colocar el centro control donde minimicen costos, y me dan tres grafos diferentes la verdad me pierdo...   

Exacto, el Algoritmo de Kruskal determina un Arbol Abarcador de Costo Mínimo (AACM) de G, son variantes de un algoritmo genérico solo que tiene una forma diferente de determinar las aristas seguras.

Ahora, Kruskal encuentra la arista segura para añadir al árbol creciente, seleccionando, entre todas las aristas que enlazan árboles distintos en el bosque G_a, la arista <u, v> de menor peso (liviana)

Ten en cuenta que Kruskal se basa en una estrategia glotona.

¿Con que estructura de datos estás implementando el algoritmo?
- Mi recomendación es usar Conjuntos Disjuntos

¿Con que estructura de datos estás implementando un grafo?
- Aqui puedes utilizar una Lista de Adyacencia o una Matriz de Adyacencia. Teniendo en cuenta que el costo si utilizas la Lista de Adyacencia es O(|E| log |V|) y si utilizas la Matriz de Adyacencia o el grafo es denso, te quedaría el costo O(|V|² log |V|)

De igual manera, esto te daría el arbol abarcador de costo mínimo, creo que después para ver la posición óptima para colocar los centros deberías utilizar otro algoritmo como DFS o BFS.

Espero haberte ayudado en algo, ve trabajando en base a esto y ve mostrando en donde tienes más dudas.

Salu2s