Ferangi Merchant Problem
 

Hi,

I wonder if anyone has seen a solution for a similar problem or can think of a better solution than this.

I initially tried to use Floyd-Warshall with a MAX function instead of MIN but the result was not as expected. If one could make that work it would be optimum.
I am not well versed in search theory so I resorted to the easier to understand breadth-first search as a starting point.


The problem ...
Find the best route from one city back to itself maximizing profit over time.
The route could be as short as one edge (there and back).
Edges are 2-way (i->j != j->i).

Key points in this method...
Breadth first search - node tree maintained so all paths are explored, not just current
visited check to prevent loops - per branch
visit map per city - branch dies if a better one has reached there first

Bad points...
near exhaustive search - many paths explored that dont need to be
Too much memory - max 6777 nodes open at one time for 168 cities durring testing (per root)
Too much time - 10 secs or so for 168 cities

Improvement - add metric, die once path is beyond hope of returning with better profit (max profit/time is known)

// Ferangi Merchant problem

//

// Find most profitable route vs time.

//

//



class node {

   node *pParent;

   float fTime;  // running totals

   float fProfit;

   float fPt;  // fProfit/fTime

   int iCity;

   int iChildren;



static float fPtMax = 0;



   node (node *parent, City *pCities,int i)

   {

     ...

   }

};





// Given an array[i,j] of Cities with time & profit from i to j

// all points are connected (though could add check for infinity)



void FindMaxRoute(CityArray &Cities, Route &out)

{

   queue qNext;

   int nCities = Cities.size();



   for(i=0;i<nCities;i++)

   {

      qNext.push(new node(0,Cities,i));

   }



   while(qNext)

   {

      node *pNode  = qNext.pop();



      if(pNode->HasReachedRoot())

      {

         if(pNode->isMax())

            pNode->updateMax(out);



         pNode->Destroy();

         continue;

      }



      for(i=0;i<nCities;i++)

      {

         if(!pNode->hasVisited(i) && !pNode->isSelf(i) && pNode->notBeat(i))

         {

            qNext.push(new node(pNode,Cities,i));

         }

      }



      if(!pNode->hasChild())

          pNode->Destroy();

   }

}