Gale-Shapley実装多次元配列の問題

Question

私は乗客とタクシーに合わせてGale-Shapleyアルゴリズムを実装しています。今のところ、私は現在のマッチを拒否したり維持したりするための単一の設定構造（距離）を持っています。

すべては問題なく、解決策に近いと思います。しかし、嗜好データ（マルチディジット配列）にアクセスすると、何か奇妙なことが起きています。 2番目のインデックス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()への1回のコールしか処理できません。 List<Taxi>あなたが使用するようにクライアントを強制していないながら、型の安全性与える：あなたは「裸」ArrayList sがダブルノーノーですを使用した方法
• にすべてこれらのメンバ変数を移動しない限り、これはおそらく、後であなたをかみますArrayList
• 一つのことを行う小さく、自己完結型の、よく名前のメソッドにあなたのdoGaleShapley()メソッドをリファクタリングだけ
• 使用ユニットは、それぞれの可能な状況をシミュレートするをテストします。各テストには、希望する機能（例えばshouldReturnEmptyWaitingListIfNoPassengersProvided）の名​​前を付け、シナリオを設定し、機能を実行し、結果が期待どおりであることを確認するステートメントGiven - When - Thenで構成する必要があります。大きなメソッドを小さなメソッドにリファクタリングした場合は、テストの名前を付けてすべてをカバーしていることを確認するのが非常に簡単です。また、Coberturaのようなコードカバレッジツールを使用して、すべてのブランチにヒットしていることを確認することもできます。
• すべてこれを実行した後、あなたはまだそれを把握することはできません、する場合は、少なくともあなたはもう少しを提供する必要があるかもしれませんあなたは