4 replies to this topic

[Saigumi]

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.

[Reedbeta]

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]

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_]

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

[Reedbeta]

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.