Asignacion de tareas a trabajadores

[morelo]

Hola, tengo q hacer un problema de Intelgencia artificial y no tengo ni idea de como plantearlo.

El problema es q tenemos N trabajadores y los debemos asignar a N tareas, y se quiere obtjer el coste minimo.

Ejmeplo si tenemos

                             TAREA 1               TAREA 2                TAREA 3
Trabajador 1                  12                        43                     15

Trabajador 2                  9                         10                      6

Trabajador 3                  5                         13                      29

Pues debería sacar la asignacion optima,

Tampoco se cual podría ser la función heurística.  Ademas debo resolver el problema por 2 algoritmos de Busqueda no Informada y otros dos de Busqueda informada.

A ver si alguien me puede ayudar, o si no, pues q conozca algun enlace a otras paginas o docuemntos que me ayuden



Gracias

[Pogacha]

Eso en realidad no es un problema de IA sino mas bien de investigacion operativa.
Programacionalmente se resuelve con un backtracking.
Tenes que hacer una rutina evaluadora y una rutina que te genere todas las permutaciones secuencialmente.
Mientras recorres todas las permutaciones memorizas el optimo resultado.

Código [Seleccionar] Expand

Mejor_Evaluacion  = Peor_Valor;
Indice_Del_Mejor = Imposible;

Para Cada Permutacion {
 Evaluacion_Actual = Evaluar ( Permutacion(indice_de_permutacion_actual) )
 Si( Evaluacion_Actual > Mejor_Evaluacion ) {
     Mejor_Evaluacion = Evaluacion_Actual;
     Indice_Del_Mejor = indice_de_permutacion_actual;
 }
}


Saludos

[morelo]

no se si es exactamente eso, el tema esta es que es para asigantura de INTELIGENCIA ARTIFICIAL, y tengo q presentar el problema, decir el estado inicial, y final, y dibujar el arbol de decision. Entonces no veo claro como se haría con esa forma,

si tu lo ves claro te agradecería mas ayuda


gracias

[ethernet]

Suena al típico problema de programación lineal:

http://es.wikipedia.org/wiki/Programaci%C3%B3n_lineal

[Marci]

Puestos a optimizar supongo que se podría con un algoritmo genético.

[Mars Attacks]

A mí me suena a deberes de una clase a la que no has prestado atención ;)

¿Qué tal si vas a tutorías?

[Daemon]

2 algoritmos de busqueda no informada: profundidad y anchura
2 algoritmos de busqueda informada: greedy y A*.

Funcion heuristica (p.e.): la suma de los costes menores que queden para llegar a la solucion (aunque para el greedy te la vas a tener que currar mas).

P.D.: estoy de acuerdo con Mars.

[imaGame]

En el curro resolvimos algo similar con el Algoritmo Húngaro (se utiliza para eso desde hace bastantes añitos)

[Pogacha]

2 algoritmos de busqueda no informada: profundidad y anchura
2 algoritmos de busqueda informada: greedy y A*.

Funcion heuristica (p.e.): la suma de los costes menores que queden para llegar a la solucion (aunque para el greedy te la vas a tener que currar mas).

P.D.: estoy de acuerdo con Mars.

Seré tan ignorante ...
No veo relación de estos algoritomos con la asígnación de tareas.

Si las restricciones fueran:
1 trabajador 1 tarea, todas las tareas ocupadas.

Entonces la solución bruta es un backtracking con las siguientes posibles optimizaciones:
Linea de corte obtenida por la primera euristica, la cual ayuda mucho
Eliminación de rama por mejor caso posible, la cual ayuda mucho mas!

Y si tenes tiempo:
Selección de rama por caso posible promedio, ayuda ligeramente mas.

Saludos.

[Daemon]

Pogacha, la solucion que tu has comentado (bracktracking) y las que yo digo son basicamente las mismas, lo unico que yo he hecho es especificar distintas maneras de moverse a traves del espacio de estados (es decir distintas maneras de generar una solucion); seria lo que tu has llamado "Permutacion(indice_de_permutacion_actual)". Aunque si bien es cierto que para el greedy..., pues no se si es correcto decir que es un algoritmo valido para este problema, ya que se trata de sacar la solucion optima y no se si habra alguna heuristica (aparte de calcular la solucion final real) que te diga cual es realmente el siguiente paso a dar (tampoco lo he pensado mucho).

Un saludo.

[veketor]

Si lo puedes enfocar como un problema de red compatible, podrías usar el algortimo de Ford-Fulkerson o una de sus variantes.