Ferangi Merchant Problem
Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
 |
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)
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();
}
}
|
Other Threads in the Computer Science Forum
- Previous Thread: Please Help me. Need Info And Answers
- Next Thread: Where can I find info about damn-low level architecture?
•
•
•
•
Views: 617 | Replies: 0 | Currently Viewing: 1 (0 members and 1 guests)
Linear Mode
