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
Please log in or register to post a reply.
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
Let me try another interpretation:
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”
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.
Genetic algorithms (GA) may also be appropriate, although GA rarely
gives an optimal solution
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.