How sets work (from the STL) work ?
Can somebody post a very basic example
(e.x how can you insert a number and then see all the contents in the set)
that would explain their basic functions ect.
This is a good question to ask Google. (Try “stl set”.)
All container classes in the STL interface much the same way. To create it you must have a type:
vector<int> foo;
A set works the same way:
set<int> bar;
With a set of structured types (i.e. not integers, floats, etc.) you should generally also specify a comparison function, and maybe an allocator. Google for examples (or post again if you can’t find any useful ones).
The usual suspects are available as member functions:
… begin() end() rbegin() rend() size() clear() find() erase() swap()
including the function to place items in your set:
… insert( const T& val )
The insert() function will not insert duplicate objects. That said, an STL set isn’t strictly mathematical; it is possible to have duplicate elements inside.
Finally, it is possible to initialize your set with an array:
int a[5] = { 12, -9, 54, 3000, 42 };
set<int> s( a, a+5 );
Remember, these are simple examples. Please don’t, for example, actually use the number 5 in your code.
[edit]Oh yeah, loop through your set using an iterator to display the value:
for (set<int>::iterator i = s.begin(); i != s.end(); i++) std::cout << *i << endl;
[/edit]
Hope this helps.
Also here’s one question about pascal
so let’s suppose that we have a set variable named s
what would the following command do?
s:=[u,v];
u and v are integers
Is this a trick question?
(Assuming it is not: )
[x,y,z,…] in pascal is set notation. X, y, z, p, q, etc. must be of an appropriate subrange type, or be automagically cast-able to one.
Hence, s must be a set of that subrange type.
An example:
type
t = 0..255;
var
s: set of t;
v, u: integer;
begin
v := 10;
u := 42;
s := [v, u];
if 42 in s
then writeln( 'yeah' )
else writeln( 'fooey' )
end.
Sets are built into the Pascal language. C and C++ do not have built-in set types. (Hence the STL set class.)
I hope you are not learning by studying code where someone wrote s := [u,v];. Such cruft lacks information and purpose --the real meaning of the program. My answer is based entirely upon the syntax of the example in your question.
Computers are stupid, and always will be. Programmers are smart (well, we hope they are at least…;)). At the risk of becoming obnoxious for repeating myself: programmers must first solve the problem themselves to understand the process used in solving the problem; only then can the computer be instructed to follow the process to solve the problem. At no point does the computer ever understand the problem.
[edit]Oh, I notice that you realize s must be a set. If you are trying to solve a specific problem then please give me more information. You can always study Pascal syntax from the manual, but problems fall in the programmer’s domain --which is what you are struggling with methinks…[/edit]
Hope this helps.
Well I am in the second phase of the school contest I had participated in(if you remember …)
and the task is to create the tsp algorithm(travelling salesman problem).
I’ve found an algorithm writen in pascal and I wanted to translate it in c++
That’s why I needed info about sets in pascal and c++.
Here is the code of what I have done until now.Have a look at it if you want but it is not completed yet and i think that it has errors …
#include <fstream>
#include <iostream>
#include <set>
using namespace std;
struct edge
{
int i,j,w;
//elegxei an h edge periexei times
bool isfilled()
{
if ((i>-1) && (j>-1) && (w>-1))
{
return true;
}
else
{
return false;
}
}
void reset_edge()
{
i=j=w=-1;
}
};
struct graph
{
int i,j,weight;
bool checked;
};
int INF=-1;
int n,m;
graph islands[1000][1000],dist[1000];
bool final[1000];
bool solution;
edge curpath[1000];
void readfile();
void displayis();
bool third_edge(int u,int v);
int find_next_node(int u);
bool include_all(set<int> s);
bool cycle(int u,int v);
graph find_min();
int main()
{
graph tmp;
readfile();
cout << n <<’
‘;
cout << m <<’
‘;
displayis();
curpath[0].i=1;
curpath[0].j=2;
curpath[0].w=45;
curpath[1].i=8;
curpath[1].j=4;
curpath[1].w=45;
tmp=find_min();
cout << tmp.i<<’ ‘<<tmp.j <<’ ‘<<tmp.weight<<’
‘;
tmp=find_min();
cout << tmp.i<<’ ‘<<tmp.j <<’ ‘<<tmp.weight<<’
‘;
tmp=find_min();
cout << tmp.i<<’ ‘<<tmp.j <<’ ‘<<tmp.weight<<’
';
return 0;
}
//***Synartiseis
//diabasma arxeioy
void readfile()
{
int r,c,w,i,j;
ifstream input_file(“cyclades.in”,ios::in|ios::binary);
input_file >> n >> m;
for(i=0;i<=m;i++)
{
input_file >> r >> c >> w;
islands[r][c].weight=w;
islands[r][c].i=r;
islands[r][c].j=c;
islands[r][c].checked=false;
islands[c][r].weight=w;
islands[c][r].i=c;
islands[c][r].j=r;
islands[c][r].checked=false;
curpath[i].reset_edge();
}
for (i=0;i<=n;i++)
{
for (j=0;j<=n;j++)
{
if((islands[i][j].weight==0) && (i!=j))
{
islands[i][j].weight=INF;
}
}
}
input_file.close();
}
//emfanisi pinaka
void displayis()
{
int i,j;
for (i=0;i<=n;i++)
{
for (j=0;j<=n;j++)
{
cout << i <<" " << j <<" "<< " "<< islands[i][j].weight << ’
';
}
}
}
//third edge
bool third_edge(int u,int v)
{
int i,c1,c2;
cout <<“third edge”<<’
';
i=c1=c2=0;
while ((curpath[i].isfilled()==true) && (c1<=1) && (c2<=1))
{
if (curpath[i].i==u)
{
c1++;
cout<<“c1=”<<c1<<’
‘;
}
if (curpath[i].j==v)
{
c2++;
cout<<“c2=”<<c2<<’
‘;
}
i++;
}
if ((c1>=1) || (c2>=1))
{
cout<<“true”<<’
‘;
return true;
}
else
{
cout<<“false”<<’
';
return false;
}
}
//vriskei epomeno kombo
int find_next_node(int u)
{
int k;
cout <<“find next”<<’
';
k=0;
while ((curpath[k+1].isfilled()==true) && (curpath[k].i!=u))
{
k++;
}if (curpath[k].i==u)
{
cout << curpath[k].j<<’
‘;
return curpath[k].j;
}
else
{
cout << “failed next”<<’
';
return 0;
}
}
//elegxei gia ton emperiexontai ola ta nisia
bool include_all(set<int> s)
{
int i;
bool b;
set<int>::iterator p ;
p= s.begin();b=true;
while ((b==true) && (i<n))
{
p = s.find(i);
if (p==s.end())
{
b=false;
return b;
}
i++;
}
return b;
}
//elegxei gia sximatismo kykloy
bool cycle(int u,int v)
{
int a;
set<int>s;
set<int>::iterator p ;
p= s.begin();
s.insert(u);
s.insert(v);
a=find_next_node(v);
while ((a!=0) && (a!=u))
{
s.insert(a);
a=find_next_node(v);
}
if (a==0)
{
return false;
}
else
{
if ((a==u) && include_all(s))
{
solution=true;
return false;
}
else
{
return true;
}
}
}
graph find_min()
{
int k,l;
graph min;
min.weight =1000001;
for(k=0;k<=m;k++)
{
for(l=0;l<=m;l++)
{
if ((min.weight>islands[k][l].weight) && (islands[k][l].weight>0) && (islands[k][l].checked==false))
{
islands[k][l].checked=true;
min=islands[k][l];
}
}
}
return min;
}
also don’t read the comments they are written in greeklish(greek with latin characters)
What is more the pascal code I am studying has that s := [u,v]; command…:no:
Ah ha, yes, another NP-Hard problem.:spin:
Are your contest organizers insane?
What are the parameters of the contest, if I may ask?
Where did you get your sample code?
Are you familiar with the Branch and Bound technique (that is, can you show someone how to use it using a pencil and a piece of paper)?
Don’t take this the wrong way, but you need to subscribe to less ambitious contests…:eyebrowlift2:
If I get a chance in the next couple of days I’ll analyze what you’ve got more carefully.
OK smathegreek, I think I’ve found the source. It’s an online PDF titled Analysis of Algorithms, instructive notes by Yannis Manolopoylos, right?
His pseudocode is pascalish… but not pascal. Unfortunately, I don’t understand Greek, and the AltaVista translator doesn’t understand technical papers.
‘Axmh’ means ‘edge’ right?
It looks like this paper deals with a non-symmetric graph.
A bug: in your ‘cycle’ function in the first ‘while’ loop you should have
a=find_next_node(a);
I haven’t finished analyzing the code yet… partly because it is obtuse and partly because I can’t read Greek…
Alas.
Well the contest is the national student programming contest.(although we are not tought programming until the last class of the shool…:rolleyes:)
You are right about the code.I’ve found it in one of his books.Also ahmh does mean edge and the paper deals with a non-symmetric graph.
I 've fixed the error you mentioned however a new problem has occured.
I did some more work in my program and here is the new source:
#include <fstream>
#include <iostream>
#include <set>
using namespace std;
struct edge
{
int i,j,w;
//checks whether the edge has values
bool isfilled()
{
if ((i>-1) && (j>-1) &&(w>-1))
{
return true;
}
else
{
return false;
}
}
void reset_edge()
{
i=j=w=-1;
}
};
struct graph
{
int i,j,weight;
bool checked;
};
int INF=-1;
int n,m;
graph islands[1000][1000],dist[1000];
bool final[1000];
bool solution=false;
edge curpath[1000];
void readfile();
void displayis();
bool third_edge(int u,int v);
int find_next_node(int u);
bool include_all(set<int> s);
bool cycle(int u,int v);
graph find_min();
int main()
{
int cur=0;
int length=0;
graph min;
readfile();
while (!solution)
{
min=find_min();
if((!third_edge(min.i,min.j)) && (!cycle(min.i,min.j)))
{
cur++;
curpath[cur].i=min.i;
curpath[cur].j=min.j;
curpath[cur].w=min.weight;
length=length+min.weight;
if (solution==true)
{
cur++;
curpath[cur].i=min.i;
curpath[cur].j=min.j;
curpath[cur].w=min.weight;
}
else
{
cout << "sol not found"<<'
';
}
cout<<"l " <<length<<'
';
}
}
return 0;
}
//********************************************functions*****************************************
//reads input file
void readfile()
{
int r,c,w,i,j;
ifstream input_file("cyclades.in",ios::in|ios::binary);
input_file >> n >> m;
for(i=0;i<=m;i++)
{
input_file >> r >> c >> w;
islands[r][c].weight=w;
islands[r][c].i=r;
islands[r][c].j=c;
islands[r][c].checked=false;
islands[c][r].weight=w;
islands[c][r].i=c;
islands[c][r].j=r;
islands[c][r].checked=false;
curpath[i].reset_edge();
}
for (i=0;i<=n;i++)
{
for (j=0;j<=n;j++)
{
if((islands[i][j].weight==0) && (i!=j))
{
islands[i][j].weight=INF;
}
}
}
input_file.close();
}
//displays array
void displayis()
{
int i,j;
for (i=0;i<=n;i++)
{
for (j=0;j<=n;j++)
{
cout << i <<" " << j <<" "<< " "<< islands[i][j].weight << '
';
}
}
}
//third edge
bool third_edge(int u,int v)
{
int i,c1,c2;
cout <<"third edge"<<'
';
i=0;
c1=0;
c2=0;
while ((curpath[i].isfilled()==true) && (c1<=1) && (c2<=1))
{
if (curpath[i].i==u)
{
c1++;
cout<<"c1="<<c1<<'
';
}
if (curpath[i].j==v)
{
c2++;
cout<<"c2="<<c2<<'
';
}
i++;
}
if ((c1>=1) || (c2>=1))
{
cout<<"true"<<'
';
return true;
}
else
{
cout<<"false"<<'
';
return false;
}
}
//finds next node
int find_next_node(int u)
{
int k;
cout <<"find next"<<'
';
k=0;
while ((curpath[k+1].isfilled()==true) && (curpath[k].i!=u))
{
k++;
}
if (curpath[k].i==u)
{
cout <<k <<' ' << curpath[k].j<<'
';
return curpath[k].j;
}
else
{
cout << "failed next"<<'
';
return 0;
}
}
//tries to find out whether every town is included
bool include_all(set<int> s)
{
int i;
bool b;
i=0;
set<int>::iterator p ;
p= s.begin();
b=true;
while ((b==true) && (i<=n))
{
p = s.find(i);
if (p==s.end())
{
b=false;
return b;
}
i++;
}
return b;
}
//checks for cycle
bool cycle(int u,int v)
{
int a;
set<int>s;
set<int>::iterator p ;
p= s.begin();
s.insert(u);
s.insert(v);
a=find_next_node(v);
while ((a!=0) && (a!=u))
{
s.insert(a);
a=find_next_node(a);
}
if (a==0)
{
return false;
}
else
{
if ((a==u) && (include_all(s)))
{
solution=true;
return false;
}
else
{
return true;
}
}
}
graph find_min()
{
int k,l;
graph min;
min.weight =1000001;
for(k=0;k<=m;k++)
{
for(l=0;l<=m;l++)
{
if ((min.weight>islands[k][l].weight) && (islands[k][l].weight>0) && (islands[k][l].checked==false))
{
islands[k][l].checked=true;
min=islands[k][l];
}
}
}
return min;
}
however the program does not manage to stop(infinate loop error)
I quess that this has something to do with the find_min or circle functions.
Any help would be really appreciated
One important note.The contest task deals with a symmetric graph
Any ideas ?
Yeah, trash this code and write your own solution. :yes:
I really haven’t had too much time to put into this. I can make my own input data but I would prefer to have yours. Please post it. (The failure to terminate might have something to do with it. Seriously. Contest organizers like to do that kind of thing.)
Also, you need to understand this yourself. You seem to have the right idea to start: somewhere one of your exit conditions is not triggering properly. You have several. Identify them on a piece of paper and list what must happen to have them trigger. Then make sure they are doing what you think they ought to be doing.
Also, you do know that you are supposed to be storing the edges in two separate locations, and why you are to do that, right? (Well, at least according to this algorithm…)
Oh yeah, you don’t need that set iterator (p) in there (since you never use it).
Hope this helps for now… I’ll get to it when I can…
Firstly about the iterator you mean in the circle function right ?
Also here is the input files:
input file cyclades.in
in the first line it contains 2 numbers n & m.
n (1<=n<=1000) represent the number of towens , islands ect. we need to connect and
1<=m<=50000 represent the number of roads that connect the islands & we can use.
The next m lines consist of 3 integers a,b,k(I represent them as i,j,weight in my program in the struct I have created)
1 <= Α < Β <= Ν, 1 <= Κ <= 1000000)
a & b represent 2 islands that are connected with a road.The road’s distance is k (in meters)
Also if there is a road between a & b there will be a road from b to a with the same distance(k)
The output should be the minimum distance of the road that connects all the islands or -1 if this road does not exist.
Here are two testfiles:
testfile 1:
6 11
1 2 45
1 4 12
1 5 61
1 6 51
2 5 18
2 6 2
3 4 9
3 5 37
3 6 14
4 5 14
5 6 52
the output of this file should be
204
testfile 2:
10 15
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 7 6
7 8 7
8 9 8
9 10 9
5 7 11
1 3 6
2 4 8
7 9 15
1 10 20
2 9 25
the output from this file should be
180
I’ve got a moment to look at it now. You really need to think about your exit conditions if your program is to be able to determine whether or not a complete circuit is possible (this is actually very easily computed before you start the TSP algorithm).
Also, I just tried a couple of solutions by hand on your first input file. I don’t know what the contest officials said, but the minimum route is at most 120 (1 2 6 3 5 4). Let me explain:
first, said I, let me get a good first guess. So I drew the numbers 1 through 6 in a circle (this represents the nodes of the graph). Then I drew a line between each connected pair and marked the distance (or weight) of each (these are the edges).
So, starting at 1 (it makes no difference which city you begin at), I took a greedy approach and simply went to the next city with the shortest connecting route, and returned to 1 when I ran out of cities. I got 145 (1 2 6 3 4 5). The first thing I noticed is that this is significantly shorter than 204.
Next, I considered how to loose a few meters by adjusting the order of the last three towns visited (just looking at the picture I drew it caught my attention that the numbers could be added better). That’s how I got 120.
This is good enough for me:
- I know that the route is circuitous, and simple (nothing tricky here)
- I have a reasonable number to aim for (145 or less)
- I know that the contest number provides considerable leeway (it is not impossible for most contestants nor does it require any one particular algorithm to find an answer)
What I have described here is called the Branch and Bound technique.
Also, your input files are over a small enough population that you don’t need a very sophisticated way of storing information in memory. I think Yannis’s duplication of data is confusing you. He is storing the data two ways:
- as list of edges, with weights
- as a matrix of nodes, with weights
This is often done just to make life a little easier when accessing the data… but in your case all you need is one or the other. I think you need to choose one so that you can think about how you are storing the problem a little more clearly.
This is a symmetric graph so you can save yourself some grief by cutting out all that part in the code too…
I’m going to leave it at that for now. I hope this helps. You really need to think about this a bit more. (Sorry)
Also, yes, the set<int>::iterator p; and p=s.begin() are completely unnecessary.
Good luck, and post back if you think you have progressed some.
[edit]
I just noticed that I made a mistake on my first guess. If I had done a truly greedy algorithm the result would be 108 (1 4 3 6 2 5). That’s probably the best answer…
[/edit]
I am trying a different algorithm this time.
Although it seems to work it does not find accurate solutions
Also about the output of the 2 testcases: the output is minimum road length x 4
For the first testcase the minimum road length=51 which means the output should be 204.
Well right now my program creates the output 208(instead of 204)
and in the second testfile it creates the output 188(instead of 180)
here is the new code
#include <iostream>
#include <fstream>
#include<set>
using namespace std;
//variables
int INF=1000001;
int n,m;
int islands[1000][1000];
set<int>s;
//function dclarations
void readfile();
void displayis();
void init_set();
void disp_set();
bool inset(int val);
int g(int i);
//main
int main()
{
readfile();
cout <<n<<' ' <<m<<'
';
displayis();
init_set();
disp_set();
//cout << inset(9)<<'
';
cout <<"length "<< g(1) *4<<'
';
return 0;
}
//reads input file
void readfile()
{
int k;
int r,c,w;
ifstream inpf("cyclades.in",ios::in|ios::binary);
inpf >> n >> m;
for(k=0;k<=m;k++)
{
inpf >> r >>c >>w;
islands[r][c]=w;
islands[c][r]=w;
}
for (r=0;r<=1000;r++)
{
for (c=0;c<=1000;c++)
{
if((islands[r][c]==0) && (r!=c))
{
islands[r][c]=INF;
}
}
}
inpf.close();
}
//displays array contents
void displayis()
{
int r,c;
for (r=0;r<=n;r++)
{
for (c=0;c<=n;c++)
{
cout << r <<" " << c <<" "<< " "<< islands[r][c] << '
';
}
}
}
//initializes set values
void init_set()
{
int r;
for(r=1;r<=n;r++)
{
s.insert(r);
}
}
//displays set contents
void disp_set()
{
for (set<int>::iterator p = s.begin(); p != s.end(); p++)
{
cout << *p << '
';
}
}
//returns true if value exists in set
bool inset(int val)
{
set<int>::iterator p ;
p= s.begin();
p = s.find(val);
if(p != s.end())
{
return true;
}
else
{
return false;
}
}
//g function, finds minimum length
int g(int i)
{
int j=0;
int cost;
int k=0;
cost =INF;
if (s.empty()==true)
{
return islands[i][0];
}
else
{
for(j=1;j<=n;j++)
{
if(inset(j)==true)
{
s.erase(j);
k=islands[i][j]+g(j);
if (k<cost)
{
cost=k;
return cost;
}
}
}
}
}
Any ideas ?
The problem I see in your algorithm is that you can’t count :)). You are overflowing buffers and reaching beyond memory in every cycle
for (r=0;r<=1000;r++)
iterates 1001 times and not 1000 times as you want.
So change all your for cycles accordingly to
for (r=0;r<1000;r++)
I haven’t compiled and tested your program, but it can be the cause of your problems.
He can count, he just has a lot of problems with off-by-one fencepost errors. To his credit, the problem originates in the input domain: cities start counting at 1 but arrays start counting at 0.
Here’s some code improvements to help you concentrate on what’s going wrong:
first
In readfile(), why are you opening inpf as a binary stream? You are only reading textual data.
The next thing to think about is the order you choose to initialize the array. Currently, you first read in data then you fill in default values. That’s backwards. Initialize your array before you read in file data.
void readfile()
{
int k, r, c, w;
ifstream inpf( "cyclades.in", ios::in );
// initialize
for (r=0; r < 1000; r++)
for (c=0; c < 1000; c++)
islands[r][c] = INF;
// read from file
inpf >> n >> m;
for (<b>k = 1</b>; k <= m; k++) // notice how we start at 1. also OK: for (k = 0; <b>k < m</b>; k++)
{ // the important point is how many times you loop: <b>m</b> or <b>m+1 </b>?
inpf >> r >> c >> w;
islands[r][c] = w;
islands[c][r] = w;
}
}
This fixes another error: diagonal elements had a weight of zero, and not INF. I know you did that on purpose, so you should think about why I got rid of it.
second
Use this code to output your table.
void displayis()
{
int r, c;
cout << "
array contents" << endl;
// display column number along the top
cout << setw( 3 ) << " ";
for (c = 1; c <= n; c++)
cout << setw( 8 ) << left << c;
cout << endl;
// display the table
for (r = 1; r <= n; r++) {
// display the row number along the left edge of the table
cout << setw( 3 ) << left << r;
// display the table values
for (c = 1; c <= n; c++)
cout << setw( 8 ) << left << islands[ r ][ c ];
cout << endl;
}
cout << endl;
}
Remember, you have an array of 1000 elements, numbered 0 to 999. You can only use 999 of the 1000 elements because you never want to use element 0. Hence, in the above code r and c both start at one. Run your program with this change and you’ll have an easier time visualizing the data in your table. (But seriously, you should have a piece of graph paper with this information drawn on it already, right?)
third
Here’s a couple of other updates, for free. In the first I change your output to display the set contents a bit more compactly (so that you can call it more than once without scrolling your array off the screen). In the second, I have not changed the meaning of your code.
// display the set
void disp_set()
{
cout << "
set contents" << endl;
for (set<int>::iterator p = s.begin(); p != s.end(); p++)
{
cout << *p << " ";
}
cout << endl << endl;
}
// return whether or not 'val' is a member of the set
bool inset(int val)
{
return s.find( val ) != s.end();
}
lastly
This leaves us with the meat of your algorithm, in g(). You have done something nice, and that is use recursion to calculate your total cost. Unfortunately from there you have gotten lost.
Your basic algorithm is (well, you want it to be) this:
- total cost := INF
- if there are no more cities to travel to, return the total cost, plus the cost to return to our initial city.
- otherwise, find the next city I can get to with the least cost
- remove that city from our set of cities
- return the cost to travel to that city + the new total cost (calculated by recursion)
You have an error in step 2 (you are returning the wrong thing --something that doesn’t even exist) and and error in step 3 (you are grabbing the first available city, not the city closest to you). Also, you have forgotten that the trip must be circuitous, and left out the part in italics in step 2.
Finally, in your main function you are multiplying the total cost by four. Don’t do that.:rolleyes:
Hope this helps.
Sorry for the double post, but after that giant last one…
I noticed that you did in fact say that the output should be total cost times four. :o Sorry.
Also, if you use the displayis() code I gave you you’ll have to put the following include at the top of your file:
#include <iomanip>
Have fun now…
Can somebody post a link for a(non genetic) simple tsp algorithm written in java c++ ,basic pascal
ect ?
Your algorithm is almost there. Here’s some code that might make sense.
// g()
// function
// Determine the cost to make a round trip starting at a specific city, using a purely
// greedy method.
// arguments
// first_city The city to start and stop at.
// current_city Used in recursion.
// returns
// The cost of a complete circuit.
//
int g( int first_city, int current_city = -1 )
{
int next_cost = INF; // the smallest cost to the next city
int next_city = -1; // the next city
int j;
// if we are starting out, initialize our set of available cities
if (current_city < 0) {
init_set();
current_city = first_city; // 'current_city' is the same as your original 'i'
s.erase( current_city ); // The first city must be traveled to last
}
// If we've exhausted all other cities, return to the first city
if (s.empty()) return islands[ current_city ][ first_city ];
// Otherwise, find the next city I can get to with the least cost
for (j = 1; j <= n; j++) // (for each city)
if (inset( j )) // (if I haven't already traveled to that city)
{
// You must do this one, sma:
// if the city j has a cost less than 'next_cost' then
// next_cost := j's cost
// next_city := j
}
// Now, if there were no edges to another available city from our
// current city, then 'next_city' will be -1 and 'next_cost' will be
// INF. If this happens, our algorithm failed and we'll have to abort.
// This shouldn't happen given the input you have, but it is possible
// on different input. You may want to think about ways to defeat
// this problem before you even call this function... However in your
// case it shouldn't hurt if you just ignore it.
if (next_city < 0)
{
cout << "Could not compute a circuitous route (though one may be possible)." << endl;
exit( 0 );
}
// Now 'next_cost' should be the smallest cost and 'next_city' should be
// the city with that cost. For functional geeks out there, note the tail recursion :-)
// (What that means, sma, is that you don't need to use recursion if you don't
// want to...)
s.erase( next_city );
return next_cost +g( first_city, next_city );
}
That’s it. Notice how I followed the algorithm. Also, pay close attention to how the total cost is computed in parts:
(A)(for the current city, find the least cost) + (B)(repeat A for the next current city).
This recursive thought is at the heart of functional programming. Essentially, given a list (our list is routes/costs between cities), if you can do something to the first element in the list in relation to the rest of the list, then you can do it for the whole list. In visual terms:
total_cost = g( 1 ) + g( 1, 4 ) + g( 1, 3 ) + g( 1, 6 ) + g( 1, 2 ) + g( 1, 5 ) + g( 1, 1 );
cost:1->4 + (all other costs)
cost:4->3 + (all remaining costs)
cost:3->6 + (all remaining costs)
and so on
Finally, you should use expressive variable names like I have and include enough commentary to follow the code at each major step.
The code so far is a good ‘first guess’ of a branch and bound technique. Also, notice how I put the initial city in the function arguments. This is for two reasons: (1) it provides better encapsulation of data, and (2) you can easily start at a different first city. It is possible to get a smaller cost by starting at a different city.
Hope this helps.
Still having some problems
here is the code:
#include <iostream>
#include <fstream>
#include<set>
using namespace std;
//variables
int INF=1000001;
int n,m;
int islands[1000][1000];
set<int>s;
//function declarations
void readfile();
void displayis();
void init_set();
void disp_set();
bool inset(int val,set<int> d);
int g( int first_city,int current_city);//,int current_city );
//main
int main()
{
readfile();
cout <<n<<' ' <<m<<'
';
displayis();
init_set();
disp_set();
//cout << inset(9)<<'
';
//cout <<"min "<< findmin(1)<<'
';
cout <<"length "<< g(1,-1) * 4 <<'
';
return 0;
}
//reads input file
void readfile()
{
int k, r, c, w;
ifstream inpf( "cyclades2.in", ios::in );
// initialize
for (r=0; r < 1000; r++)
for (c=0; c < 1000; c++)
islands[r][c] = INF;
// read from file
inpf >> n >> m;
for (k = 1; k <= m; k++) // notice how we start at 1. also OK: for (k = 0; k < m; k++)
{ // the important point is how many times you loop: m or m+1 ?
inpf >> r >> c >> w;
islands[r][c] = w;
islands[c][r] = w;
}
}
//displays array contents
void displayis()
{
int r,c;
for (r=1;r<=n;r++)
{
for (c=1;c<=n;c++)
{
cout << r <<" " << c <<" "<< " "<< islands[r][c] << '
';
}
}
}
//initializes set values
void init_set()
{
int r;
for(r=1;r<=n;r++)
{
s.insert(r);
}
}
//displays set contents
void disp_set()
{
for (set<int>::iterator p = s.begin(); p != s.end(); p++)
{
cout << *p << '
';
}
}
//returns true if value exists in set
// return whether or not 'val' is a member of the set
bool inset(int val)
{
return s.find( val ) != s.end();
}
// g()
// function
// Determine the cost to make a round trip starting at a specific city, using a purely
// greedy method.
// arguments
// first_city The city to start and stop at.
// current_city Used in recursion.
// returns
// The cost of a complete circuit.
//
int g( int first_city,int current_city)
{
int next_cost = INF; // the smallest cost to the next city
int next_city = -1; // the next city
int j;
// if we are starting out, initialize our set of available cities
if (current_city < 0) {
init_set();
current_city = first_city; // 'current_city' is the same as your original 'i'
s.erase( current_city ); // The first city must be traveled to last
}
// If we've exhausted all other cities, return to the first city
if (s.empty()) return islands[ current_city ][ first_city ];
// Otherwise, find the next city I can get to with the least cost
for (j = 1; j <= n; j++) // (for each city)
if (inset( j )) // (if I haven't already traveled to that city)
{
// You must do this one, sma:
// if the city j has a cost less than 'next_cost' then
next_cost = j;//'s cost
next_city = j;
}
// Now, if there were no edges to another available city from our
// current city, then 'next_city' will be -1 and 'next_cost' will be
// INF. If this happens, our algorithm failed and we'll have to abort.
// This shouldn't happen given the input you have, but it is possible
// on different input. You may want to think about ways to defeat
// this problem before you even call this function... However in your
// case it shouldn't hurt if you just ignore it.
if (next_city < 0)
{
cout << -1 << endl;
exit( 0 );
}
// Now 'next_cost' should be the smallest cost and 'next_city' should be
// the city with that cost. For functional geeks out there, note the tail recursion :-)
// (What that means, sma, is that you don't need to use recursion if you don't
// want to...)
s.erase( next_city );
return next_cost +g( first_city, next_city );
}
I still get false outputs:
1st input -> output:260
2nd input ->output:220
Well I know that you are propably tired (and bored) working with this (big thanks for the great help again :D)
but still some help would be usefull ! :o
Also notice that because of this declaration I received a strange error message int g( int first_city,int current_city= -1)
so I changed it to
int g( int first_city,int current_city)
and in the main function i called the g function as:
g(1,-1).
I think that this has to do something with the error
The error has to do with the order of things. The prototype (above the main() function) should read
int g( int first_city, int current_city = -1 );
and the function definition should read
int g( int first_city, int current_city )
{
...
}
Default values must be specified with the declaration (or prototype). That way, when the compiler gets to the part where you use the function, it knows what value to plug in, even though it doesn’t know anything else about the function…
I’ve got to go to class right now, but I’ll look it over to see where the error is happening this evening.
[edit]
No, wait. I see the problem right away. Just because the city is an available target doesn’t mean it’s cost is the smallest. Right now you are setting next_city to j every time you go through the loop, so that next_city always winds up being the last available city, regardless of cost.
The next_cost always starts out at infinity. If you find a city with a smaller cost than next_cost, only then do you set it to the new city’s cost. Think about it.
Also, be careful about mixing types of things. While next_city and next_cost are both int, they are not the same type of thing. Think about what the things represent, and how to get a thing’s representation.
For example, you may say that next_city is of type ‘t_city_index’:
typedef int t_city_index;
Now, every place in your code where you need a city index variable, declare it as type t_city_index. For example:
t_city_index j;
You may say that next_cost is of type ‘t_cost’ in like manner. Again, t_city_index and t_cost are two different things, even though in this context they are both declared as int. What if your city distances were given in fractions of km? You would then have to make t_cost a float instead of an int. All you would have to do to make this change is modify the typedef at the beginning of the file, and recompile.
Does this make sense?
Hope this helps.