|
Define the DFA "state" of an NDFA as being the list of all states that the NDFA "could" be. Then determine for each possible combination of states, what combinations of states could occur as a result of each possible input character. For example, consider the following NDFA:
1. START STATE. If input is "T", maybe advance to state 2. In any case, maybe stay in state 1.
2. If input is "E", advance to state 3.
3. If input is "S", advance to state 4.
4. If input is "T", advance to state 5.
5. If input is "E", advance to state 6.
6. If input is "R", advance to state 7.
7. ACCEPTING STATE. Stay in state 7 regardless of input.
It's possible that the machine will only be in state 1 (call that DFA state "1").
If it's in DFA state 1 and it gets a "T", it could be in state 1 or 2 (call that DFA state "1/2"); if it gets anything else, it can only be in state 1.
If it's in DFA state "1/2" and it gets a "T", it could be in state 1 or 2; if it gets an "E", it can be in state 1 or 3 ("1/3"). Anything else, it can only be state 1.
If it's in DFA state "1/3" and it gets a "T", it could be in state 1 or 2; if it gets an "S", it can be in state 1 or 4 ("1/4"). Anything else, it can only be state 1.
If it's in DFA state "1/4" and it gets a "T", it could be in state 1, 2, or 5. Anything else, it can only be state 1.
If it's in DFA state "1/2/5" and it gets an "E", it could be in state 1, 3, or 6. Anything else, it can only be state 1.
If it's in DFA state "1/3/6" and it gets an "R", it could be in state 1 or 7 (though state 1 won't really matter); if "S", it can be in state 1 or 4; if "T", state 1 or 2. Anything else, it can only be state 1.
If it's in DFA state "1/7", one could evaluate further state transitions, but since "acceptance" is guaranteed, they're moot.
|
|
|
|
|
|
Did you try a search?[^]
CQ de W5ALT
Walt Fair, Jr., P. E.
Comport Computing
Specializing in Technical Engineering Software
|
|
|
|
|
Hey does anyone know of an algorithm to find the point that resides inside a polygon that is farthest (on average) to any other point in the polygon? The polygons don't have to be regular and not all points can see the other points (IE you may not be able to draw a line between every point without intersecting the outer edge of the polygon)
|
|
|
|
|
Look up how to calculate the centroid of an arbitrary area. This comes out of the more general study of moments of area.
The wonderful thing about the Darwin Awards is that everyone wins, especially the members of the audience.
|
|
|
|
|
My understanding of centroid means that if your polygon was in the shape of the letter C the centroid would be somewhere outside the polygon (in the middle of the c that is). I could be wrong though.
|
|
|
|
|
Yes, certainly with concave polygons the centroid may but doesn't necessarily lie outside.
If I'm understanding your problem this time, you need to formulate it by taking the double integral over the area of the polygon of the distance to each point and an arbitrary point (x,y). Personally, I'd use distance squared and get rid of the pesky square root. Then once you've established the equation of the distance squared over the area, you take the partial derivatives with respect to x and y and find the maximum. The rub probably comes when you have to restrict (x, y) to lie "inside" the polygon. Off the top of my head, that part isn't clear. I'm on the road and tired so that part is left up to the student. 
The wonderful thing about the Darwin Awards is that everyone wins, especially the members of the audience.
|
|
|
|
|
Thanks Tim, this has put me on the right track. I am developing an algorithm that will do just this, I hadn't even considered that it was a maximization problem until now. I'll get back to you with my results.
|
|
|
|
|
I'd like to hear, especially the constrait to the body of the polygon part. It's easy to say but, I think, mathematically it might me more difficult to express. At least generally.
I made it to the airport and, hopefully, tonight I'll be home.
The wonderful thing about the Darwin Awards is that everyone wins, especially the members of the audience.
|
|
|
|
|
This is a very interesting question. I don't know if there is a known algorithm for that (but I guess there must be).
Just a thought: maybe you can start working on a basic idea like drawing a line from each vertex to the middle point of each side (excluding the two sides on which the vertex stands). Then examine the intersection points of these lines (excluding those that lie outside the polygon) and find the one which is farthest on average from all vertexes.
Not sure if this is the right way to go, but I hope I gave you some idea to work on. 
Let me know if you find the solution, I'll be very interested.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
To calculate the centroid of a polygon:
Source: http://en.wikipedia.org/wiki/Centroid[^] and http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/[^]
PointF centroid(PointF[] p) {
float cx = 0;
float cy = 0;
float a = 0;
float ca;
for (int i = 0; i < p.Length; i++) {
ca = x[i] * y[(i + 1) % p.Length] - x[(i + 1) % p.Length] * y[i];
cx = cx + (x[i] + x[(i + 1) % p.Length]) * ca;
cy = cy + (y[i] + y[(i + 1) % p.Length]) * ca;
a = a + ca / 2;
}
cx = cx / (6 * a);
cy = cy / (6 * a);
return new PointF(cx , cy);
}
By the way, I am not sure if what you need is a centroid. Hope this helps, anyway.
|
|
|
|
|
I have raw metal sheets of various rectangular sizes (x1*y1, x2*y2,
... xn*yn).I want select best fit sheet which fullfill my requirement for getting new sheets of X*Y it also has some tolerence.
e.g
I have metals sheets like 200*100,300*200,250*500,50*100,100*100
and I Require 3 pieces of 100*100 with 3mm tolerence.so how do I find the best fit soluion and how do I implement this logic.
Thanks in advance.
|
|
|
|
|
I am guessing that the effort involved in implementing would be extensive and difficult unless you are a major gemotry geek. After a little searching it seems some of the relevant keywords that lead to academic articles on the topic are "Nesting", and "No Fit Polygon". Since nesting could get you more bird articles you might want to include "sheet metal" or "CAD" in your search. I know it isn't an answer, but it should help your search.
|
|
|
|
|
thx for your suggestion. if any one has done same kind logic for cutting it will be more helpful for me.
|
|
|
|
|
I know it can be done for example with Dynamic Programming[^], but it requires expertise in that particular technique.
My suggestion if you're not specifically into optimization is to go for a stochastic algoritm like Simulated Annealing[^] or a greedy algorithm derived from the classical Kanpsack Problem[^], since they are very easy to implement, not time intensive, and give good results. In both cases, the trick to make it work for your case is to find the right Heuristic[^] function, that is the function to decide wich placing of each rectangular shape is better at a certain iteration.
Another very good approach is using Rectangle Packing algorithms. Google that and you should find info.
Just as a reference, there are many generic optimization techniques, which can apply to specific cases depending on requirements and problem modeling, you can have a look Here[^] for an overview.
Good luck. 
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
thx for suggestion. but any one has done same kind of sheet cutting logic it will more helpful for me.
|
|
|
|
|
Hi all,
I am creating a little program for scoring RadioControl contests.
First, I distribute the pilots (say they are 30) in 3 groups of 10, and repeat it (in different combinations) several rounds (say 6 rounds)
In each round, each pilot flies one time, only in one group, against other 9 pilots.
I create the groups randomly. Then I count scores and present it.
BUT, the big BUT is some pilots complaint: "I have only flied 1 time against pilot nameJoe , and 4 times against pilot namePeter"
So I need some direction for creating R rounds of N pilots in G groups, trying that all the pilots have flied against each of the other pilots a similar number of times (ideally the same number of times, but if not, with a little difference).
I.e.: this is a contest of 6 pilots (A,B,C,D,E,F), 4 rounds, 2 groups:
ABC DEF
AFC BED
EBD ACF
FCE ADB
A has flied 2 times against B and 3 against C, but none against E
Thank you for any sugestion.
Alex
modified on Thursday, May 27, 2010 6:33 PM
|
|
|
|
|
|
I know there's a few tournament organization algorithms, but I'm not much into that, so I can't suggest you any.
You are using a stochastic algorithm, which can surely be ok. You just need to add some logic to de-randomize matchings in order to get the result you need.
A simple approach can be holding the number of times each pilot flies against each other in a list (array).
Select a random pairing, then randomly select one of the two paired pilots (or just iterate through pilots and choose the second pilot randomly, this depends on how you currently do pairing ofc).
Look into the selected pilot's list, starting at the index corresponding to the second pilot, then proceed in one direction until you get to the same position, holding the index of the cell with the least value you find.
When you're done, change the second pilot to the one whose corresponding cell held the least value.
This is the basic rough idea, it must of course be adapted to your current algorithm and data structures.
It should ensure a certain degree of randomness and come close to the result you need.
Good luck.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
In fact, I was doing a similar aproach, using an array for counting the matches between each pair of pilots. But I got problems when swapping the pair of pilots for correcting the anomalies.
Actually, this is an old problem. Just yesterday, googleing, I found
http://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem[^]
There are some solutions. The best I have found use you suggested approach, but adding a "taboo" value, counting the iterations a pair is not swapped:
http://delphiforfun.org/programs/kirkman.htm[^]
Thank you for you help, anyway
Alex
|
|
|
|
|
My pleasure.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
WolframAlpha[^] returns a different joke for a "Tell me a joke" query.
|
|
|
|
|
Q: Why did the mathematician name his dog "Cauchy?"
A: Because he left a residue at every pole.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
|
Hello,
I need to analyze a document and compile a statistics of the sentences that are used more than once. As sentences I actually mean any sequence of words. I read that compression algorithms do something similar to what I want creating dictionaries of blocks of text with a piece of information telling the frequency of it.
Thanks a lot for any help.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
