|
I wonder what optimization algorithm should be used for such a problem:
x: independent variable
y: dependent variable
For y = f(x), find all x such that:
sum of y is > p where p is a positive integer
sum of y is the minimum of all sums that are greater than p
|
|
|
|
|
There is important information missing:
1. what types are x and y?
2. what are valid ranges for x and y?
3. what do you mean by "sum of y"? For any given x, there is only one y - what is it that you sum up?
4. what are the properties of f()? E. g. is it monotonous, continuous, continuously differentiable? Can you even give an exact definition? Is it even a function? You do not state as much!
|
|
|
|
|
Myself I suspect that the most important piece of information missing is which school class this is for.
|
|
|
|
|
@jschelll - sorry to disappoint. Its been many years since I left college which is probably why I'm finding it hard to write a generalized statement for the problem I'm facing!!!
|
|
|
|
|
Let me clarify my question:
x: is a discrete random variable
y: is a discrete dependent variable that follows count data model
y is a function of x.
Both x, y are both finite positive integers
Question is:
For a given p: find all x (i.e., x1, x2, ... , xi) such that
y1 + y2 + ... + yi > p
and
(y1 + y2 + ... + yi) is the smallest sum of all combinations of y's > p
|
|
|
|
|
This looks a lot like a variation on the knapsack problem[^]
That could suggest a strategy.
|
|
|
|
|
Let me clarify my response: Your question doesn't make sense, not in the original posting nor in this 'clarification: you are seeking the combinatorial optimum soultion in an infinite search space, and that is impossible to solve. You must restrict that search space to a finite set of (x,y) pairs, before the question even starts to make sense!
|
|
|
|
|
I have been interested in Decision Tables [^] a long time, and lately I found myself wanting to do some exploratory programming to create a Decision Table UI, and parse it, and crank out a bunch of complex logical assertions in a form that would be useful for creating a set of "business rules," state-machines, language-parsers, etc.
I suspect some of you "old-timers" here have experience with decision table software, and theory.
The most interesting aspect of decision-table theory, to me, is the analysis of a set of complex logical statements to see if there are ambiguities, contradictions, or "incompleteness."
I don't quite know how to conceptualize the dynamics of the process of logical verification; I'm posting this message to just ask for some pointers to any resources you are aware of for theory or algorithms useful for this.
I'm not looking to find code, at this point. I have been searching on the web, and have been examining the various commercial software packages for Windows for decision tables (pricey !). Nothing yet has really given me any ideas on the theory/algorithms for logical "provability."
thanks, Bill
“But I don't want to go among mad people,” Alice remarked.
“Oh, you can't help that,” said the Cat: “we're all mad here. I'm mad. You're mad.”
“How do you know I'm mad?” said Alice.
“You must be," said the Cat, or you wouldn't have come here.” Lewis Carroll
|
|
|
|
|
I have no idea (always a good start for an answer), but you may be interested in BDDs[^] as well (because they are often a good way to store and manipulate boolean functions).
|
|
|
|
|
Many thanks, Harold, that's an excellent resource.
After posting this message, memory came back to me of studying Truth Tables, around 1982, when I was bored out of my mind in the first year of a doctoral program in social science.
Another issue that interests me is a question of heuristic ordering of logical comparisons in order to optimize computation ... given you have a compiler, like C#, that suspends evaluation "smartly."
So, the question of "who's on first ?" is very interesting, in that context: I use the term "heuristic" since I think that the information a programmer has is, often, which one, or a few, tests are known to be very frequent, and which other tests are estimated to be less frequent.
For very complex sets of logical conditions, given frequency information on each possible condition's occurrence, it's interesting to consider what might be involved in producing code that's optimal: and what happens if, over time, those probabilities fluctuate in regular "clusters" (modes). So that, in State #1 you want one chunk of code, and in other States #n you want other chunks.
Do I make sense ? Wait, no, please ... forget I asked that 
“But I don't want to go among mad people,” Alice remarked.
“Oh, you can't help that,” said the Cat: “we're all mad here. I'm mad. You're mad.”
“How do you know I'm mad?” said Alice.
“You must be," said the Cat, or you wouldn't have come here.” Lewis Carroll
|
|
|
|
|
What sort of aspects do you want to consider?
For example, if you assume uniform cost of all tests/branches, then the obvious order is in decreasing order of probability.
If the cost is slightly more realistic and based on the fraction of mispredictions (assuming the branch is random but biased), then .. I'm not sure. The total cost (ie average time spent in the tests) would be approximated as F(i) = C(i) + (1-P(i)) * F(i + 1) and F(n) = 0 where P(i) is the probability of the i-th branch being taken and C(i) = 0.55 e(-8 (P(i)-0.5)2) - 0.04 (that's not the best approximation of the cost of a branch ever, but it's the best I could come up with in a couple of minutes).
|
|
|
|
|
Recently while looking for Braille characters as images, I discovered a rather strange thing - there were many, many websites that taught Braille, but I could not find any that had all of its characters as separate image files, let alone in one place.
In order to fill this gap, I went ahead and created an open source project on SourceForge BrailleAlphabetGenerator hoping it would be useful for someone. The intention was to keep the image parameters customizable.
I am seeking feedback from all of you on how to improve the project - code, visual, or anything else (except perhaps, 'Why not use Unicode?').
Thanks much in advance for your feedback.
|
|
|
|
|
|
Thanks for showing me the right place. Moved it there.
|
|
|
|
|
Hi,
I am working on this project that requires a base protocol to be developed through (sound)whistle patterns. This project is meant to have an alternative for large area communication not using wifi or Bluetooth or any such technology that requires some additional circuitry overheads, we just need sound base transmission and receiver for sound so we decided to use whistle patterns as protocol that will use different wavelengths/patterns.
My concern is patterns may come randomly and I want to search it within database for right match of pattern with efficiency, since it is a sound pattern how do I store it and what is the right approach for searching through it. Also if any garbage then how to identify it well in advance before search even.
Patterns are nothing but commands, information and even at times signals(Normal functioning, some Event occurred, Abnormal condition)
Algorithm that I write should generate whistle with some starting point that marks it as valid may be for receiver to know that next is actual data. Whistle sent may have information about device from which it is coming and other information every time it sends with end of message to it.
I am sorry if this is not very clear but this is what I have.
Thanks!
Rahul Joshi
|
|
|
|
|
The MP3 algorithm will reduce the amount of sound data you need to process, by eliminating sounds the human ear can't hear. So although it's a lossy compression method, it accurately reproduces the original signal.
|
|
|
|
|
Thank you for your help, I will research more on this.
We actually want to study send/receive of both audible and non-audible (just to see also possible effect of it on birds/animals) if we want to use it should not cause any harm to environment.
Anyways thanks for your comment.
|
|
|
|
|
I need to find the shortest path between two points in a maze using recursion. the maze is represented by a two-dimensional array of integers. You can walk through cells in the array if their values are different than -1. In addition, if there are some paths with the same length, the algorithm should find the path with the highest values in the array.
I thought about an algorithm that checks all the possible paths, but I need something more efficient.
thank you!
|
|
|
|
|
Homework?
Did you done anything by yourself so far?
Let us see your code...
I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is. (V)
|
|
|
|
|
|
I think this should be common problem in Computer science.
I have a data like this
List<Map<Integer,List<String>>> Qdata = new ArrayList<Map<Integer,List<String>>>();
List<Map<Integer,List<String>>> Tdata = new ArrayList<Map<Integer,List<String>>>();
List<String> Qg1 = Arrays.asList("C", "A", "PC", "R");
List<String> Qg2 = Arrays.asList("DQ", "EQ", "KC", "AC");
List<String> Qg3 = Arrays.asList("KQ", "AT");
List<String> Qg4 = Arrays.asList("KQ", "AT", "DQ", "KC","AC","KQ", "AT", "KC","AC","KQ", "AT", "DQ", "KC","AC");
List<String> Qg5 = Arrays.asList("KQ", "AT", "DQ", "KC","AC");
List<String> Qg6 = Arrays.asList("KQ", "AT", "DQ", "KC","AC");
List<String> Qg7 = Arrays.asList("AC","KQ", "AT","AT", "DQ", "KC","AC");
Map<Integer,List<String>> Qmap = new HashMap<Integer, List<String>>();
Qmap.put(1, Qg1);
Qmap.put(2, Qg2);
Qmap.put(3, Qg3);
Qmap.put(4, Qg4);
Qmap.put(5, Qg5);
Qmap.put(6, Qg6);
Qmap.put(7, Qg7);
List<String> Tg1 = Arrays.asList("C", "A", "PC", "?");
List<String> Tg2 = Arrays.asList("KQ", "AT","DQ", "EQ", "KC", "AC");
List<String> Tg3 = Arrays.asList("AT", "DQ", "KC","AC");
List<String> Tg4 = Arrays.asList("KQ", "AT", "DQ", "KC","AC","KQ", "AT", "KC","AC");
List<String> Tg5 = Arrays.asList("KQ", "AT", "DQ", "KC","AC");
List<String> Tg6 = Arrays.asList("KQ", "AT", "DQ", "KC","AC");
List<String> Tg7 = Arrays.asList("AT","AT", "DQ", "KC","AC");
List<String> Tg8 = Arrays.asList("AC");
List<String> Tg9 = Arrays.asList("ACL","AC","C","A","PC");
Map<Integer,List<String>> Tmap = new HashMap<Integer, List<String>>();
Tmap.put(1, Tg1);
Tmap.put(2, Tg2);
Tmap.put(3, Tg3);
Tmap.put(4, Tg4);
Tmap.put(5, Tg5);
Tmap.put(6, Tg6);
Tmap.put(7, Tg7);
Tmap.put(8, Tg8);
Tmap.put(9, Tg9);
Qdata.add(Qmap);
Tdata.add(Tmap)
want to match Qdata with Tdata, the tricky part here is, if you observe the data
Qg3+Qg2 forms Tg2
Tg4+Tg3 forms Qg4 with "kQ" missing between Tg4 and Tg3
Tg8+Tg9 forms Qg7
and with the rest, it is pretty straight forward. I don't know how to deal with this tricky part.
I used map to store the data because it is more desired for the algorithm to finds matching in the same position in Tdata and Qdata like
Qg5 has a complete match with Tg5 Qg6 has a complete match with Tg6
The final ideal output that I expect in this case is:
Qg1 matches with Tg1 with a wild card("?") (some penalty for wild card)
Qg3+Qg2 matches Tg2
Qg4 matches Tg4+Tg3 (some penalty for missing word
Qg5 has a complete match with Tg5
Qg6 has a complete match with Tg6
Qg7 matches with Tg8+Tg9 (penalty)
and penalty for extra Tg9.
I already tried longest common subsequence and needleman wunsch algorithms they are good in aligning with gaps but I don't know how to mix two parts and match them like the tricky part I mentioned and how to teach algorithm when to mix parts and start matching and when not to?
Sorry for my bad english
I'm currently coding in java.
Any suggestions will very much keep me alive and get going.
Thanks in advance
|
|
|
|
|
I have a DAG of N nodes ( say million ) that I will querying for connectivity of two nodes [ isConnected(a,b} ]. I will be querying the DAG M ( say million ) times. Is there a way to optimize the process?
Here are the best approaches that I could come up with.
BFS = O( M * N )
Dijkstra = O( M* E* log N)
Is there any other better approach for this process ?
|
|
|
|
|
Dear all,
I am trying to do dual axis solar tracker with seasonal tilt.
Necessary Document:
1)Below links gives us calculation sun elevation/ azimuth angle.
http://www.nrel.gov/midc/spa/[^]
2)i am using Inclinometer to determine actual motion of tracker
Questions:
1) can someone give me algorithm flowchart for Dual axis solar tracker.
2)Dual axis tracker will move either horizontal/ vertical axis .How/when to set motion of motor along its axis.
3)what are the angle we need to taken consideration for calculation.
|
|
|
|
|
Hello, I have a variation of the weighted activity selection problem I could use some help with. The problem is that there are activities that have a start time, finish time, and profit. I need to find the maximum profit achievable with the variation that there must be more "short" activities used than "long" activities. Where a short activity is an activity with duration less than 5 (finish time - start time). I have solved the problem without the variation, not sure how to implement the restrictions. This is homework so i am only looking for help with the recursion.
|
|
|
|
|
"...there must be more "short" activities used than "long" activities."
In the recursive step (where I assume you add another activity), just skip adding "long" activities when the number of short activities is less than or equal to the number of long activities minus one.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
