Background : Finding the lowest cost path through a graph is a common challenge
ID: 3793158 • Letter: B
Question
Background: Finding the lowest cost path through a graph is a common challenge in many applications. While it can be an expensive process in general, often constraints of the graph structure simplify the search. In this project, we’ll examine exiting a diamond grid (shown tilted 45 degrees counterclockwise below). The weights between points are randomly generated integers between -99 and 99, inclusive. Non-participating array cells (the padding) have weights set to 10,000. Note that the linearized array offset is shown in blue in each square. The goal is to find the minimum cost path between the center and any exit edge where cost is the sum of all weights encountered along the path. All paths must have a length of five squares not counting the center square. The problem is considerably more difficult if this path requirement is relaxed. Strategy: Unlike many “function only” programming tasks where a solution can be quickly envisioned and implemented, this task requires a different strategy. Before writing any code, reflect on the task requirements and constraints. Mentally explore different approaches and algorithms, considering their potential performance and costs. The metrics of merit are static code length, dynamic execution time, and storage requirements. There are often trade offs between these parameters. Sometimes back of the envelope calculations (e.g., how many comparisons will be performed) can help illuminate the potential of an approach.
/* D i a m o n d S e a r c h
Student Name:
Date:
ECE 2035 Project 1-1
This program finds the shortest path out of a diamond of weighted squares. */
#include <stdio.h>
#include <stdlib.h>
/* Example from Project description:
int Array[121] = {
10000, 10000, 10000, 10000, 10000, -99, 10000, 10000, 10000, 10000, 10000,
10000, 10000, 10000, 10000, -49, -37, 83, 10000, 10000, 10000, 10000,
10000, 10000, 10000, -64, 19, 67, -82, -2, 10000, 10000, 10000,
10000, 10000, -30, -37, 64, -68, 92, 40, 2, 10000, 10000,
10000, 27, -70, 52, 79, -77, -31, -41, -77, -81, 10000,
80, -73, -8, -59, 53, 0, -47, 46, -32, 98, -98,
10000, 13, -99, -47, -60, -14, -45, 80, 15, 69, 10000,
10000, 10000, -9, 8, -88, 69, 54, 12, 53, 10000, 10000,
10000, 10000, 10000, -21, 3, -61, -43, 29, 10000, 10000, 10000,
10000, 10000, 10000, 10000, 45, -34, -85, 10000, 10000, 10000, 10000,
10000, 10000, 10000, 10000, 10000, 59, 10000, 10000, 10000, 10000, 10000 };
*/
#define ArraySize 121
int main(int argc, char *argv[]) {
int Array[ArraySize];
int Length, MinCost = 10000;
int Load_Mem(char *, int *);
if (argc != 2) {
printf("usage: P1-1 valuefile ");
exit(1);
}
Length = Load_Mem(argv[1], Array);
if (Length != ArraySize) {
printf("valuefile does not contain valid data. ");
exit(1);
}
/* Your diamond search code goes here */
/* This routine loads in up to ArraySize newline delimited integers from
a named file in the local directory. The values are placed in the
passed integer array. The number of input integers is returned. */
int Load_Mem(char *InputFileName, int IntArray[]) {
int N, Addr, Value, NumVals;
FILE *FP;
FP = fopen(InputFileName, "r");
if (FP == NULL) {
printf("%s could not be opened; check the filename ", InputFileName);
return 0;
} else {
for (N=0; N < ArraySize; N++) {
NumVals = fscanf(FP, "%d: %d", &Addr, &Value);
if (NumVals == 2)
IntArray[N] = Value;
else
break;
}
fclose(FP);
return N;
}
}
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
int Array[121] = {
10000, 10000, 10000, 10000, 10000, -99, 10000, 10000, 10000, 10000, 10000,
10000, 10000, 10000, 10000, -49, -37, 83, 10000, 10000, 10000, 10000,
10000, 10000, 10000, -64, 19, 67, -82, -2, 10000, 10000, 10000,
10000, 10000, -30, -37, 64, -68, 92, 40, 2, 10000, 10000,
10000, 27, -70, 52, 79, -77, -31, -41, -77, -81, 10000,
80, -73, -8, -59, 53, 0, -47, 46, -32, 98, -98,
10000, 13, -99, -47, -60, -14, -45, 80, 15, 69, 10000,
10000, 10000, -9, 8, -88, 69, 54, 12, 53, 10000, 10000,
10000, 10000, 10000, -21, 3, -61, -43, 29, 10000, 10000, 10000,
10000, 10000, 10000, 10000, 45, -34, -85, 10000, 10000, 10000, 10000,
10000, 10000, 10000, 10000, 10000, 59, 10000, 10000, 10000, 10000, 10000 };
*/
#define ArraySize 121
int main(int argc, char *argv[]) {
int Array[ArraySize];
int Length, MinCost = 10000;
int Load_Mem(char *, int *);
if (argc != 2) {
printf("usage: P1-1 valuefile ");
exit(1);
}
Length = Load_Mem(argv[1], Array);
if (Length != ArraySize) {
printf("valuefile does not contain valid data. ");
exit(1);
}
/* Your diamond search code goes here */
/* This routine loads in up to ArraySize newline delimited integers from
a named file in the local directory. The values are placed in the
passed integer array. The number of input integers is returned. */
int Load_Mem(char *InputFileName, int IntArray[]) {
int N, Addr, Value, NumVals;
FILE *FP;
FP = fopen(InputFileName, "r");
if (FP == NULL) {
printf("%s could not be opened; check the filename ", InputFileName);
return 0;
} else {
for (N=0; N < ArraySize; N++) {
NumVals = fscanf(FP, "%d: %d", &Addr, &Value);
if (NumVals == 2)
IntArray[N] = Value;
else
break;
}
fclose(FP);
return N;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.