Looping problem

[Alex Tweedly]

Glen Bojsza wrote:

>I'm stuck...and getting burnt out so I thought I would see if someone
>has a fresh idea for me to try.
>
>The scope is to have a number of locations and the minimum path
>connecting the locations.
>
>I have two fields.
>
>Field Name contains a list of single unique site names. (for example 20 names)
>
>Field Link contains a list of three items. The first two items are
>single names from the field Name and the third item is a weighted
>numeric value. This field is the total possible combinations of the
>names and their associated values for lowest to highest. So my
>combinations would total 20*(20-1)/2 =190
>
>I am trying to create a resulting field that would have a list that
>would include a least one occurance of each name. Therefore 20 -1 = 19
>links (preferably from the lowest value upwards.
>  
>
I'm not sure if I have understood the problem exactly - I can read it 
two different ways.  Taking a small example (4 names instead of 20), I 
think you have a

Field Name
------------
A
B
C
D

Field Link
----------
A B 12
A C 17
A D 22
B C 8
B D 12
C D 6

Are you looking for

(a) result field consisting of entries from the link field, such that 
each name occurs at least once 
   e.g     A B 12, C D 6
(b) result field ... such that each name occurs once in each column
   e.g. A C 17, B C 8, C D 6   (with an implicit final D A ... omitted)
(c) something else ??

I think it's probably (b) - in which case you've described an instance 
of the well-known "Travelling Salesman" problem).

It's well-known because it's an instance of an NP Complete problem - 
i.e. HARD. There is no known solution for finding the optimal solution 
for large values of N - the number of possible combinations to be 
examined grows surprisingly quickly.

A Google for Travelling Salesman Problem will bring up lots of 
suggestions ....

Sorry, I don't have any actual useful suggestions for this one ....



-- 
Alex Tweedly       http://www.tweedly.net



-- 
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.323 / Virus Database: 267.7.8/22 - Release Date: 17/06/2005