我正在运行此代码,并收到此错误
Fatal glibc error: malloc.c:2593 (sysmalloc): assertion failed: (old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)
Aborted (core dumped)
当我使用gdb运行它时,它是这样的:
Fatal glibc error: malloc.c:2593 (sysmalloc): assertion failed: (old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)
Program received signal SIGABRT, Aborted.
__pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0) at pthread_kill.c:44
44 return INTERNAL_SYSCALL_ERROR_P (ret) ? INTERNAL_SYSCALL_ERRNO (ret) : 0;
我不知道为什么。请帮帮我。
代码:
#include <bits/stdc++.h>
using namespace std;
bool cancolor(vector<vector<int>> &mat, int m, vector<int> colors, int idx)
{
if (idx == mat.size())
{
return true;
}
else
{
int color = 1;
while (color <= m)
{
int edges = 0;
int i = 0;
while (i < mat.size())
{
if (mat[idx][i] == 1)
{
edges++;
if (colors[i] != color)
{
colors[idx] = color;
if (cancolor(mat, m, colors, idx + 1))
{
return true;
}
colors[idx] = 0;
}
else
{
i = mat.size();
}
}
i++;
}
if (edges == 0)
{
colors[idx] = color;
if (cancolor(mat, m, colors, idx + 1))
{
return true;
}
return false;
}
color++;
}
return false;
}
}
string graphColoring(vector<vector<int>> &mat, int m)
{
vector<int> colors;
for (int i = 0; i <= m; i++)
{
colors.push_back(0);
}
if (cancolor(mat, m, colors, 0))
{
return "YES";
}
return "NO";
}
int main()
{
vector<vector<int>> mat = {{0, 0, 0, 1, 0, 0, 0},
{0, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0}};
cout << graphColoring(mat, 5) << endl;
return 0;
}
如果你想知道我想达到什么目的,这里有链接:https://www.codingninjas.com/codestudio/problems/981273
我试着用pythontutor运行它,但它在174步左右后结束了,在第5个节点后。
2条答案
按热度按时间xlpyo6sf1#
问题出在
graphColoring
;m
是颜色的数量,但是colors
矢量应该包含mat.size()
元素。在这个向量之外写入(如您所做的)具有未定义的行为,并且可能导致某种类型的内存崩溃。
w8biq8rn2#
你所得到的是一个指数级的爆炸,对于每个
idx
,你会快速地调用cancolor()
很多次,对于每个调用,又会进行很多次递归调用,如此类推。您通常会遇到堆栈溢出,但是您对动态分配内存的使用(可能来自
std::vector<int> colors
)使我认为空闲存储区首先爆炸。你应该重新考虑你的算法如果这是不可能,尝试和线性化,以减少您的内存需求。
另外,
using namsepace std
和#include <bits/stdc++.h>
被认为是有害的。我让你搜索一下。