Traveling Salesman Problem

[KantKwitDansin1]

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]

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-lite/how-to-post.html#faq-5.2

 

[Ron Natalie]

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]

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]

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]

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
answering posts than reading the posts they are responding to.

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
extension; Google will allow you access to wotsit. They show two files they
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]

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]

[ ... ]

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)

Since you're (presumably) doing it in C++, you probably want to use
std::istream::read instead of fread -- the latter is more or left-over
from C, and provides little advantage in C++.

 

[Mike Wahler]

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]

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.