Archived

This topic is now archived and is closed to further replies.

CProgrammer

Animal behaviour

Recommended Posts

CProgrammer    303
I have a group of animals. Each has saved which of the other animals he likes to be in company with. Now I want to calculate a group in which all animals like eachother. I just cant seem to come up with a descent algorithm. Any ideas pointers? -CProgrammer

Share this post


Link to post
Share on other sites
CProgrammer    303
Wait a sec. If I find out the cycle in a directed graph would that really be correct?
Lets say this example:
We have Animal A,B,C,D,E,F

A->B->C->D->A
is a cycle.
Then it isnt said that C likes A for instance.
-CProgrammer

Share this post


Link to post
Share on other sites
Captain Nuss    100
To pick up your ABCDEF example...

Take animal A. Check which animals it likes to be with, animals B, D, E and F for instance. You can drop animal C already, as there will be at least one animal that doesn''t like C. So you''ll be left with animals A, B, D, E and F. Now go to the next animal (B) and check which animals in the group it doesn''t like. Eliminate those and go to the next one.

This method has its weaknesses, but it''s a very easy solution. The problem is, that if B doesn''t like E, but the other ones like E, if B gets thrown out by animal C, E isn''t in the list even though no animal is left in the group that doesn''t like E. You can probably work around this somehow by keeping another list of animals that have been thrown out and checking that list when you''ve assembled your basic group.

- Christoph

---
Teamwork Software - Stuff That Does Something

Share this post


Link to post
Share on other sites
CProgrammer    303
quote:
Original post by Captain Nuss
To pick up your ABCDEF example...

Take animal A. Check which animals it likes to be with, animals B, D, E and F for instance. You can drop animal C already, as there will be at least one animal that doesn''t like C. So you''ll be left with animals A, B, D, E and F. Now go to the next animal (B) and check which animals in the group it doesn''t like. Eliminate those and go to the next one.

This method has its weaknesses, but it''s a very easy solution. The problem is, that if B doesn''t like E, but the other ones like E, if B gets thrown out by animal C, E isn''t in the list even though no animal is left in the group that doesn''t like E. You can probably work around this somehow by keeping another list of animals that have been thrown out and checking that list when you''ve assembled your basic group.

- Christoph

---
Teamwork Software - Stuff That Does Something



Thats a way to go yeah, although that problem may get tricky and CPU consuming, but i''ll think it through thanks.
-CProgrammer

Share this post


Link to post
Share on other sites
Dreamforger    122
quote:
Original post by Zahlman
If I understand your question correctly... google for "maximum clique".

... and shortly after that find out that you are trying to solve a NP-complete problem which I doubt you will succeed at. I fact I know you will fail.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Yeah I said cycles but that''s wrong. It''s actually finding the largest complete subgraph.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Yeah it sounds NP-complete, but that''s not bad because all NP-complete problems have the same solution.

1) Enumerate all possible solutions
2) Pick the correct answer

NP-complete problems are a pain because they become intractable quickly, not because they are hard to solve.

Share this post


Link to post
Share on other sites
CProgrammer    303
I think you guys are right, an absolutely correct answer requires calculating all possibilities and taking the best one.
Thats a bummer but well...
-CProgrammer

Share this post


Link to post
Share on other sites