Я реализую алгоритм Гейла-Шепли, чтобы соответствовать пассажирам и такси. Пока у меня есть единственная структура предпочтений (расстояние), чтобы отклонить или сохранить текущее соответствие.
Все, кажется, хорошо, и я думаю, что я близок к решению. Однако при доступе к данным о предпочтениях (многомерный массив) происходит нечто странное. Второй индекс, 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;
}
}
}