Re: Travelling Salesman Problem - Algorithms Discussion Boards

Re: Bresenhams algorithm for drawing lines

Jörgen Sigvardsson6-Nov-06 14:09

6-Nov-06 14:09

Yes. I think I saw too many trees, ran into a couple of them, got under one, and climbed one too many - so no, I didn't see the forrest. Big Grin | :-D

Thanks, both of you. I understand Bresenham's line algorithm now. Jig | [Dance]

--
Torn from tomorrow's headlines

Re: Bresenhams algorithm for drawing lines

Michael Dunn7-Nov-06 15:27

Michael Dunn

7-Nov-06 15:27

The equation for a line that you're probably familiar with is

5) y = mx + b

where m is the slope and b is the Y-intercept. You can get from 1) to 5) with algebra:

ax + by + c = 0
ax/b + y + c/b = 0 [divide both sides by b]
y = -ax/b - c/b    [subtract the same term from both sides] 
y = Mx + B         [substitute M = -a/b, B = -c/b]

You can prove that B = -c/b is the Y-intercept by evaluating 1) for x=0.

--Mike--
Visual C++ MVP Cool | :cool:

LINKS~! Ericahist | PimpFish | CP SearchBar v3.0 | C++ Forum FAQ

Nearest neighbour algorithm

Islam Khalil Saber6-Nov-06 4:33

Islam Khalil Saber

6-Nov-06 4:33

i want to see code for Nearest neighbour algorithm
-for example
if i have 3 classes each one have X1 .X2,X3
and i have afile contain 100 pattren i choose 50 raqndomly to know in witch class

If I HaD OnE sInglE wIsh IwIll gO back for thE fIrst tIme i sEE yOu

Re: Nearest neighbour algorithm

ejuanpp6-Nov-06 4:54

ejuanpp

6-Nov-06 4:54

Could you please explain this a bit more ?

Re: Nearest neighbour algorithm

Islam Khalil Saber6-Nov-06 13:13

Islam Khalil Saber

6-Nov-06 13:13

i want an example of how this algorithm can be implement
in c#

If I HaD OnE sInglE wIsh IwIll gO back for thE fIrst tIme i sEE yOu

Travelling Salesman Problem

and_reas5-Nov-06 23:11

and_reas

5-Nov-06 23:11

can somebody give me the source code of this problem (TSP travelling salesman problem) in java ?? or somewhere similar ???

please ???

Re: Travelling Salesman Problem

Just me at will_george...something6-Nov-06 6:01

Just me at will_george...something

6-Nov-06 6:01

I SHOULD NOT reply because I'm SO BAD at Math.. but I had to!

I found one Open Source program.. There are MANY out on the NET.

http://sourceforge.net/projects/jcconvenant

I only responded to this because this is the only Math subject I ever got a 'A' in.. I had the C# code I used for the grade but I cannot find it. (You would be more than welcome to it BUT.. I'm affraid it's lost) It has been been awhile since it was made. Sorry! As I remember it took me forever to get it right.

If it helps, I found a book at the time which 'at least made me understand the subject'

Algorithms In C, Third addition, Graphic algorithms, Part 5, by Robert Sedgewick, Addison-Wesley

Re: Travelling Salesman Problem

Steve S7-Nov-06 1:03

Steve S

7-Nov-06 1:03

Just me at will_george...something wrote:
Algorithms In C, Third addition, Graphic algorithms, Part 5, by Robert Sedgewick, Addison-Wesley

Excellent choice. There are C++ versions available as well, with parts 1-4 (in a single volume), and part 5.

Steve S
Developer for hire

Re: Travelling Salesman Problem

Just me at will_george...something8-Nov-06 2:22

Just me at will_george...something

8-Nov-06 2:22

There are C++ versions available as well.. That is what I have! I really did not fing <<< (I thought I typed FIND) it hard to translate it to C# Well, the graphic part was a bit of a problem though. I only mentioned this book because I'm sort of stupid at math (but I love to try!) and this book at least made me think I knew what I was doing!

Re: Travelling Salesman Problem

mehata7-Nov-06 16:57

mehata

7-Nov-06 16:57

Hi, iam the mathematics person.can anyone give me the problem so i can sure help on it.
please give me the problem then i will think on it.

mehata sheetal

Re: Travelling Salesman Problem

Just me at will_george...something8-Nov-06 2:12

Just me at will_george...something

8-Nov-06 2:12

Hi, iam the mathematics person.can anyone give me the problem so i can sure help on it. please give me the problem then i will think on it......

Hi, I'm the mathematics person. Can anyone give me a problem? I'm sure I can help you with it.

I changed some of the English... LOL.. Not that I am a expert on it. I have been doing it for only 65+ years. I still get it all wrong!

Really! There is NO HATE HERE toward anybody.. I just thought it was funny from my point of view. I have a strange mind and had a good laugh. Good way to start a day. Thank You!

By the way, I know no other language except my Chicago style English. I'm in wonder of people that speak or write in other languages! Amazing! I have a 'TIN' ear and cannot get the 'words' spoken in my brain.

I'm about as poor at Math as my English!

Anyway... My question, which I'm sure is stupid. (I have no shame so I'll ask it anyway.)

I hope I can explain what I am thinking of....

Using Trig in a C# program or other (I mention C# because it is what I usually use now) I see strange results on what I try to do. (I would assume it is me) BUT I had this thought in my little old brain. The way I see it, Trig. is based on a true circle. However when I make a picturebox, panel or other it is always some sort of square or rectangle with my bitmap or Draw object within it. (Does Microsoft have a true circle Control?) If I want a theta, I 'think' it is sort of based on the mouse/joystick input from the picturebox/panel/whatever which is a square/rectangle..

What am I missing? I'm lost.

Bless YOU!

Re: Travelling Salesman Problem

DHIRAJ SHETI7-Dec-06 18:05

DHIRAJ SHETI

7-Dec-06 18:05

HI,

i m transportation engg. M.tech student. i want to learn matlab. how to start it from the begining????

i want to solve genetic algorithm for my project work. is matlab will be simple or c programme???????

REPLY ME

HAVE A NICE DAY

Re: Travelling Salesman Problem

ed^nrgc6-Nov-06 6:18

ed^nrgc

6-Nov-06 6:18

Don't crosspost.

Cross poster not doing their own homework

leckey6-Nov-06 6:45

leckey

6-Nov-06 6:45

Nuff said.

Re: Cross poster not doing their own homework

Paul Conrad7-Nov-06 6:53

Paul Conrad

7-Nov-06 6:53

leckey wrote:
Nuff said.

Yeppers.

Re: Cross poster not doing their own homework [modified]

Just me at will_george...something8-Nov-06 2:33

Just me at will_george...something

8-Nov-06 2:33

not doing their own homework..

I sort of agree BUT in my math classes (which I take just because I love frustration) I have used comments/code from 'other' sources that got me a reasonable grade.. Sometimes FAILED using it! BUT it gave me insight to things I never knew before. Nuff Said.

-- modified at 8:51 Wednesday 8th November, 2006

I'm adding this because I'm old and hit the Post Message Button before I was finished.

I wanted to say that I can do almost anything with my hands without hardly thinking except draw/paint. My Mom can paint anything.. All I get is a blob!
Must be the Math in drawing objects! One time I carved a almost perfect Elephant in wood that everybody I know just LOVES it.. I have no idea how I did it.. I carved while watching Twilight Zone or something..

Not everybody that asks a question is asking for homework for you to do.. Well, maybe AOT but what does that matter? Their 'homework' will work out in the end when they cannot do the job.. BUT.... maybe somebody out there will become a Great Enginner or Banker keeping 'the books' on YOUR bank account!

Destructing a large data structure

Steve M.5-Nov-06 15:56

Steve M.

5-Nov-06 15:56

I have a general question about de-allocating memory for large data structures.

If you have any large data structure, say a tree with many nodes, your destructor (assuming you're working in C++) would have to traverse each node to destroy it, right? Essentially, your destructor is an O(n) operation, where n is the number of nodes in the data structure. Makes sense so far, right?

Maybe I'm horribly naive, but this seems like a very slow way to destroy a data structure. When you close a large document, like a Photoshop document, the document appears to close and release memory quickly. How are the large data structures that make up the document destroyed so quickly? Is it typical for a destructor to traverse each node, or am I missing some well-known practice to get around this?

Thanks,
Steve

Re: Destructing a large data structure

El Corazon5-Nov-06 20:28

El Corazon

5-Nov-06 20:28

there are several ways, one of which is to control your own allocation. You allocate a large block, then divvy it up into smaller pieces that are passed as allocated blocks to nodes, then you can deallocate by the large block if necessary and then everything is gone. Photoshop, in pre 5.0 versions often did not release memory, once allocated it gets thrown on a reuse heap internally. Another way is simply to store pointers to all allocated blocks in a list, then it is a linear release, no traversals for a delete all.

There are papers on internal garbage collection routines and efficient process operations related to almost any subject, including memory allocation.

_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

Re: Destructing a large data structure

Steve S7-Nov-06 1:08

Steve S

7-Nov-06 1:08

Indeed. If you're working with C++ classes, then you can provide class specific new and delete operators (for single objects and arrays). This means that in a Win32 environment you can hit the VMM directly (VirtualAlloc/VirtualFree) if it's appropriate, to do whatever you want.

Just carried out such an exercise on a server app (along with reshaping the internal data representation) and it was worth it - as reported by profiling the app with 'typical' and 'degenerate' loading.

Steve S
Developer for hire

Numerical Recipes in C#

Bassam Abdul-Baki31-Oct-06 5:18

Bassam Abdul-Baki

31-Oct-06 5:18

Not sure this[^] is legal, but it led me to this[^] which seems interesting. The former link is also mentioned in the latter. So it might be.

"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

Re: Numerical Recipes in C#

djlove31-Oct-06 22:42

djlove

31-Oct-06 22:42

Good find.

It always takes me an age to translate something from the book into CS, this is a real time saver!

Re: Numerical Recipes in C#

Just me at will_george...something8-Nov-06 3:09

Just me at will_george...something

8-Nov-06 3:09

The former link is also mentioned in the latter. So it might be.

LOL.. Got me to 'CLICK'

Si units in C++

Toastersparks31-Oct-06 4:34

Toastersparks

31-Oct-06 4:34

Hi!

I'm just looking for your thoughts and ideas on what would be the most elegant way to implement a system of Si units in C++.

Cheers,

--
Mike

Re: Si units in C++

Maximilien31-Oct-06 6:49

Maximilien

31-Oct-06 6:49

Units are only semantic definitions over the variables used in your applications.

In your design, you should mention that all values are in SI units, and offer appropriate conversions functions between base units ( meter, kilogram, ... ) and alternative unit type (inches, pound, onces, ... )

after that, it's only a matter of enforcing, really not hard, those rules.

or maybe I did not understand what you want.

Maximilien Lincourt
Your Head A Splode - Strong Bad

Re: Si units in C++

Stephen Hewitt31-Oct-06 12:01

Stephen Hewitt

31-Oct-06 12:01

Maximilien wrote:
Units are only semantic definitions over the variables used in your applications.

This need not be the case. An interesting discussion can be found here[^] in the Boost documentation. Code can be found in the Boost vault here[^].

Steve

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.