Gale-Shapley 구현 다차원 배열 문제

Question

나는 승객과 택시를 맞추기 위해 Gale-Shapley 알고리즘을 구현 중이다. 지금까지는 현재 일치를 거부하거나 유지하기 위해 단일 기본 설정 구조 (거리)가 있습니다.

모두 괜찮아 보이는군요. 나는 해결책에 가깝다고 생각합니다. 그러나 환경 설정 데이터 (multidim 배열)에 액세스 할 때 이상한 일이 발생합니다. 두 번째 인덱스 인 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

나는 나쁜 소식의 무기명으로 싫어하지만,이 복잡한 알고리즘이 특정 문제에 대한, 당신은 핀 포인트의 답변을 얻을 확률이 낮다. 난 당신이 버그 (들)을 찾을 수 있도록 제안 할 수 있습니다 무엇

:

• 당신은 서로 다른 크기의 특정 배열에 컬렉션을 많이 보유하고 있습니다.
• 알고리즘이 아닌 객체 지향 코드 (또는 의사 코드)로 표현 된 것처럼 보입니다. 가치가있을 수 있습니다. Taxi 및 Passenger을 나타내는 새로운 클래스를 설정하여 특정 배열의 특정 배열 위치로 색인을 작성하는 대신 모든 관련 세부 사항을 포함합니다.
• 메소드 매개 변수와 멤버 변수가 TaxiScheduler은 한 번에 doGaleShapley() 번으로 한 번만 전화를 처리 할 수 ​​있습니다. 이것은 아마도 나중에 당신이 "알몸"ArrayList의 사용 방법
• 에 모든 그 멤버 변수를 이동하지 않는 한 물지입니다 것입니다 이중되지 노 노 :를 사용하도록 클라이언트를 강요하지 않으면 서 List<Taxi> 당신에게 입력 안전을 제공합니다 ArrayList
• 은
• 사용 단위는 각각의 가능한 상황을 시뮬레이션 할 수을 테스트 한 일을 작은, 독립적 인, 잘이라는 방법으로 doGaleShapley() 방법을 리팩토링. 각 테스트는 원하는 기능 (예 : shouldReturnEmptyWaitingListIfNoPassengersProvided)을 따라 이름을 지정하고 시나리오를 설정하고 기능을 사용하며 결과가 예상대로인지 확인하는 Given - When - Then 문으로 구성되어야합니다. 큰 방법을 작은 방법으로 리팩터링 한 경우 테스트 이름을 지정하고 모든 것을 다루는 것이 매우 쉽습니다. 또한 Cobertura과 같은 코드 커버리지 도구를 사용하여 모든 지점이 적중되도록 할 수 있습니다.
• 이 모든 일을 한 후, 당신은 아직도 그것을 알아낼 수없는 경우에, 당신은 적어도 당신이