|
Yes. So how can I solve it.I need an alogorithms i can use. I do not want to use brute force solution to check all the possible routes.( As the points are not fixed. )
ihe
|
|
|
|
|
If you want an exact solution, brute force is the only option. If you can find a non brute force solution that gives the optimal route in all cases, you've just proved P=NP. If an approximate solution is good enough, and your points obey the triangle inequality(1) then something like the A* algorythm can be used to fine one. Google is your friend.
(1) the distance from A to C is shorter than the distance from A to B plus the distance from B to C for all points A, B, C.
|
|
|
|
|
I'll give you a hint to help you get started ...
Google for the A* algorithm.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Thank you for the hint.
ihe
|
|
|
|
|
as with the others... you can use brute-force min-max scoring of paths to try all paths. This is an exponential of data therefore inefficient, but always finds the right solution. Every choice generates a new branch of every other choice it has, and so forth, and so on.
A* and Dynamic A* get into AI decisions of "pre-pruning" paths before evaluating them based on some judgement rules. This is not always the "best" solution, but generates a fast "good" solution.
check path navigation in AI game programming wisdom series of books.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
Thank you. Where can find this "AI game programming wisdom series of books" on the web .
ihe
|
|
|
|
|
|
This one's a repost, but a classic and deserving of the new Math forum.
The Klein Four Group[^]
Finite Simple Group (of Order Two)[^]
The path of love is never smooth
But mine's continuous for you
You're the upper bound in the chains of my heart
You're my Axiom of Choice, you know it's true
But lately our relation's not so well-defined
And I just can't function without you
I'll prove my proposition and I'm sure you'll find
We're a finite simple group of order two
I'm losing my identity
I'm getting tensor every day
And without loss of generality
I will assume that you feel the same way
Since every time I see you, you just quotient out
The faithful image that I map into
But when we're one-to-one you'll see what I'm about
'Cause we're a finite simple group of order two
Our equivalence was stable,
A principal love bundle sitting deep inside
But then you drove a wedge between our two-forms
Now everything is so complexified
When we first met, we simply connected
My heart was open but too dense
Our system was already directed
To have a finite limit, in some sense
I'm living in the kernel of a rank-one map
From my domain, its image looks so blue,
'Cause all I see are zeroes, it's a cruel trap
But we're a finite simple group of order two
I'm not the smoothest operator in my class,
But we're a mirror pair, me and you,
So let's apply forgetful functors to the past
And be a finite simple group, a finite simple group,
Let's be a finite simple group of order two
(Oughter: "Why not three?")
I've proved my proposition now, as you can see,
So let's both be associative and free
And by corollary, this shows you and I to be
Purely inseparable. Q. E. D.
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon
Web - Blog - RSS - Math - LinkedIn
|
|
|
|
|
Good read on OGRs.[^]
They have a distributed software application like SETI if you're into that.
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon
Web - Blog - RSS - Math - LinkedIn
|
|
|
|
|
It's interesting that these types of problems have found applications in engineering.
|
|
|
|
|
All Math is related somehow. All all science use Math.
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon
Web - Blog - RSS - Math - LinkedIn
|
|
|
|
|
it's been a long time since i had to do this stuff, and i can't figure out how to solve what seems like it should be a simple calculation...
you have 6000 marbles in a box. 300 of them are black, the rest are white. you draw ten marbles without replacement.
what are the odds that three of the marbles you draw are black ?
|
|
|
|
|
I'd have to look up how to handle the other 7 marbles, but the probability of getting at least 3 black ones is calculated by:
300/6000 * 299/5999 * 298/5998 = 0.000123815
You can approximate it fairly closely with .05^3 for a simpler calculation (comes out to be .000125)
I think you can just multiple the rest of the fractions out:
300/6000 * 299/5999 * 298/5998 * 5700/5997 * 5699/5996 * 5698/5995 * 5697/5994 * 5696/5993 * 5695/5992 * 5694/5991 = 0.000086752
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: the probability of getting at least 3 black ones is calculated by:
300/6000 * 299/5999 * 298/5998 = 0.000123815
isn't that the probability of choosing three black in a row ? those denominators (total number of marbles left) will change, if you draw a white one between black ones.
i believe this problem is classified as a Hypergeometric Distribution problem. but, the technique for calculating that requires that i calculate things like 6000! (a.k.a. 2.69 * 10^20065). there has to be a simpler way to do it.
|
|
|
|
|
Chris Losinger wrote: isn't that the probability of choosing three black in a row ? those denominators (total number of marbles left) will change, if you draw a white one between black ones.
The order doesn't matter. All the numbers are being multiplied. It would be just like if I wrote it as:
(300 * 299 * 298)/(6000 * 5999 * 5998) = ...
Doing just the above calculation will give you the probability of drawing at least 3 black marbles in an unbounded subset of your population. The second formula I gave should give you the probability of drawing exactly 3.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
You're right. Excel has a COMBIN function that returns those large combinations and I'm getting =(COMBIN(300,3)*COMBIN(5700,7))/COMBIN(6000,10)=0.010410216 as the answer.
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon
Web - Blog - RSS - Math - LinkedIn
|
|
|
|
|
ah... good old Excel.
thanks 
|
|
|
|
|
You can also probably try a log base 10 transform.
|
|
|
|
|
If you simplify the combinations, you end up with:
((10 * 9 * 8) / (3 * 2)) * (The second forumula from my original post).
I'm not sure where that coefficient (which evaluates to 120) comes from -- possibly 120 different placements for the black marble selections?
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Chris Losinger wrote: it's been a long time since i had to do this stuff, and i can't figure out how to solve what seems like it should be a simple calculation...
you have 6000 marbles in a box. 300 of them are black, the rest are white. you draw ten marbles without replacement.
what are the odds that three of the marbles you draw are black ?
Hi Chris, I think you want the hypergeometric probability distribution for this problem. This will give you the probability that in a sample of n objects drawn from a population, k will be black (no replacement).
Let:
N = 6000 be the total number of marbles <br />
n = 10 be the number of marbles drawn (your sample)<br />
B = 300 be the number of black marbles <br />
k = 3 be the number you are interested in
Then the probability of having k black marbles in a sample n of the total population N where f() is the probability, is:
f(k;N,B,n) = (B choose k) * ( (N-B) choose (n-k) ) / ( N choose n)
That is, there are N choose n total samples without replacement and B choose k ways to choose k black marbles and N-B choose n-k remaining ways to select.
Hope that helps.
|
|
|
|
|
It's been a while, what's choose again? Is that like: a choose b = a!/b!
Logifusion[^]
If not entertaining, write your Congressman.
|
|
|
|
|
Dustin Metzgar wrote: It's been a while, what's choose again? Is that like: a choose b = a!/b!
Almost, it's a choose b = a!/[b!(a-b)!].
--
Marcus Kwok
|
|
|
|
|
My dumb-dumb Stats 100 textbook says that you can approximate the answer by using the binomial probability distribution.
Conditions:
1. The procedure has a fixed number of trials (10)
2. The trials must be independent.*
3. Each trial must have all outcomes classified into two categories (black and white).
4. The probabilities must remain constant for each trial.
n = # of trials = 10
x = # of successes among n trials = 3
p = prob. of success in any one trial = 300/6000 = 0.05
q = prob. of failure in any one trial = (1 - p) = 0.95
Then
P(3) = (10!) / ((10 - 3)! * 3!) * (0.05)^3 * (0.95)^(10-3)
Which, when I calculated it out, equals 0.0104750594. My TI's binompdf function agrees.
Stats/Math nerds, if this is wrong, please let us know.
* The justification for using this as an approximation even though we're selecting without replacement is this:
"When sampling without replacement, the events can be treated as if they were independent if the sample size is no more than 5% of the population size. (That is, n <= 0.05N.)" 10 <= 300, so we're good.
|
|
|
|
|
Nice solution Jon. I didn't even think of that and sent the poor guy towards the hypergeometric distribution. Then I forgot he had to evaluate these huge factorials... 
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
