Flying Arrow
United States
Pennsylvania
flag msg tools
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Without having played with any sample outputs, that's the metric I would use - ignoring total number of trades and maximizing trade quality using the above formula (where number of trades is implicitly taken into account). Let me know if that produces reasonable results.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mikko Saari
Finland
Tampere
flag msg tools
http://www.lautapeliopas.fi/ - the best Finnish board game resource!
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Yes, that works well. The results were around 50-70 trades. That's quite reasonable. That kind of scoring will be available in the second release of TradeResolver, I'll make it an option.

Edit: Now that I've actually squashed all the bugs in the quality-counting algorithm and changed it to count in the untraded items, it looks like the results are pretty much the same whether you're looking for most trades or most quality. Which is interesting.

The quality tends to be around 0.5 on a list where most items are traded - is that enough for those who are looking for high quality trades, I don't know, but it does mean many people are getting their first want.

Of course, if a list is harder, the quality will be lower. On those lists, the maximize quality algorithm will work hard to increase the number of trades, because that's the easiest way to get better quality. With an easier list where you can get more trades, there's more alternatives to get a better quality.

So, what I'm saying here is that TradeResolver can produce satisfying results, if the quality you want is not "as many 1st want trades as possible, screw the rest" but "as good trades for everyone as possible".
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Patrick Barringer
United States
Rushford
New York
flag msg tools
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
I know this is an old thread and thus I might not get any results, but could someone either fill me in on how to find and enumerate all of the cycles in a digraph (without worrying if they are disjoint) or link me to some page that can?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christian Fechner
Germany
Gladbeck
Ruhrgebiet
flag msg tools
mbmbmbmbmb
Re:Math Trade Theory & Algorithms (Warning: Can Hurt Brain)
Hi,

I was wondering about the same thing yesterday, when I read the thread the first time. I thought, first find all circles, and then try an approximation of the perfect cover which satisfies the disjoint condition.

But then I noticed the following:
A complete graph (not digraph) with n vertices has (n-1)!/2 cycles (if I'm right). So you come to a cover problem (which is also NP-complete) with exponential size of the original problem. This won't help anything.

To count all cycles, I see no other way, than perform a complete DFS (or BFS) on the graph and count every cycle one by one. Simply color every vertex you visited and increase the cycle counter every time you hit a colored vertex.

Christian
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
I have done this, but with my own algorithm and therefor may not be the most efficient.

I preformed a DFS on the list and recorded all cycles regardless of where the fell in the tree.

My program was writting in VB6 so I made use of the TreeView Control. I picked a starting game and then added its first want to the tree with a node key of the edge (ie "1->2"). I continued this for each game recursively until I hit a "key already exsists" error. This meant that I reached a vertex & edge that is already on the tree. I moved up the tree to find the starting vertex and recorded that chain. I moved to the next game in the previous vertexes want list and repeated. I added a check to make sure that each game in the chain was unique.

The problems I ran into were

1) the sheer number of chains that are found is huge and storage of the data becomes a major issue.
2) once I had an approximation of all of the chains, putting them together was extremely slow even slower.
3) there was diminishing returns (in otherwords with 50 vertexes the program might run in 20 milliseconds, 100 vertexes the program might run in 3 minutes, 200 vertexes ... well it never finished because I ran out of memory)

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
chrikru wrote:

To count all cycles, I see no other way, than perform a complete DFS (or BFS) on the graph and count every cycle one by one. Simply color every vertex you visited and increase the cycle counter every time you hit a colored vertex.
FWIW, BFS will find short chains quickly. DFS will find long chains quickly. Neither one has proven to be the better solution.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Patticus wrote:
but could someone either fill me in on how to find and enumerate all of the cycles in a digraph
A simple Depth First Search (DFS) for every offer->want pair will work. You just need to cache each complete cycle somewhere as you come across it.

http://en.wikipedia.org/wiki/Depth-first_search



 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
Never mind BFS or DFS... Chris O. has solved the problem! See

Math trades are SOLVED!
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Prev «  1 , 2 , 3  |