1 Discussion slides for week of November 26, 2007 The University of Michigan2 Agenda z Any Questions? z HW4 (Due coming Tuesday) z PA3 Questions/discussion z Last time − Branch & Bound • Today − Input parsing, “tokenizing” − PA3 review (BnB) − 2-approximation − k-Optimization, getrusage − Anytime algorithms :z This is a pain, especially for complex formats z You’ve already done this for PA1; much of your solution should translate to PA3 z A very common problem is extracting chunks of information from a delimited string − “Tokenizing” a string − Extract ints from “1 2 3 40 5 12” or “1,2,3,40,5,12” 3 Parsing Input :z The C strtok() function char str[] = “1,2,3,40,5,12” ; char *tmp; printf ("Splitting string \"%s\" into tokens:\n",str); tmp = strtok (str,","); while (tmp != NULL) { printf ("%s\n",tmp); tmp = strtok (NULL, ","); } 4 Options for Tokenizing :z Use string library functions string tmp; string delims = “ ,”; int j = 0; int i = s.find_first_not_of(delims,j); while (i != string::npos) { j = s.find(delims, i); tmp = s.substr(i, j-i); I = s.find_first_not_of(delims,j); // process tmp } 5 Options for Tokenizing :z Use the iostream get/getline functionality istream& getline (char* s, streamsize n, char delim ); z For example: char delim = ‘,’; char buf[256]; ifstream file(“in.txt”); while (file.good()) { file.getline(buf, 256, delim); // process token (stored in buf) } 6 Options for Tokenizing :z Use a stringstream (if the tokens are spaces) int i; stringstream a(“1 2 3 40 5 12”) while (a>>i) { // process i } 7 Options for Tokenizing :8910111213PA3 – k-Approximation : 15 z From professor’s lecture notes: − Start with an initial tour, e.g., the randomly generated one or the MST − Consider two cities vi and vi+1 or any two cities u and v − Check if visiting vi+1 before visiting vi decreases total tour length − Repeat with different vi until there is no further improvement (or up to time limit) z Time limit of 60 seconds! z You must use getrusage(2) to determine both the elapsed time and time remaining z Use the timing information provided by this function to help regulate your heuristics and algorithms.double getcputime(void) { struct timeval tmpTime; struct rusage ru; getrusage(RUSAGE_SELF, &ru); tmpTime = ru.ru_utime; double t = (double)tim.tv_sec + (double)tim.tv_usec / 1000000.0; tim = ru.ru_stime; t += (double)tim.tv_sec + (double)tim.tv_usec / 1000000.0; return t; } 16 getrusage :z In many applications, we need *an* answer, even if it is not the best answer − Available time may be unknown − Solution times can vary widely for different instances z We want an algorithm that will always return the best answer it can, given the time we allow it − “Real time” or “anytime” computation Anytime algorithms : 17Time Quality Optimal value 18 Solution Quality :z For PA3, you must return the best solution you can on 60 seconds. How could you approach this? 19 PA3 Anytime Algorithm :z Always store the best known solution to return when time is up (and for use as a bound) z First, compute quick solutions that may not be very good − Random − Heuristic solution (e.g. greedy) − 2-approximation z Local search for improvements (k-opt) z Compute the optimal solution (BnB) 20 General Strategy :That’s it for today! Any questions? 21