Feb. 16th, 2004

maxwells_daemon: (Dr Manhatten)
(actually I have too, but the TeXbook isn't what I'm talking about). I thought maybe this was a problem that those of you who read computer science might have an idea about. I'm afraid the phyisicst's approach ("any combinatoric problem can be solved with enough nested DO loops") has led me to geometric overload.

Here's the problem... I even drew a diagram

initial diagram

Given a network like the one above (where only the topology matters), I need an algorithm to find the minimum set of links that joins the 3 nodes (marked with blobs).

result diagram

To join the 3 nodes, one needs to use the 6 links marked in red, and include 4 additional nodes.

In general, I have a list of L links each of which connects two vertices. N of the V vertices need to be linked together, either directly or indirectly. (In my example, L=11, N=3, V=12.) How can I find which links and which additional nodes I need to do this? At the moment my problem has just one solution, but I may have to add additional connections which include a loop. It would be nice if the algorithm could pick the solution with fewest links. I guess this is related to the travelling salesman problem, though the problem is one of selection of cities to visit rather than order.

Don't worry, I'm not asking for the code to do this, just a hint about an algorithm. My current effort, trys including all combinations of links until it finds the smallest set that includes the desired nodes. That works fine, but requires L! iterations, and it's getting very slow :-(

What I'm actually trying to do is find out programatically which tables and joins are required for an SQL query that includes a subset of all the tables in the database.

Thanks!

PS. and if anyone has an analytic solution to the QCD Lagrangian, that too would be welcome :-)

Profile

maxwells_daemon: (Default)
maxwells_daemon

April 2013

S M T W T F S
 1 23456
78910111213
14151617181920
21222324252627
282930    

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 3rd, 2025 04:28 am
Powered by Dreamwidth Studios