C - Beräkna djup på Stack
Hej, går en kurs i datavetenskap och nu ska vi analysera rumskomplexiteten för DFS i en stack. Vi fick färdig kod där vi bara skulle implementera en funktion (stack_get_max_size). Jag tolkade stackens djup som detsamma som max antal element i stacken. Jag har dock gjort fel någonstans för enligt handledare ska stackens djup inte överstiga 50, medans jag får antalet element att överstiga 500k i slutet.
Given kod:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "search.h"
/* INTERFACE (STACK) */
typedef struct stack
{
int capacity;
int size;
State *data;
} Stack;
Stack *stack_create(void);
void stack_destroy(Stack *s);
void stack_push(Stack *s, State value);
State stack_pop(Stack *s);
bool stack_is_empty(const Stack *s);
int stack_get_max_size(const Stack *s);
/* IMPLEMENTATION (STACK) */
Stack *stack_create(void)
{
Stack *s = malloc(sizeof(Stack));
s->capacity = 1024;
s->size = 0;
s->data = malloc(sizeof(State) * s->capacity);
return s;
}
void stack_destroy(Stack *s)
{
free(s->data);
free(s);
}
void stack_push(Stack *s, State value)
{
if (s->size == s->capacity) {
s->capacity *= 2;
s->data = realloc(s->data, sizeof(State) * s->capacity);
}
s->data[s->size++] = value;
}
State stack_pop(Stack *s)
{
return s->data[--s->size];
}
bool stack_is_empty(const Stack *s)
{
return s->size == 0;
}
int stack_get_max_size(const Stack *s)
{
/* TODO: IMPLEMENT */
/* Return the largest size that the stack has ever been. */
return -1;
}
/* IMPLEMENTATION (DFS) */
struct dfs_data {
Stack *stack;
};
void dfs_push_state(void *data, State S)
{
struct dfs_data *p = data;
stack_push(p->stack, S);
}
State dfs_pop_state(void *data)
{
struct dfs_data *p = data;
return stack_pop(p->stack);
}
bool dfs_empty_state(void *data)
{
struct dfs_data *p = data;
return stack_is_empty(p->stack);
}
int dfs_max_size(void *data)
{
struct dfs_data *p = data;
return stack_get_max_size(p->stack);
}
void dfs_search(State start, int max_depth)
{
struct dfs_data data = { stack_create() };
generic_search(start, max_depth, dfs_push_state, dfs_pop_state, dfs_empty_state, dfs_max_size, &data);
stack_destroy(data.stack);
}
/* MAIN */
int main(void)
{
printf("EXPERIMENT PÅ STACK\n");
printf("======================================================================\n\n");
printf("Det här programmet mäter hur mycket minne som algoritmen DFS behöver\n"
"för att räkna antalet lösningar till instanser av 15-pusslet. Det\n"
"maximala antalet förflyttningar varieras mellan 1 och 15. Instanserna\n"
"är skapade så att de går att lösa. Resultaten skrivs ut i textformat\n"
"till stdout med tab-separerade kolumner. Tiden mäts i sekunder. Minnet\n"
"mäts i antal element i stacken.\n");
printf("\n");
printf("RESULTAT\n");
printf("======================================================================\n\n");
printf("%4s\t%10s\t%13s\t%13s\t%12s\n", "max", "tid", "tillstånd", "lösningar", "minne");
for (int max_depth = 1; max_depth <= 15; max_depth++) {
srand(max_depth);
State start = goal_state();
random_moves(&start, max_depth);
dfs_search(start, max_depth);
}
}
För att implementera stack_get_max_size la jag till int max_size i stackens struct, ökade sedan denna varje gång ett element pushades till stacken och returnerar detta värde i stack_get_max_size. Ändringarna visas nedan i fet stil:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "search.h"
/* INTERFACE (STACK) */
typedef struct stack
{
int capacity;
int size;
State *data;
} Stack;
Stack *stack_create(void);
void stack_destroy(Stack *s);
void stack_push(Stack *s, State value);
State stack_pop(Stack *s);
bool stack_is_empty(const Stack *s);
int stack_get_max_size(const Stack *s);
/* IMPLEMENTATION (STACK) */
Stack *stack_create(void)
{
Stack *s = malloc(sizeof(Stack));
s->capacity = 1024;
s->size = 0;
s->max_size = s->size;
s->data = malloc(sizeof(State) * s->capacity);
return s;
}
void stack_destroy(Stack *s)
{
free(s->data);
free(s);
}
void stack_push(Stack *s, State value)
{
if (s->size == s->capacity) {
s->capacity *= 2;
s->data = realloc(s->data, sizeof(State) * s->capacity);
}
s->data[s->size++] = value;
s->max_size++;
}
State stack_pop(Stack *s)
{
return s->data[--s->size];
}
bool stack_is_empty(const Stack *s)
{
return s->size == 0;
}
int stack_get_max_size(const Stack *s)
{
/* TODO: IMPLEMENT */
/* Return the largest size that the stack has ever been. */
return s->max_size;
}
/* IMPLEMENTATION (DFS) */
struct dfs_data {
Stack *stack;
};
void dfs_push_state(void *data, State S)
{
struct dfs_data *p = data;
stack_push(p->stack, S);
}
State dfs_pop_state(void *data)
{
struct dfs_data *p = data;
return stack_pop(p->stack);
}
bool dfs_empty_state(void *data)
{
struct dfs_data *p = data;
return stack_is_empty(p->stack);
}
int dfs_max_size(void *data)
{
struct dfs_data *p = data;
return stack_get_max_size(p->stack);
}
void dfs_search(State start, int max_depth)
{
struct dfs_data data = { stack_create() };
generic_search(start, max_depth, dfs_push_state, dfs_pop_state, dfs_empty_state, dfs_max_size, &data);
stack_destroy(data.stack);
}
/* MAIN */
int main(void)
{
printf("EXPERIMENT PÅ STACK\n");
printf("======================================================================\n\n");
printf("Det här programmet mäter hur mycket minne som algoritmen DFS behöver\n"
"för att räkna antalet lösningar till instanser av 15-pusslet. Det\n"
"maximala antalet förflyttningar varieras mellan 1 och 15. Instanserna\n"
"är skapade så att de går att lösa. Resultaten skrivs ut i textformat\n"
"till stdout med tab-separerade kolumner. Tiden mäts i sekunder. Minnet\n"
"mäts i antal element i stacken.\n");
printf("\n");
printf("RESULTAT\n");
printf("======================================================================\n\n");
printf("%4s\t%10s\t%13s\t%13s\t%12s\n", "max", "tid", "tillstånd", "lösningar", "minne");
for (int max_depth = 1; max_depth <= 15; max_depth++) {
srand(max_depth);
State start = goal_state();
random_moves(&start, max_depth);
dfs_search(start, max_depth);
}
}
Det jag undrar över är om jag gjort fel när jag implementerar stack_get_max_size eller tolkar jag hela uppgiften fel?
Dessa filer behövs för att kompilera programmet, men jag har ej ändrat något i dem utan vi fick dom färdiga.
search.c:
[code]#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include "search.h"
/* Return the current time in seconds with high precision. */
static double get_time(void)
{
struct timeval tv;
gettimeofday(&tv, 0); /* Defined in POSIX (not standard C). */
return tv.tv_sec + tv.tv_usec * 1e-6;
}
State goal_state(void)
{
State S = { { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 }, 15, 0 };
return S;
}
static bool is_goal_state(const State *S)
{
for (int k = 0; k < 15; k++) {
if (S->cells[k] != k + 1) {
return false;
}
}
return true;
}
static int adjacent_states(const State *S, State adj[4])
{
int n = 0;
const int offsets[4] = { -1, +1, -4, +4 };
const int empty = S->empty;
for (int d = 0; d < 4; d++) {
const int index = empty + offsets[d];
if (offsets[d] == -1 || offsets[d] == +1) {
if (index / 4 != empty / 4) {
continue;
}
}
if (index >= 0 && index <= 15) {
State T = *S;
T.cells[empty] = T.cells[index];
T.cells[index] = 0;
T.empty = index;
T.depth += 1;
adj[n++] = T;
}
}
return n;
}
void random_moves(State *S, int n)
{
State adj[4];
for (int k = 0; k < n; k++) {
int num = adjacent_states(S, adj);
int index = rand() % num;
*S = adj[index];
}
S->depth -= n;
}
#if 0
static void print_state(const State *S)
{
for (int row = 0; row < 4; row++) {
for (int col = 0; col < 4; col++) {
int k = 4 * row + col;
char c = S->cells[k];
if (c == 0) {
printf(" . ");
} else {
printf("%2d ", c);
}
}
printf("\n");
}
printf("\n");
}
#endif
void generic_search(State start, int max_depth, push_state_fn push, pop_state_fn pop, empty_state_fn empty, max_size_state_fn max_size, void *data)
{
int states = 1;
int solutions = 0;
double T = get_time();
push(data, start);
while (!empty(data)) {
State S = pop(data);
if (is_goal_state(&S)) {
solutions++;
}
if (S.depth < max_depth) {
State adj[4];
int n = adjacent_states(&S, adj);
for (int k = 0; k < n; k++) {
push(data, adj[k]);
states++;
}
}
}
T = get_time() - T;
printf("%4d\t%10.6lf\t%12d\t%12d\t%12d\n", max_depth, T, states, solutions, max_size(data));
}
[/code)
search.h:
#ifndef SEARCH_H
#define SEARCH_H
#include <stdbool.h>
typedef struct state {
char cells[16];
char empty;
char depth;
} State;
typedef void (*push_state_fn)(void *data, State S);
typedef State (*pop_state_fn)(void *data);
typedef bool (*empty_state_fn)(void *data);
typedef int (*max_size_state_fn)(void *data);
State goal_state(void);
void random_moves(State *S, int n);
void generic_search(State start, int max_depth, push_state_fn push, pop_state_fn pop, empty_state_fn empty, max_size_state_fn max_size, void *data);
#endif
