From Vasai to [code]
Sep. 28th, 2010 10:55 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
davvAs I wrote in an LJ entry, I was thinking about writing some CS problem/algorithm thoughts here. One in particular comes to mind, both because I referred to it on that other entry, and because somehow it's been stuck in my mind - its simple puzzle-like nature may be to blame, there.
(It's a funny thing; I still haven't quite got the DW-LJ balance right. I thought I would put the short "hey d00d" posts on LJ and the long ones here, but the past two LJ entries ended up quite long in themselves...)
But it's quite a jump from my creatures, and so I'll put up a cut here so it won't clutter the page of those that prefer reading about the critters :)
Everybody knows that abstract CS problems need either fancy or descriptive names. I've tended towards the latter, but I'll try one of the former here, so let's call the problem I'll describe, the "tired competitors problem".
Consider some kind of pairwise contest among n competitors. There are 0.5n(n-1) matches because the competitors don't face themselves and face each other only once. However, the type of contest they're engaged in leaves them tired, so each competitor would prefer to wait some time before he has to face somebody else. Say that the outcome of each match will be more chancy the less resting time they get.
Now, the reasonable thing would be to put waiting periods between matches so that the competitors can rest, but those who are arranging the competition would prefer it to be over quickly. Idealize the problem a little, and we're left with this:
Consider the series of matches 1...0.5n(n-1). Each match, call it p, has a score that is equal to the number of matches that pass until one of the competitors are involved in another match (whichever gets involved first). If neither gets involved, the score is equal to k >= 0.5n(n-1), since the competitors will have a long time to rest after the contest will be over. In the standard, k unspecified version of the problem, k = 0.5n(n-1), so no temporary break can be as rewarding as not having to do any more matches.
An assignment is a way of ordering the 0.5n(n-1) matches. The assignment's score is equal to the sum of the scores of all its matches.
Now, what I've been thinking about is: is it possible to find the assignment that has maximum score, in reasonable time? If so, how?
I have made a greedy algorithm that works well, but it doesn't always find the optimum. At each point, among all the contests that remain, determine the backwards score. That score is the distance to the closest of the two competitors involved in the contest in question, were it to be added to the end. Pick the contest with the greatest backwards score. Repeat until done, reverse the assignment (since the score is backwards), and that's the output.
I think that's right. For my particular purpose, the greedy algorithm works well enough, but being who I am, I still wonder about the theoretical optimum.
If you wonder what practical use such an algorithm might have, just ask!
(It's a funny thing; I still haven't quite got the DW-LJ balance right. I thought I would put the short "hey d00d" posts on LJ and the long ones here, but the past two LJ entries ended up quite long in themselves...)
But it's quite a jump from my creatures, and so I'll put up a cut here so it won't clutter the page of those that prefer reading about the critters :)
Everybody knows that abstract CS problems need either fancy or descriptive names. I've tended towards the latter, but I'll try one of the former here, so let's call the problem I'll describe, the "tired competitors problem".
Consider some kind of pairwise contest among n competitors. There are 0.5n(n-1) matches because the competitors don't face themselves and face each other only once. However, the type of contest they're engaged in leaves them tired, so each competitor would prefer to wait some time before he has to face somebody else. Say that the outcome of each match will be more chancy the less resting time they get.
Now, the reasonable thing would be to put waiting periods between matches so that the competitors can rest, but those who are arranging the competition would prefer it to be over quickly. Idealize the problem a little, and we're left with this:
Consider the series of matches 1...0.5n(n-1). Each match, call it p, has a score that is equal to the number of matches that pass until one of the competitors are involved in another match (whichever gets involved first). If neither gets involved, the score is equal to k >= 0.5n(n-1), since the competitors will have a long time to rest after the contest will be over. In the standard, k unspecified version of the problem, k = 0.5n(n-1), so no temporary break can be as rewarding as not having to do any more matches.
An assignment is a way of ordering the 0.5n(n-1) matches. The assignment's score is equal to the sum of the scores of all its matches.
Now, what I've been thinking about is: is it possible to find the assignment that has maximum score, in reasonable time? If so, how?
I have made a greedy algorithm that works well, but it doesn't always find the optimum. At each point, among all the contests that remain, determine the backwards score. That score is the distance to the closest of the two competitors involved in the contest in question, were it to be added to the end. Pick the contest with the greatest backwards score. Repeat until done, reverse the assignment (since the score is backwards), and that's the output.
I think that's right. For my particular purpose, the greedy algorithm works well enough, but being who I am, I still wonder about the theoretical optimum.
If you wonder what practical use such an algorithm might have, just ask!