Прожорливые алгоритмы

Я - студент программирования и я хотел бы знать, может ли какой-либо давать мне идею как реализовывать следующую проблему используя прожорливые алгоритмы.

Находить хорошее решение для следующей проблемы используя прожорливый алгоритм. Объяснять функционирование алгоритма: какова набор кандидатов, функция выбора, функция, чтобы добавлять элемент к решению, критерию окончания, критерию цены, и т.д.

В голосовании существуют n кандидаты и м избиратели. Вероятность того, что избиратель i проголосует за кандидата j, мы знаем априори, и он приходит данная из-за P [i, j]. Любой избиратель в puede быть принужденным для того, чтобы он проголосовал за кандидата, которого давайте любить, например p, для чего мы должны платить ему C [в] ptas. С этим, мы убеждаемся, что P [в, p] = 1, и P [в, j] = 0, для j ≠ p.

Цель состоит, в минимальное количество денег становится измученным, принуждая необходимых избирателей, чтобы гарантировать, что кандидат p данный унесет по крайней мере 70 % обетов (в соответствии с ожидаемой вероятностью). Решение будет составлено списком избирателей, которых нужно принуждать.

Применять алгоритм, разработанный в следующий пример: n = 2 кандидата, м = 7 избирателей, p = 1. Процентное содержание и цены принуждения:

                          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
4
задан 25.04.2016, 06:14
2 ответа

Прожорливые алгоритмы могут быть решенными с ordenaciГіn или без нее, завись от стратегии, которая решает использовать, я это решил реализовывая ordenaciГіn предварительная соединяю кандидаты . Мы идем с cГіdigo:

у Класса, что представляет организацию избиратель, есть вероятность обета, цена, прикладная цена, а именно все деньги предполагают нам получать вероятность 100 %, чтобы получать обет и идентификатора избирателя.

public class Votante {

  private final String idVotante;
  private final float probabilidadVoto;
  private final int costo;
  private final float costoAplicado;


  public Votante(String idVotante, float probabilidadCandidato, int costo) {
    this.idVotante = idVotante;
    this.probabilidadVoto=probabilidadCandidato;
    this.costo = costo;
    this.costoAplicado = (1 - probabilidadVoto) * costo;
  }

  public String getIdCandidato() {
    return idVotante;
  }

  public float getProbabilidadVoto() {
    return probabilidadVoto;
  }

  public int getCosto() {
    return costo;
  }

  public float getCostoAplicado() {
    return this.costoAplicado;
  }

  @Override
  public String toString() {
    StringBuffer str=new StringBuffer("Votante: ").append(idVotante)
            .append(" - Probabilidad de voto: ").append(probabilidadVoto)
            .append(" - Costo de corrupcion: ").append(costo)
            .append(" - Costo en base a probabilidad: ").append(costoAplicado);
    return str.toString();
  }

}

С другой стороны мы будем осуществлять Comparator для odenar наши соединенные кандидаты таким образом что вероятность обета - превосходящего несовершеннолетнего, если встречается та же вероятность, тогда упорядочи из-за цены несовершеннолетнего в больший:

public class ComparadorDeVotantes implements Comparator<Votante> {

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

}

Я Определяю тривиальный интерфейс, чтобы представлять функциональность алгоритма, получает набор cadidatos и возвращает набор решение :

public interface AlgoritmoVoraz<T> {

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

}

Сейчас мы осуществляем класс, чтобы решать эту проблему

public class AlgoritmoCostoCorrupcion implements AlgoritmoVoraz<Votante> {

  private String candidatoElectoral;

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

  @Override
  public List<Votante> procesa(List<Votante> listaDeVotantes) {
    //ordenamos el conjunto candidatos
    Collections.sort(listaDeVotantes, new ComparadorDeVotantes());
    //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
    int elementosTotales = listaDeVotantes.size();
    //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
        Votante candidato = seleccionarCandidato(listaDeVotantes);
        //sumamos
        costoCorrupcion = costoCorrupcion + candidato.getCostoAplicado();
        //añadimos al conjunto solucion
        solucion.add(candidato);
        //eliminamos del conjunto candidato
        listaDeVotantes.remove(candidato);
    }
    //conjunto solucion
    return solucion;
  }

  //obtiene el primer elemento del conjunto candidato
  private Votante seleccionarCandidato(List<Votante> listaDeVotantes) {
    return listaDeVotantes.get(0);
  }

  //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;
  }

//muestra resultado
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());
        costoCorrupcion = costoCorrupcion + elementoDeSolucion.getCostoAplicado();
    }
    System.out.println("El coste de corrupcion minimo es de : " + costoCorrupcion + " para el candidato: " 
            + candidatoElectoral + "con al menos el 70% de los votantes");

  }

}

Тест для Ваш comprobaciГіn:

public class AlgoritmoCostoCorrupcionTest {

  @Test
  public void testProcesa() {
    List<Votante> listaDeVotantes=new ArrayList<Votante>();
    listaDeVotantes.add(new Votante("Votante1",0.2f,4));
    listaDeVotantes.add(new Votante("Votante2",0.1f,3));
    listaDeVotantes.add(new Votante("Votante3",0.8f,2));
    listaDeVotantes.add(new Votante("Votante4",0.5f,5));
    listaDeVotantes.add(new Votante("Votante5",0.6f,3));
    listaDeVotantes.add(new Votante("Votante6",0.2f,3));
    listaDeVotantes.add(new Votante("Votante7",0f,5));

    AlgoritmoCostoCorrupcion ccc=new AlgoritmoCostoCorrupcion("Candidato A");
    List<Votante>solucion=ccc.procesa(listaDeVotantes);
    ccc.print(solucion);

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

}

Надеялся, что он ты помогает, без ordenaciГіn предварительная она implementaciГіn для меня она сложнее, то же самое тебе это не кажется.

3
ответ дан 24.11.2019, 14:32

Прожорливые алгоритмы решают самый полезный выбор в каждом состоянии проблемы. В этом случае я думаю, что состоит в том, чтобы выбирать идею сначала избиратель с самой меньшей ценой, который благодетельствует больше в голосование кандидата 1. Потом тот, который следует за ним в цене / благодеянии, и я схватил последовательно до того, чтобы достигать цели гарантировать 70 %. Я надеюсь, что он помогает тебе.

0
ответ дан 24.11.2019, 14:32