Algoritmos voraces
Publicado por Carlos (1 intervención) el 25/04/2016 03:20:35
Hola buen dia a todos, soy estudiante de programación y quisiera saber si alguno me puede dar una idea de como realizar el siguiente problema utilizando algoritmos voraces.
Encontrar una buena solución para el siguiente problema usando un algoritmo voraz. Explicar el funcionamiento del algoritmo: cuál es el conjunto de candidatos, la función de selección, la función para añadir un elemento a la solución, el criterio de finalización, el criterio de coste, etc.
En una votación existen n candidatos y m votantes. La probabilidad de que un votante i vote al candidato j la conocemos a priori, y viene dada por P[i, j]. Un votante cualquiera a puede ser coaccionado para que vote al candidato que queramos, por ejemplo el p, para lo cual tenemos que pagarle C[a] ptas. Con esto, nos aseguramos que P[a, p] = 1, y P[a, j] = 0, para j p.
El objetivo consiste en gastarse la mínima cantidad de dinero, coaccionando a los votantes necesarios, para garantizar que un candidato p dado se llevará al menos el 70% de los votos (de acuerdo con las probabilidades esperadas). La solución estará compuesta por la lista de votantes a los cuales hay que coaccionar.
Aplicar el algoritmo diseñado al siguiente ejemplo: n = 2 candidatos, m = 7 votantes, p = 1. Porcentajes y costes de coacción:
Votantes
1 2 3 4 5 6 7
P[i, 1] 0.2 0.1 0.8 0.5 0.6 0.2 0
P[i, 2] 0.8 0.9 0.2 0.5 0.4 0.8 1
C[i] 4 3 2 5 3 3 5
Gracias
Encontrar una buena solución para el siguiente problema usando un algoritmo voraz. Explicar el funcionamiento del algoritmo: cuál es el conjunto de candidatos, la función de selección, la función para añadir un elemento a la solución, el criterio de finalización, el criterio de coste, etc.
En una votación existen n candidatos y m votantes. La probabilidad de que un votante i vote al candidato j la conocemos a priori, y viene dada por P[i, j]. Un votante cualquiera a puede ser coaccionado para que vote al candidato que queramos, por ejemplo el p, para lo cual tenemos que pagarle C[a] ptas. Con esto, nos aseguramos que P[a, p] = 1, y P[a, j] = 0, para j p.
El objetivo consiste en gastarse la mínima cantidad de dinero, coaccionando a los votantes necesarios, para garantizar que un candidato p dado se llevará al menos el 70% de los votos (de acuerdo con las probabilidades esperadas). La solución estará compuesta por la lista de votantes a los cuales hay que coaccionar.
Aplicar el algoritmo diseñado al siguiente ejemplo: n = 2 candidatos, m = 7 votantes, p = 1. Porcentajes y costes de coacción:
Votantes
1 2 3 4 5 6 7
P[i, 1] 0.2 0.1 0.8 0.5 0.6 0.2 0
P[i, 2] 0.8 0.9 0.2 0.5 0.4 0.8 1
C[i] 4 3 2 5 3 3 5
Gracias
Valora esta pregunta
0