Group Abstract Group Abstract

Message Boards Message Boards

Mathematica algorithm to minimize summation

GROUPS:
Hi all!
I'm new in Mathematica's world, but i urgently need an algorithm:
data  = {1,3,5,6,7}     // a set of n data
[size=2]Sum[ Min[  | x_i   -  x_a | ,  | x_i  - x_b | ] , i from 1 to n ]     where x_i \in data [/size]
I have to find the (x_a,x_b) that minimize this Sum..

Can someone help me?
Thank you very much!!
POSTED BY: Mattew McHarroy
Answer
11 months ago
Are x_a and x_b also in the data set? If so, any reason not to do a brute-force search?

Is this a one-off problem, that is, only for this data set, or is it something you might need to solve for many such sets?

Is there a motivation for this problem? (Read: Is it something *other* than homework?)
POSTED BY: Daniel Lichtblau
Answer
11 months ago
thanks for response first!

yes x_a and x_b must be in data set and they can be the same..
i know that exists a function called 'findroot' that can do a brute-force search, but i'm not able to use this because i'm noob (I have just started learning it).
i need this sourcecode because we (exercise on algorithm book) have to find a algorithm (greedy technique i suppose), and i need to create more example..

have you understand what i mean?
hope you still can help me..
POSTED BY: Mattew McHarroy
Answer
11 months ago
 In[112]:= SeedRandom[11111111];
 data = RandomInteger[{0, 200}, 100]
 min = Infinity;
 n = Length[data];
 
 Timing[Do[
 tot = Total[
 Map[Min,
 Thread[{Abs[data - data[[j]]], Abs[data - data[[k]]]}]]];
If[tot < min,
Print[{data[[j]], data[[k]], tot}];
min = tot;
bestpair = data[[{j, k}]]];
, {j, n}, {k, j, n}];
bestpair]

Out[113]= {66, 74, 141, 104, 59, 59, 152, 149, 91, 183, 153, 188, 58, \
147, 145, 11, 129, 97, 36, 199, 57, 157, 181, 29, 34, 9, 104, 104, \
138, 157, 136, 73, 95, 200, 152, 172, 94, 57, 116, 184, 95, 87, 195, \
37, 32, 123, 154, 83, 50, 130, 143, 114, 52, 100, 143, 70, 33, 71, \
113, 65, 47, 27, 9, 159, 167, 1, 188, 188, 112, 109, 45, 48, 139, \
129, 150, 68, 193, 12, 124, 83, 49, 137, 39, 107, 68, 174, 55, 193, \
35, 60, 121, 33, 79, 18, 173, 196, 96, 97, 142, 104}

During evaluation of In[112]:= {66,66,5402}

During evaluation of In[112]:= {66,74,4882}

During evaluation of In[112]:= {66,141,2431}

During evaluation of In[112]:= {66,152,2378}

During evaluation of In[112]:= {141,59,2368}

During evaluation of In[112]:= {141,58,2364}

During evaluation of In[112]:= {141,57,2362}

During evaluation of In[112]:= {59,152,2347}

During evaluation of In[112]:= {59,149,2346}

During evaluation of In[112]:= {59,147,2344}

During evaluation of In[112]:= {149,58,2343}

During evaluation of In[112]:= {149,57,2342}

During evaluation of In[112]:= {58,147,2341}

During evaluation of In[112]:= {147,57,2340}

Out[116]= {0.294364, {147, 57}}
Could be done as above. (Would have preferred to say "Could be done as below", but once I had that formatted code block my cursor seemed unwilling to sneak above it to get into text mode. This is an unfortunate predicament for a cursor of but little understanding in the ways of the world.)
POSTED BY: Daniel Lichtblau
Answer
11 months ago
thank you very, very, very, very much!!!!
POSTED BY: Mattew McHarroy
Answer
11 months ago