Traveling Salesman Problem

Discussion in 'C++' started by KantKwitDansin1, Dec 11, 2004.

  1. 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.
    KantKwitDansin1, Dec 11, 2004
    #1
    1. Advertising

  2. KantKwitDansin1

    Andre Kostur Guest

    "KantKwitDansin1" <> wrote in
    news::

    > 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
    Andre Kostur, Dec 11, 2004
    #2
    1. Advertising

  3. KantKwitDansin1

    Ron Natalie Guest

    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.
    Ron Natalie, Dec 11, 2004
    #3
  4. KantKwitDansin1

    Chris Theis Guest

    "KantKwitDansin1" <> wrote in message
    news:...
    > 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
    Chris Theis, Dec 11, 2004
    #4
  5. 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.
    KantKwitDansin1, Dec 11, 2004
    #5
  6. KantKwitDansin1

    osmium Guest

    "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
    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?
    osmium, Dec 11, 2004
    #6
  7. 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)
    KantKwitDansin1, Dec 12, 2004
    #7
  8. KantKwitDansin1

    Guest

    [ ... ]

    > 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++.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    , Dec 12, 2004
    #8
  9. KantKwitDansin1

    Mike Wahler Guest

    "KantKwitDansin1" <> wrote in message
    news:...
    > 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
    Mike Wahler, Dec 12, 2004
    #9
  10. 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
    Surendra Singhi, Dec 12, 2004
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vinay Adella

    complexity of Traveling Salesman Problem?

    Vinay Adella, Sep 3, 2003, in forum: C Programming
    Replies:
    4
    Views:
    1,736
    Jack Klein
    Sep 4, 2003
  2. Replies:
    5
    Views:
    959
    Jim Langston
    Sep 11, 2006
  3. Replies:
    0
    Views:
    623
  4. JSH
    Replies:
    61
    Views:
    1,506
    Michael Press
    Aug 21, 2008
  5. Ruby Quiz
    Replies:
    17
    Views:
    299
    Rick DeNatale
    Apr 29, 2009
Loading...

Share This Page