Я пытаюсь написать решатель для конкретной головоломки. Он пытается найти решение, пробуя все возможные движения по одному, пока не найдет решение. Первая версия попыталась разрешить ее глубину - сначала, постоянно пытаясь двигаться до тех пор, пока она не сработает, а затем отступит, но это оказалось слишком медленным. Я переписал его на ширину, сначала используя структуру очереди, но у меня проблемы с управлением памятью.Запуск памяти .. Как?
Вот соответствующие части:
int main(int argc, char *argv[])
{
...
int solved = 0;
do {
solved = solver(queue);
} while (!solved && !pblListIsEmpty(queue));
...
}
int solver(PblList *queue) {
state_t *state = (state_t *) pblListPoll(queue);
if (is_solution(state->pucks)) {
print_solution(state);
return 1;
}
state_t *state_cp;
puck new_location;
for (int p = 0; p < puck_count; p++) {
for (dir i = NORTH; i <= WEST; i++) {
if (!rules(state->pucks, p, i)) continue;
new_location = in_dir(state->pucks, p, i);
if (new_location.x != -1) {
state_cp = (state_t *) malloc(sizeof(state_t));
state_cp->move.from = state->pucks[p];
state_cp->move.direction = i;
state_cp->prev = state;
state_cp->pucks = (puck *) malloc (puck_count * sizeof(puck));
memcpy(state_cp->pucks, state->pucks, puck_count * sizeof(puck)); /*CRASH*/
state_cp->pucks[p] = new_location;
pblListPush(queue, state_cp);
}
}
}
free(state->pucks);
return 0;
}
Когда я запускаю его я получаю сообщение об ошибке:
ice(90175) malloc: *** mmap(size=2097152) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
Bus error
ошибка происходит вокруг итерации 93000. Из того, что я могу сказать, сообщение об ошибке происходит от сбоя malloc, а ошибка шины - из memcpy после него.
Мне трудно поверить, что у меня заканчивается память, так как каждое состояние игры составляет всего ~ 400 байт. Тем не менее, похоже, это то, что происходит, поскольку монитор активности сообщает, что он использует 3,99 ГБ, прежде чем он сработает. Я использую http://www.mission-base.com/peter/source/ для структуры очереди (это связанный список).
Очевидно, я делаю что-то немое. Какие-либо предложения?
Вы противоречите себе тремя способами. 1. 400 байт, 2. 3.99GB, 3. 93000 * puck_count * sizeof (шайба) распределения (это чертовски больше 400 байт). Какое поведение вы наблюдаете на самом деле? Забываете ли вы «освободить» память, когда закончите с ней? –
каждое состояние игры составляет около 400 байт, но он делает много копий, видимо, достаточно, чтобы заполнить 4 гигабайта. Я не освобождаю всю прежнюю память (я освобождаю старые шайбы-массивы, но это все), но это потому, что мне нужно, чтобы отслеживать шаги, предпринятые до сих пор. – maxdj
@maxdj: Тогда как вы объясните противоречие №3? –