Trying to figure out the name or algorythm for a system

Saigumi 101 Dec 06, 2006 at 16:48

Ok, I’m working on a bit of freeware and am trying to optimize a system of performing trades.

The basic system is that there are a lot group of nodes, say 20 to 200 of items for trade. Each node then has a weighted line to a bunch of other nodes. This basically represents the item for trade and then the order of desire of what that wants to be traded for. The trades also need to wrap themselves into the most inclusive loop or multiple loops.

I’ve been doing it sort of like A* at the moment. But it’s not really meeting the right need and seems wonky. Basically, I want to be able to select one of two outcomes. One being the highest weight with the most people and the other would include the most people while trying to stay with the highest weight.

Does anyone know the name of what this type of algorythm is? I’ve been trying to find some more guidance on making this, but am having the roughest time.

4 Replies

Please log in or register to post a reply.

Reedbeta 167 Dec 06, 2006 at 16:53

I’m not quite clear on what you want the algorithm to produce. You’ve got a graph with vertices representing commodities and edges representing exchange rates (prices)? Or are the edges something else? And you’re looking for what - a highest weight path? A heighest weight cycle?

Jare 101 Dec 16, 2006 at 01:12

Let me try another interpretation:

  • You have a number of nodes, for example planets.
  • Each node has a number of items.
  • Each node has some connections to other nodes.
  • A connection represents a specific possible trade that can be performed.
  • Each connection includes which items will be given and which items will be received, as well as an overall value of the connection.
  • For the sake of simplicity, I’ll assume that a node can’t have more than one connection with any other given node.
  • A node can’t perform all the possible trades it has with other nodes, because the resources being traded are limited.

You want to find, for a given node, some sets of trades that can be performed at once, with two criteria:
- Which set of trades represents the highest total value?
- Which set of trades includes the largest amount of different trades, and if there’s more than one set, which among them represents the highest total value?

Is that what you want? I can’t even remotely guess what “The trades also need to wrap themselves into the most inclusive loop or multiple loops” might mean.

If you can’t bruteforce this and can live with an approximation, “Greedy algorithms” are usually a good starting point for this kind of problems. Google or wikipedia the term.

dave_ 101 Dec 16, 2006 at 01:32

Genetic algorithms (GA) may also be appropriate, although GA rarely gives an optimal solution

Reedbeta 167 Dec 16, 2006 at 04:26

It sounds sort of like a max flow problem although I’m not quite sure how you would characterize it as such. If you could state it as a flow problem though there are plenty well known and pretty fast algorithms for solving it.