# Voracious Algorithms

4

I am a student of programming and I would like to know if any of them can give me an idea of how to perform the following problem using voracious algorithms.

Find a good solution to the following problem using a voracious algorithm. Explain the operation of the algorithm: which is the set of candidates, the selection function, the function to add an element to the solution, the criterion of completion, the cost criterion, etc.

In a vote there are n candidates and m voters. The probability that a voter i votes the candidate j is known a priori, and is given by P [i, j] . Any voter to can be coerced into voting for the candidate we want, for example p , for which we have to pay C [a] ptas With this, we make sure that P [a, p] = 1 , and P [a, j] = 0 , for j ≠ p .

The objective is to spend the minimum amount of money, coercing the necessary voters, to ensure that a given p candidate will take at least 70% of the votes (according to the odds expected). The solution will consist of the list of voters to be coerced.

Apply the algorithm designed to the following example: n = 2 candidates, m = 7 voters, p = 1. Percentages and costs of coercion:

```                          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```

asked by Charlie 25.04.2016 в 03:25
source

3

The voracious algorithms can be solved with or without ordering, it depends on the strategy that is decided to use, I have solved it doing previous ordering of the set of candidates . Let's go with the code:

Class that represents the voting entity, has the probability of voting, a cost, an applied cost, that is, how much money we are supposed to get a 100% probability to obtain the vote and a voter's identifier.

``````public class Votante {

private final String idVotante;
private final int costo;

public Votante(String idVotante, float probabilidadCandidato, int costo) {
this.idVotante = idVotante;
this.costo = costo;
}

public String getIdCandidato() {
return idVotante;
}

}

public int getCosto() {
return costo;
}

}

@Override
public String toString() {
StringBuffer str=new StringBuffer("Votante: ").append(idVotante)
.append(" - Costo de corrupcion: ").append(costo)
return str.toString();
}

}
``````

On the other hand we are going to implement a Comparator to order our candidate set so that the probability of voting is greater or lesser, if the same probability is given then order for the cost from least to greatest:

``````public class ComparadorDeVotantes implements Comparator<Votante> {

@Override
public int compare(Votante v1, Votante v2) {
return v1.getCosto() < v2.getCosto() ? -1 : v1.getCosto() == v2.getCosto() ? 0: -1 ;
}
}

}
``````

I define a trivial interface to represent the functionality of the algorithm, receive a set cadidates and return a set solution :

``````public interface AlgoritmoVoraz<T> {

public List<T> procesa(List<T> candidatos);

}
``````

Now we implement a class to solve this problem

``````public class AlgoritmoCostoCorrupcion implements AlgoritmoVoraz<Votante> {

private String candidatoElectoral;

public AlgoritmoCostoCorrupcion(String candidatoElectoral) {
this.candidatoElectoral=candidatoElectoral;
}

@Override
//ordenamos el conjunto candidatos
//creamos el conjunto solucion, inicialmente vacio
List<Votante> solucion = new ArrayList<Votante>();
//guardamos el numero de elementos del conjunto candidato para poder
//calcular porcentaje de procesamiento posteriormente
//sumatorio para calcular el costo de corrupcion de los votantes
float costoCorrupcion = 0;

//iteramos mientras no tengamos una solucion valida
while (!esSolucion(solucion.size(), elementosTotales, 70)) {
//como el conjunto candidato esta ordenado la seleccion es
//tan simple como obtener siempre el primero
//sumamos
//eliminamos del conjunto candidato
}
//conjunto solucion
return solucion;
}

//obtiene el primer elemento del conjunto candidato
}

//es solucion cuando se han procesado el 70% o mas de los elementos
//del conjunto candidato, no es necesario mas al estar ordenados
private boolean esSolucion(int elementosProcesados, int elementosMaximos, int porcentajeMinimo) {
return (elementosProcesados * 100) / elementosMaximos > porcentajeMinimo;
}

public void print(List<Votante> solucion) {
float costoCorrupcion=0;
System.out.println("Datos del conjunto solucion:");
for (Votante elementoDeSolucion : solucion) {
System.out.println("\t"+elementoDeSolucion.toString());
}
System.out.println("El coste de corrupcion minimo es de : " + costoCorrupcion + " para el candidato: "
+ candidatoElectoral + "con al menos el 70% de los votantes");

}

}
``````

Test to check:

``````public class AlgoritmoCostoCorrupcionTest {

@Test
public void testProcesa() {

AlgoritmoCostoCorrupcion ccc=new AlgoritmoCostoCorrupcion("Candidato A");
ccc.print(solucion);

assertThat(solucion.size(),is(equalTo(5)));
}

}
``````

I hope it will be helpful, without prior planning the implementation is more complicated for me, the same thing you do not think so.

0

The voracious algorithms decide the most beneficial option in each state of the problem. In this case I think the idea is to choose the voter first with the lowest cost that benefits the candidate's vote more 1. Then the next one in cost / benefit and so on until reaching the goal of ensuring 70%. I hope it helps you.