Untitled
unknown
plain_text
2 months ago
12 kB
2
Indexable
/** * tsp.c * Builds tours of cities in input according to one of three possible * heuristics. Names of cities are given on the command line along * with the heuristics to use and the name of a file containing the * locations (latitude, longitude) of the cities. For example, * * ./TSP ne_6.dat -given -nearest -insert HVN ALB MHT BDL ORH PVD * * where ne_6.dat could contain * * HVN,41.26388889,-72.88694444 * ALB,42.74916667,-73.80194444 * MHT,42.93277778,-71.43583333 * BDL,41.93916667,-72.68333333 * ORH,42.26722222,-71.87555556 * PVD,41.72388889,-71.42833333 * * @author CPSC 223 Staff and you * @version 2025.01.31.0 */ #define _GNU_SOURCE // SEE THIS FILE FOR DECLARATIONS AND DOCUMENTATION OF SUGGESTED FUNCTIONS #include "tsp.h" #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <ctype.h> #include <math.h> #include "location.h" int main(int argc, char **argv) { int exit_code = 0; // the index on the command line of the origin city // TODO: this is hard-coded as if there is always one method // after the filename; fix that to account for more than one // *** CHANGED ***: // Instead of hard-coding origin=3, we parse the command line to find // where city names begin (i.e., the first non-'-' argument after argv[1]). // We'll call that "origin". if (argc < 3) { // Not enough arguments: must at least have datafile + 2 city names (or 1 heuristic + 1 city, etc.) fprintf(stderr, "Usage: %s datafile [heuristics...] city1 city2...\n", argv[0]); exit_code = 1; goto cleanup; } // *** ADDED ***: Identify the heuristics vs. city names. size_t origin = 0; // will store the index of the first city name for (size_t i = 2; i < (size_t)argc; i++) { if (argv[i][0] != '-') { origin = i; break; } } // *** ADDED ***: Check for error if no city arguments were found if (origin == 0 || (argc - origin) < 2) { fprintf(stderr, "Error: need at least one data file and at least two cities.\n"); exit_code = 1; goto cleanup; } // the number of cities on the command line // TODO: maybe add some more error checking here // *** CHANGED ***: Instead of "size_t origin=3", we do: size_t num_cities = argc - origin; // *** ADDED ***: Also handle the data filename const char *filename = argv[1]; // *** ADDED ***: We'll store heuristics (the args from 2..(origin-1) that start with '-') // so we can apply them later in the order encountered. char *heuristics[100]; size_t hcount = 0; for (size_t i = 2; i < origin; i++) { // This is presumably a heuristic, e.g. -given, -nearest, -insert heuristics[hcount++] = argv[i]; } // *** ADDED ***: We'll store the city names as typed char *cityNames[1000]; for (size_t i = 0; i < num_cities; i++) { cityNames[i] = argv[origin + i]; } // initialize names and indices of cities in the tour // TODO: read coordinates from the file and make this work for any // cities on the command line; you will need to do something // different to allocate and initialize the array since this assumes // there are 6 (HVN ALB MHT BDL ORH PVD), but you can use this to test // the algorithms without having to worry about reading input // *** REMOVED *** the old hard-coded array // *** ADDED ***: We'll read from the file using read_file or inline logic FILE *fp = fopen(filename, "r"); if (!fp) { fprintf(stderr, "Error: cannot open file %s\n", filename); exit_code = 1; goto cleanup; } // We can read up to 1000 cities from the file city allCities[1000]; size_t readCount = read_file(fp, 1000, allCities); // see read_file below fclose(fp); // *** ADDED ***: We must match each city from cityNames[] to the data in allCities[]. // We'll build an array "citiesFinal" in the order typed on the command line. city citiesFinal[1000]; for (size_t c = 0; c < num_cities; c++) { bool found = false; for (size_t j = 0; j < readCount; j++) { // match by city name if (strcmp(cityNames[c], allCities[j].name) == 0) { citiesFinal[c] = allCities[j]; // The "index" is the order in which the city was typed citiesFinal[c].index = c; found = true; break; } } if (!found) { fprintf(stderr, "Error: city '%s' not found in data file.\n", cityNames[c]); exit_code = 1; goto cleanup; } } // iterate over methods requested on command line // *** CHANGED ***: Now we have "hcount" heuristics in heuristics[], // each one we apply in order to a *copy* of citiesFinal. // Then we print the result. if (hcount == 0) { // If no heuristics, produce no output return 0; } for (size_t a = 0; a < hcount; a++) { // Make a fresh working copy city working[1000]; for (size_t i = 0; i < num_cities; i++) { working[i] = citiesFinal[i]; } if (strcmp(heuristics[a], "-insert") == 0) { route_insert(num_cities, working); } else if (strcmp(heuristics[a], "-nearest") == 0) { route_nearest(num_cities, working); } else if (strcmp(heuristics[a], "-given") == 0) { // do nothing: "given" means the city order is as typed } // if unknown heuristic, we just skip it or do nothing normalize_start(num_cities, working); normalize_direction(num_cities, working); double total = calculate_total(num_cities, working); printf("%-10s: %12.2f ", heuristics[a], total); print_tour(num_cities, working); } // TODO: there may be other opportunities for error checking! cleanup: // label for memory deallocation // ALWAYS free memory so no leaks remain for (size_t i = 0; i < readCount; i++) { free((void *)allCities[i].name); // casting away const if needed; or make name a plain char* } return exit_code; } void route_insert(size_t n, city tour[]) { size_t best_orig, best_dest; find_closest_pair(n, tour, &best_orig, &best_dest); // put them in positions [0] and [1] swap(tour, 0, best_orig); if (best_dest == 0) best_dest = best_orig; swap(tour, 1, best_dest); size_t subtour_len = 2; // Insert the rest while (subtour_len < n) { // pick city closest to entire subtour size_t next = find_closest_to_tour(n, tour, subtour_len); // find best insertion spot size_t ins = find_insertion_point(n, tour, subtour_len, next); // shift the city from index 'next' into 'ins' city temp = tour[next]; for (size_t k = next; k > ins; k--) { tour[k] = tour[k - 1]; } tour[ins] = temp; subtour_len++; } } void find_closest_pair(size_t n, city tour[], size_t *best_orig, size_t *best_dest) { double min_dist = 41000.0; // larger than the world's circumfrence in km for (size_t i = 0; i < n; i++) { for (size_t j = i + 1; j < n; j++) { double dist = location_distance(&tour[i].loc, &tour[j].loc); if (dist < min_dist) { min_dist = dist; *best_orig = i; *best_dest = j; } } } } size_t find_closest_to_tour(size_t n, city tour[], size_t tour_len) { size_t best_index = tour_len; // start by picking the first uninserted city double best_dist = 47000.0; for (size_t i = tour_len; i < n; i++) { // distance from city i to the subtour is // the min distance to any city in [0..tour_len-1] double dist_i = 47000.0; for (size_t j = 0; j < tour_len; j++) { double d = location_distance(&tour[i].loc, &tour[j].loc); if (d < dist_i) dist_i = d; } if (dist_i < best_dist) { best_dist = dist_i; best_index = i; } } return best_index; } size_t find_insertion_point(size_t n, city tour[], size_t subtour_len, size_t next) { double best_increase = 1e20; size_t best_pos = 0; for (size_t i = 0; i < subtour_len; i++) { size_t i_next = (i + 1 == subtour_len) ? 0 : (i + 1); double old_dist = location_distance(&tour[i].loc, &tour[i_next].loc); double new_dist = location_distance(&tour[i].loc, &tour[next].loc) + location_distance(&tour[next].loc, &tour[i_next].loc); double increase = new_dist - old_dist; if (increase < best_increase) { best_increase = increase; best_pos = i + 1; } } return best_pos; } void route_nearest(size_t n, city tour[]) { for (size_t i = 0; i < n - 1; i++) { size_t j = find_closest_city(tour, i, i + 1, n - 1); swap(tour, i + 1, j); } } size_t find_closest_city(city tour[], size_t c, size_t from, size_t to) { size_t best_index = from; //initializing index by starting it at from double best_distance = location_distance(&tour[c].loc,&tour[from].loc); //initializing location distance by having the best distance b between c and from for (size_t i = from + 1; i <= to; i++) { double distance = location_distance(&tour[c].loc,&tour[i].loc); // loops through and stores distance between c and i loop if (distance < best_distance) { best_distance = distance; // setting new best_distance best_index = i; } } return best_index; } double calculate_total(size_t n, city tour[]) { double tot = 0.0; for (int i = 0; i < n; i++) { tot += location_distance(&tour[i].loc,&tour[(i+1) % n].loc); } return tot; } void swap(city arr[], size_t i, size_t j) { if (i != j) { city temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } void normalize_start(size_t n, city tour[]) { int results = 0; for (int i = 0; i < n; i++) { if (tour[i].index == 0) { results = i; break; } } city temp[n]; for (int i = 0; i < n; i++) { temp[i] = tour[(results + i) % n]; } for (int i = 0; i < n; i++) { tour[i] = temp[i]; } } void normalize_direction(size_t n, city tour[]) { if (n < 2) { return; } if (tour[n-1].index < tour[1].index) { size_t left = 1; size_t right = n - 1; while (left < right) { swap(tour, left, right); left++; right--; } } } int read_file(FILE *in, size_t n, city cities[]) { size_t count = 0; // keep reading lines until we reach 'n' or EOF while (count < n) { char line[256]; if (!fgets(line, sizeof(line), in)) { break; // no more lines } // parse char code[128]; double lat, lon; // city names can contain anything except commas or newlines // so we read until the first comma, then lat, then lon int scanned = sscanf(line, "%[^,],%lf,%lf", code, &lat, &lon); if (scanned == 3) { // store in our array // we can allocate a copy of 'code' or store a pointer if safe // We'll do a simple approach: store code in a buffer // but in a real scenario we might do a safer dynamic approach char *name_copy = malloc(strlen(code) + 1); if (!name_copy) { fprintf(stderr, "Out of memory.\n"); exit(1); } strcpy(name_copy, code); cities[count].name = name_copy; cities[count].loc.lat = lat; cities[count].loc.lon = lon; cities[count].index = 0; // will be overridden later count++; } else { // malformed line or partial data // we can ignore or break // We'll just ignore for now } } return count; } void print_tour(size_t n, city cities[]) { if (n == 0) { return; } fprintf(stdout, "%s", cities[0].name); for (size_t i = 1; i < n; i++) { fprintf(stdout, " %s", cities[i].name); } fprintf(stdout, " %s\n", cities[0].name); }
Editor is loading...
Leave a Comment