Реализация многоуровневого массива Gale-Shapley

Question

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

Все кажется прекрасным, и я думаю, что я близок к решению. Однако при доступе к данным предпочтений (многодисковый массив) происходит нечто странное. Второй индекс, kTaxiIndex, имеет правильное значение, но при индексировании я получаю данные из другого столбца в одной строке! Я уже перемещал переменные. Кто-нибудь знает, что здесь происходит?

Любая помощь приветствуется.

class TaxiScheduler { 

    ArrayList acceptorTaxis; 
    ArrayList proposorPassengers; 
    Integer [] waitingList; //index represent taxis, contents passengers 
    ArrayList<Integer> rejectionPool; //where unmatched passengers are kept 
    Integer [] rejectionCounter; //determines the KBest option for that passenger 
    Double [][] distancePreferences;  //unique preference structure 

    public TaxiScheduler(){ 

    } 

    public Integer[] doGaleShapley(ArrayList taxis, ArrayList passengers){ 

     acceptorTaxis = taxis; 
     proposorPassengers = passengers; 
     waitingList = new Integer [acceptorTaxis.size()]; //keeps best current match 
     rejectionPool = new ArrayList<Integer>(); //rejected passengers' indexes 
     rejectionCounter = new Integer [proposorPassengers.size()]; //keeps track of rejections per passenger 
     distancePreferences = new Double[proposorPassengers.size()][acceptorTaxis.size()]; 

     initPoolandCounter(); //No passenger has been rejected, but all are included in the rejecion (not matched) pool 
     calculatePreferences(); // distances between taxis and passengers 

     /* 
     * Every rejected passenger turns to its next (1st, 2nd, 3rd,...) closest taxi 
     * Every taxi with more than one proposal keeps the closest passenger in the waitingList and 
     * rejects other proposing passengers 
     */ 
     ListIterator<Integer> itrRejected = this.rejectionPool.listIterator(); 
     while(!this.rejectionPool.isEmpty()) 
     { 
      if(!itrRejected.hasNext()) //end of list 
       itrRejected = this.rejectionPool.listIterator(); 

      int newPassengerIndex = (Integer) itrRejected.next().intValue(); 
      int kTaxiIndex = getKBestOption(this.rejectionCounter[newPassengerIndex], newPassengerIndex); //Get K-best based on number of rejections 

      itrRejected.remove(); //remove current passenger from rejected list 

      if(waitingList[kTaxiIndex]== null){ //taxi is vacant! 
       waitingList[kTaxiIndex] = newPassengerIndex; //match w/ closest taxi 
      }else{ //compare, keep the best and pool rejected, update rejection counter 
       int currentPassengerIndex = waitingList[kTaxiIndex].intValue(); 

       Double d1 = distancePreferences[currentPassengerIndex][kTaxiIndex]; 
       Double d2 = distancePreferences[newPassengerIndex][kTaxiIndex]; 

       if(d1.compareTo(d2) > 0){ //new passenger is closer i.e. d1 > d2 
        addToPool(currentPassengerIndex, itrRejected); //add current passenger to pool and update rejection counter 
        waitingList[kTaxiIndex] = new Integer(newPassengerIndex); //set new passenger as new match 

       }else{ //current passenger is preferred 
        addToPool(newPassengerIndex, itrRejected); 
       } 
      } 
     } 
     Logger.getLogger("data").log(Level.INFO, "rejectedList = "+printPool(), ""); 
     return waitingList; 
    } 

    private void initPoolandCounter() { 
     rejectionCounter = new Integer[this.proposorPassengers.size()]; 

     for(int i = 0;i< rejectionCounter.length;i++) 
     { 
      rejectionCounter[i]=0; 
      this.rejectionPool.add(i); 
     } 
    } 

    //Works with indexes, look up on preference structure 
    private Double getDistance(Integer passengerIndex, Integer taxiIndex) { 
     return distancePreferences[passengerIndex.intValue()][taxiIndex.intValue()]; 
    } 

    /** 
    *Fills the preferences structure with distances between taxis and passengers 
    * 
    */ 

    private void calculatePreferences() { 
     double distance = -1; 
     StringBuffer buff = new StringBuffer(); 

     try { 
      for (int iPass = 0; iPass < this.proposorPassengers.size(); iPass++){ 
       PassengerMovement passMov = (PassengerMovement) this.proposorPassengers.get(iPass); 
       GeoPointExt passGeo = new GeoPointExt(passMov.getLatitude(),passMov.getLongitude()); 
       buff.append(iPass+":\t"); 
       for (int iTaxi = 0; iTaxi < this.acceptorTaxis.size(); iTaxi++){ 
        TaxiMovement taxiMov = (TaxiMovement) this.acceptorTaxis.get(iTaxi); 
        GeoPointExt taxiGeo = new GeoPointExt(taxiMov.getLatitude(), taxiMov.getLongitude()); 

        distance = Haversine.getDistance(taxiGeo, passGeo, DistanceUnit.Kilometers); 
        this.distancePreferences[iPass][iTaxi] = new Double(distance); 
        //TODO: Inverted distances!!! 
        buff.append(distancePreferences[iPass][iTaxi].toString().substring(0, 5) +"\t"); 

        //Logger.getLogger(TaxiScheduler.class.getName()).log(Level.SEVERE, "PREFS = ["+passMov.getPassengerMovementPK().getMobileNo()+"]["+taxiMov.getTaxiMovementPK().getPlateNo()+"]"); 
        //Logger.getLogger(TaxiScheduler.class.getName()).log(Level.SEVERE, "PREFS = ["+iPass+"]["+iTaxi+"]("+this.distancePreferences[iPass][iTaxi].toString().substring(0, 4)); 
        } 
       buff.append("\n"); 
      } 
     }catch(NullPointerException ex) 
     { 
      Logger.getLogger(TaxiScheduler.class.getName()).log(Level.SEVERE, "distance = "+distance, ex); 
     } 

     Logger.getLogger(TaxiScheduler.class.getName()).log(Level.SEVERE, "TOTAL PREF = \n"+buff.toString());   

    } 

    /* 
    * Returns index of the taxi that is k-best option for that passenger 
    * 
    * @param k The k-best (closest) taxi to be retrieved, 0 being the closest 
    * @param passIndex The passenger index 
    * @return K-closest taxi index for this passenger 
    */ 
    private int getKBestOption(int k, int passIndex){ 
     Double [] passPreferences = this.distancePreferences[passIndex]; //Preferences for the taxi in that index 
     List<Double> pPreferences = Arrays.asList(passPreferences); 
     ArrayList originalOrder = new ArrayList(pPreferences); 

     Collections.sort(pPreferences); //sort taxi distances 
     Double kDistance = (Double) pPreferences.get(k); //get k-smallest distance 
     int ind = originalOrder.indexOf(kDistance); //find index of this value in the original array, even if repeated still KBest 
     return ind; 
    } 

    private String printPool() { 
     StringBuffer buff = new StringBuffer(); 
     int c = 0; 

     for(Integer x:this.rejectionPool) 
     { 
      buff.append(x+"["+rejectionCounter[x]+"] "); 
      c++; 
     } 
     return buff.toString(); 
    } 

    /* 
    * Add this element to rejection pool and updates its rejection counter 
    * 
    * @param passengerToPool Passenger index to add to the pool 
    * @param itrRejected iterator used in the rejectionPool 
    */ 
    private void addToPool(int passengerToPool, ListIterator<Integer> itrRejected) { 
     //check whether this passenger is already in the pool 
     int rIndex = rejectionPool.indexOf(passengerToPool); 

     if(rIndex == -1){ //not in the pool 
      this.rejectionCounter[passengerToPool]+=1; 
      if(this.rejectionCounter[passengerToPool] < this.acceptorTaxis.size()) //if has not been rejected by all taxis 
       itrRejected.add(passengerToPool); 

     }else{ //was already pooled, leave it there and increase counter 
      this.rejectionCounter[rIndex]+=1; 
     } 
    } 
} 

Answer 1

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

Что я могу предложить, чтобы помочь вам найти ошибку (ы):

• У вас есть много коллекций, в частности массивов различных размеров. Меня не удивляет, что вы получаете какие-то «из-за ударов» позиций, учитывая это
• Похоже, вы взяли алгоритм, выраженный на языке, отличном от OO (или, возможно, псевдокоде) - это может стоить создание нового класса для представления Taxi и Passenger, содержащего все соответствующие детали внутри, вместо того, чтобы пытаться индексировать конкретную позицию массива определенного массива
• У вас есть смесь параметров метода и переменных-членов, что означает TaxiScheduler может фактически иметь дело только с одним звонком до doGaleShapley() за раз. Это, вероятно, укусить вас позже, если вы не двигаться все эти переменные члены в метод
• Использование «голых» ArrayList сек это не двойной нет-нет: List<Taxi> дает безопасность типов, а не заставляя клиента использовать ArrayList
• реорганизовать метод doGaleShapley() на более мелкие, самодостаточных, хорошо названных методов, сделать одну вещь только
• Использование модульных тестов для моделирования каждой возможной ситуации. Каждый тест должен быть назван после желаемой функциональности (например, shouldReturnEmptyWaitingListIfNoPassengersProvided) и состоит из операторов Given - When - Then, которые настраивают сценарий, выполняют вашу функцию и проверяют, что результаты ожидаются. Если вы переработали свой большой метод на более мелкие, будет очень легко назвать ваши тесты и убедиться, что вы все покрываете. Вы также можете использовать инструмент покрытия кода, например Cobertura, чтобы все ваши ветви были удалены.
• Если, после того, как делать все это, вы все еще не можете понять это, вы должны, по крайней мере, иметь меньший фрагмент кода, который вы можете разместить здесь :-)