Matching algorithm

Question

Odd question here not really code but logic,hope its ok to post it here,here it is

I have a data structure that can be thought of as a graph. Each node can support many links but is limited to a value for each node. All links are bidirectional. and each link has a cost. the cost depends on euclidian difference between the nodes the minimum value of two parameters in each node. and a global modifier.

i wish to find the maximum cost for the graph.

wondering if there was a clever way to find such a matching, rather than going through in brute force ...which is ugly... and i'm not sure how i'd even do that without spending 7 million years running it.

To clarify:

Global variable = T
many nodes N each have E,X,Y,L
L is the max number of links each node can have.
cost of link A,B = Sqrt(  min([a].e | [b].e)  ) x 
     ( 1 + Sqrt( sqrt(sqr([a].x-[b].x)+sqr([a].y-[b].y)))/75 + Sqrt(t)/10 )


total cost =sum all links.....and we wish to maximize this.

average values for nodes is 40-50 can range to (20..600) average node linking factor is 3 range 0-10.

Answer 1

Is it possible that by greedily selecting the next most expensive option from any given start point (omitting jumps to visited nodes) and stopping once all nodes are visited? If you get to a dead end backtrack to the previous spot where you are not at a dead end and greedily select. It would require some work and probably something like a stack to keep your paths in. I think this would work quite effectively provided the costs are well ordered and non negative.

Answer 2

Use Genetic Algorithms. They are designed to solve the problem you state rapidly reducing time complexity. Check for AI library in your language of choice.

Answer 3

For the sake of completeness for anybody else that looks at this article, i would suggest revisiting your graph theory algorithms:

• Dijkstra
• Astar
• Greedy
• Depth / Breadth First
• Even dynamic programming (in some situations)
• ect. ect.

In there somewhere is the correct solution for your problem. I would suggest looking at Dijkstra first.

I hope this helps someone.

Answer 4

If I understand the problem correctly, there is likely no polynomial solution. Therefore I would implement the following algorithm:

1. Find some solution by beng greedy. To do that, you sort all edges by cost and then go through them starting with the highest, adding an edge to your graph while possible, and skipping when the node can't accept more edges.
2. Look at your edges and try to change them to archive higher cost by using a heuristics. The first that comes to my mind: you cycle through all 4-tuples of nodes (A,B,C,D) and if your current graph has edges AB, CD but AC, BD would be better, then you make the change.
3. Optionally the same thing with 6-tuples, or other genetic algorithms (they are called that way because they work by mutations).

Answer 5

This is equivalent to the traveling salesman problem (and is therefore NP-Complete) since if you could solve this problem efficiently, you could solve TSP simply by replacing each cost with its reciprocal.

This means you can't solve exactly. On the other hand, it means that you can do exactly as I said (replace each cost with its reciprocal) and then use any of the known TSP approximation methods on this problem.

Answer 6

Seems like a max flow problem to me.