140 - Bandwidth

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Wed Jan 02, 2002 8:10 pm

I solve 140(Bandwidth) by permutating all pattern and calculate the bandwidth.
But I think this is really slow, can anyone tell me the quick algorithm to solve 140?
Thanks a lot!

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh » Thu Jan 03, 2002 11:51 pm

Unfortunately, there is no quick solution to this problem.

Backtracking with good cutoffs is probably efficient enough.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi » Fri Feb 01, 2002 2:07 pm

Is there any trick in this problem? I should generate all the permutation, and select that one with the minimum bandwith what is the first in lexicaly oreder. But why my program gets WA? Because of the blank graphs/lines? What sould I print if there is one?
-> 0
Is it ok?

Lawrence
New poster
Posts: 17
Joined: Sat Feb 09, 2002 2:00 am
Location: China
Contact:

Post by Lawrence » Sat Feb 23, 2002 3:56 pm

How fast would you want? My complete search algorithm only runs 0.47 sec, this is enough for me.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Apr 17, 2002 11:02 pm

I permutate and then check the bandwidth. It takes forever since my bandwidth checker is O(26^2). Any ideas on how to check bandwidth faster?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Apr 18, 2002 2:16 am

Well, the first thing to do is to go down to O(8^2) by renaming the nodes to A,B,C,... consecutively. Then, you can gain some speedup if you build the permutations recursively and while building them already partly calculate the bandwith. Of course this also works in the iterative version, but only if you do it yourself rather than to rely on next_permutation of the STL.

If you want it really fast, you should have a look at the programs Skiena mentions in his book. Reportedly you can solve cases with 30 nodes in about a second or a minute, I don't remember.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Thu Apr 18, 2002 10:38 am

You mean the Algorithm Design Manual? I will check it out when I get back from Cali. Thanks for the tip.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Apr 18, 2002 11:33 am

Yes, that's the one I meant. You can get a small part of it here:
http://www.cs.sunysb.edu/~algorith/file ... idth.shtml

You can also find two implementations of solutions there, I believe from his students. And at least one of them contains a little documentation of the used algorithm somewhere.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Mon Apr 22, 2002 1:02 am

Just to clarify, I have the book and have read it several times. I was trying to devise a novel algorithm:P

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

140 - bandwith

Post by titid_gede » Mon Apr 21, 2003 5:21 pm

is sample output for problem 140 correct? or just only to show the right output format? i was curios since (correspond to sample input) node F is not adjacent of node C, but the sample output gives F after C.
thank you very much.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Mon Apr 21, 2003 9:40 pm

Titid, ... you misunderstood the problem. The sample output is correct. You're asked to print the optimal ordering of the nodes, ... you need to understand the pictures that describe ABCDEHGF and ABCDGFHE orderings ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Tue Apr 22, 2003 5:26 pm

aha, I see, yes i misunderstood the problem, i got AC, thank you pak haryanto.

ivec
New poster
Posts: 8
Joined: Tue May 27, 2003 2:41 pm
Contact:

140 - Bandwidth

Post by ivec » Sat Jun 28, 2003 12:42 am

I had no luck on this one so far... first problem I seem to stumble on.
What would be a good approach?

Googling lead me to consider some "cuthill-mckee" algorithm, but I haven't been able to find a description of that algorithm online. Does anyone have such a description ?
Also, I'm not sure if the algorithm can easily find the lexicographically smallest solution.

So, at this stage, I would really be thankful for any links to some reference and/or hints towards a working approach.

TIA! -- Ivan

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sun Jun 29, 2003 5:53 am

I think this problem is NP... so your best hope is brute-force with some pruning...

dennis
New poster
Posts: 5
Joined: Fri Aug 01, 2003 4:41 am
Contact:

140

Post by dennis » Sun Aug 10, 2003 6:10 am

Can anyone help me with this problem?
thx for any hints

Post Reply

Return to “Volume 1 (100-199)”