ayuda con este proyacto.

loca_sexy
11 de Enero del 2006
Proyecto 1. Armas

Cierto país imperialista persiste en ocultar sus armas de destrucción masiva a la comunidad internacional. La ONU ha decidido planificar una serie de inspecciones exhaustivas para analizar todos los posibles almacenes de armas. Tenemos un mapa T de localizaciones, con n sitios sospechosos y los caminos existentes entre ellos. En el mapa, T[i, j] valdrá 1 si existe un camino entre i y j, y 0 en caso contrario. Existen varios equipos de inspectores, que parten inicialmente del mismo sitio. Cada equipo visita un sitio durante un día y se desplaza por la tarde (es decir, en todos los caminos tardamos un tiempo unitario).

Hay que tener en cuenta que las armas se pueden mover de sitio, para evitar ser descubiertas. Las armas se mueven por los mismos caminos que los inspectores, aunque lo hacen por la noche (es decir, no se pueden cruzar por el camino).

Para garantizar que el plan de inspecciones sea efectivo debemos velar por lo siguiente:

1) todos los sitios son inspeccionados,
2) hay que evitar que se puedan mover armas a un sitio que ya ha sido inspeccionado; para ello, debemos garantizar que cualquier posible camino entre un sitio inspeccionado y uno no inspeccionado pase por un sitio que esté siendo inspeccionado.

Diseñar un algoritmo para resolver los siguientes problemas.
Mostrar gráficamente la ejecución sobre el mapa de la figura de abajo.

a) Suponiendo que todos los equipos de inspectores parte del sitio I, encontrar cuánto tiempo tarda el plan de inspecciones (como mínimo), qué sitios se deben visitar cada día, cuántos equipos de inspectores necesitamos en total y por dónde se debe mover cada equipo. Ejecutar con I = 1.
b) Suponiendo que queremos minimizar el tiempo total del plan de inspecciones, encontrar desde qué sitio deben partir las inspecciones, qué sitios se deben visitar cada día y cuántos equipos de inspectores necesitamos.