Archived

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

CProgrammer

Animal behaviour

Recommended Posts

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
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
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
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
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