Velocity Reviews > C++ > Traveling Salesman Problem

# Traveling Salesman Problem

KantKwitDansin1
Guest
Posts: n/a

 12-11-2004
I have the following assignment, but I am not familiar at all with .dat
files and how to use them as input and to generate a .dat file as
output. Our final grade is based on if the program works on the
running time. Could someone please assist me with this problem.
Thanks!
Traveling Sales Man
--Problem Description: A salesman must visit n cities. He wishes to
visit each city exactly once and finish at the city he starts from.
There is an integer cost c(i, j) to travel from city i to city j, and
the salesman wishes to make the tour whose total cost is minimum, where
the total cost is the sum of the individual costs along the edges of
the tour.
* Input: city.dat, containing a 10 x 10 adjacency matrix of positive
integer cost.
* Output: tour.dat, containing a 1D array of the tour path.

Andre Kostur
Guest
Posts: n/a

 12-11-2004
"KantKwitDansin1" <(E-Mail Removed)> wrote in
news:(E-Mail Removed) ups.com:

> I have the following assignment, but I am not familiar at all with .dat
> files and how to use them as input and to generate a .dat file as
> output. Our final grade is based on if the program works on the
> running time. Could someone please assist me with this problem.
> Thanks!
> Traveling Sales Man
> --Problem Description: A salesman must visit n cities. He wishes to
> visit each city exactly once and finish at the city he starts from.
> There is an integer cost c(i, j) to travel from city i to city j, and
> the salesman wishes to make the tour whose total cost is minimum, where
> the total cost is the sum of the individual costs along the edges of
> the tour.
> * Input: city.dat, containing a 10 x 10 adjacency matrix of positive
> integer cost.
> * Output: tour.dat, containing a 1D array of the tour path.

Tell you what... why bother sending _you_ the answer to the assignment, why
don't we just submit the assignment directly to your professor?

See: http://www.parashift.com/c++-faq-lit...t.html#faq-5.2

Ron Natalie
Guest
Posts: n/a

 12-11-2004
KantKwitDansin1 wrote:
> I have the following assignment, but I am not familiar at all with .dat
> files and how to use them as input and to generate a .dat file as
> output.

There's no standard concept as "dat" file. You need to inquire of
your isntructor just what the format of these files are.

Chris Theis
Guest
Posts: n/a

 12-11-2004

"KantKwitDansin1" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
> I have the following assignment, but I am not familiar at all with .dat
> files and how to use them as input and to generate a .dat file as
> output. Our final grade is based on if the program works on the
> running time. Could someone please assist me with this problem.
> Thanks!
> Traveling Sales Man
> --Problem Description: A salesman must visit n cities. He wishes to
> visit each city exactly once and finish at the city he starts from.
> There is an integer cost c(i, j) to travel from city i to city j, and
> the salesman wishes to make the tour whose total cost is minimum, where
> the total cost is the sum of the individual costs along the edges of
> the tour.
> * Input: city.dat, containing a 10 x 10 adjacency matrix of positive
> integer cost.
> * Output: tour.dat, containing a 1D array of the tour path.
>

You donŽt need to be familiar with dat files (there is no standard format
anyway) because the problem description includes what youŽll find. So you
just need to go ahead, read the matrix, construct the energy function, etc.,
etc.

Why donŽt you show us what youŽve got & people will be willing to help you
with specific questions. You know, the thing with homework assignment is
that you are the one who should learn something by doing it and not that
others should demonstrate that they can do it for you.

Chris

KantKwitDansin1
Guest
Posts: n/a

 12-11-2004
I am not seekinga direct solution to the assignment, just an
explanation of how to work with .dat files, since this was the first I
have seen of them. I found out they are binary files and, therefore
cannot be handled by text editors. I need to use fopen and fread to
access the date. Thanks to you who did not attack me for asking a
question regarding a file type of which I am not familiar.

osmium
Guest
Posts: n/a

 12-11-2004
"KantKwitDansin1" writes:

>I am not seekinga direct solution to the assignment, just an
> explanation of how to work with .dat files, since this was the first I
> have seen of them. I found out they are binary files and, therefore
> cannot be handled by text editors. I need to use fopen and fread to
> access the date. Thanks to you who did not attack me for asking a
> question regarding a file type of which I am not familiar.

It is an unfortunate Usenet factoid that some people spend more time

As has already been said, a .dat file is not a well known file format. When
confronted with a new file extension I go to wotsit and type in the
call .dat, I don't know if either of them are what your instructor has in
mind. I hope the first one isn't, I didn't look at the other one.

Binary files are accessed using read() and write() rather than the textual
oriented methods you are probably familiar with. A binary file is linked to
a particular hardware system, in terms of size, representation (one or twos
complement) and big endian/little endian. To use a binary file with an
undisclosed (so far) format sounds like severe overkill for your problem. I
am certainly glad I am not in that course.

BTW, you indicate you have to meet some running time constraints. Just out
of curiosity, what are those constraints?

KantKwitDansin1
Guest
Posts: n/a

 12-12-2004
Thanks for the wotsit tip. Running time constraints...well, it is for
an algorithms class so runing time is a big factor. It can be as fast
or slow as we want, but the faster and more efficient it is, the higher
score we receive. I have decided to tackle a different problem now,
though it still deals with binary files. The file contains an array of
10^4 32 bit integers and I need to determine if they are prime ( the
primality I will have to deal with later). I need to read in 32 bits
and thats the first number, read in another 32 bits and thats the 2nd
number, etc. I'm not sure how to specify the number of bits to be read
in at a time.. is it something like this? fread(char, sizeofchar,
numberofelements, filepointer)

jcoffin@taeus.com
Guest
Posts: n/a

 12-12-2004
[ ... ]

> I need to read in 32 bits
> and thats the first number, read in another 32 bits and thats the 2nd
> number, etc. I'm not sure how to specify the number of bits to be

> in at a time.. is it something like this? fread(char, sizeofchar,
> numberofelements, filepointer)

Since you're (presumably) doing it in C++, you probably want to use
from C, and provides little advantage in C++.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Mike Wahler
Guest
Posts: n/a

 12-12-2004
"KantKwitDansin1" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> Thanks for the wotsit tip.

In this case, 'wotsit' is not a pertinent 'tip'.

The file format is defined by your assignment. That's
where to get the format, not from 'wotsit'. ".dat" is
simply a sequence of characters, it does not denote
any 'standard' format. E.g. a '.dat' file could be
plain text (as I suspect is the format of your assignment's
files), a bitmap file, a proprietary format, etc., etc.

-Mike

Surendra Singhi
Guest
Posts: n/a

 12-12-2004
KantKwitDansin1 wrote:
> I have the following assignment, but I am not familiar at all with .dat
> files and how to use them as input and to generate a .dat file as
> output. Our final grade is based on if the program works on the
> running time. Could someone please assist me with this problem.
> Thanks!
> Traveling Sales Man
> --Problem Description: A salesman must visit n cities. He wishes to
> visit each city exactly once and finish at the city he starts from.
> There is an integer cost c(i, j) to travel from city i to city j, and
> the salesman wishes to make the tour whose total cost is minimum, where
> the total cost is the sum of the individual costs along the edges of
> the tour.
> * Input: city.dat, containing a 10 x 10 adjacency matrix of positive
> integer cost.
> * Output: tour.dat, containing a 1D array of the tour path.
>

I feel the format of the input file is plain ascii, try opening it with
xemacs (notepad ) or any other editor you are comfortable with.

The ".dat" stands for data, and it is a very common extension used for
data input files. I remember getting(and giving) assignments, in which
the file extension is .dat

And for reading the file the simple

int x;
ifstream ifs("blah.dat");
ifs>>x;

or something similar to it will work. I suspect your file contains
integer data.

--
Surendra Singhi

www.public.asu.edu/~sksinghi