Trying to figure out the name or algorythm for a system
Posted 06 December 2006 - 04:48 PM
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.
Posted 06 December 2006 - 04:53 PM
Posted 16 December 2006 - 01:12 AM
- 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.
Posted 16 December 2006 - 01:32 AM
Posted 16 December 2006 - 04:26 AM
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users