标签: np-hard

NP,NP-Complete和NP-Hard有什么区别？

我知道网上有很多资源.我想阅读你的解释,原因是它们可能与那些不同,或者有些东西我不知道.

让我们说我有抛物线.现在我也有一堆宽度相同的棒(是的,我的绘画技巧太棒了!).如何在抛物线内堆叠这些木棍,以便尽可能减少其使用的空间？我认为这属于背包问题类别,但这个维基百科页面似乎并没有让我更接近现实世界的解决方案.这是NP-Hard问题吗？

在这个问题中,我们试图最小化消耗的区域量(例如:积分),其中包括垂直区域.

我面临着一个三维装箱问题,目前正在进行一些初步研究,以确定哪些算法/启发式方法目前正在产生最佳结果.由于问题是NP难,我不希望在每种情况下找到最佳解决方案,但我想知道:

1)什么是最精确的求解器？分支和绑定？我可以通过合理的计算资源解决哪些问题实例大小？
2)什么是最好的启发式求解器？
3)进行一些实验有哪些现成的解决方案？

我想知道TSP没有问题的名称是什么,考虑回到起点的方式以及解决这个问题的算法是什么.

我查看了最短路径问题,但这不是我想要的,问题只能找到2个指定点的最短路径.但我正在寻找的是我们给出n分并仅输入1个起点的问题.然后,找到所有点正好行进一次的最短路径.(终点可以是任何一点.)

我也研究了汉密尔顿路径问题,但似乎没有解决我定义的问题,而是找出是否存在汉密尔顿路径.

请指教我,谢谢!

这是我长期以来一直存在的问题.作为一名教师和程序员的儿子,我很早就想到了......但我仍然没有找到解决方案.

所以这就是问题所在.人们需要使用一些约束为学校创建时间表.这些通常分为两类:

理智检查

• 老师不能同时教两门课
• 学生不能同时学习两节课
• 一些教师必须在一周内至少休息一天
• 时间表应涵盖一周中的所有日期
• 受试者X每周必须完全正常
• ...

喜好

• 每位教师的日程安排应尽可能紧凑(即教师应该连续一天工作,如果可能的话,没有暂停)
• 休息日的教师应该能够在哪一天表达偏好
• 从事兼职工作的教师应该能够表达是否在学校开始或结束时工作的偏好.
• ...

现在,经过几年没有找到解决方案(同时学习一两件事),我意识到这就像一个NP难的问题.

它被证明是NP难吗？

有没有人知道如何破解这个东西？

看看这个问题让我想到了这个问题,以及在这种情况下遗传算法是否可用.然而,在保持理智检查规则的同时,很难改变可能性.我还不清楚如何区分不兼容的要求.

一个小的附录,以更好地说明问题.这适用于意大利学校风格的教室,所有学生都在不同的班级(例如:第1年A部分),教师在不同课程之间移动.同一班级的所有学生都有相同的时间表,并且无法选择参加哪些课程.

我在NP Completeness的背景下在大学里学习过TSP.我实际上从未遇到过适用于实际问题的情况.一些研究表明,它已被用来选择最便宜的移动钻头的路径,即在电路板上钻孔.这几乎是我所能找到的.

你在用它吗？TSA还有哪些其他实际应用？

我需要编写一个程序(大学项目)来解决(近似)NP难题.它是线性排序问题的变体.一般来说,我将有非常大的输入(如图形),并将尝试找到最佳解决方案(基于一个"评价"每个解决方案的功能)

如果我用C风格的代码(一个main和函数)编写它,或构建一个Solver类,创建一个实例并从main调用一个'run'方法(类似于Java),会有区别吗

此外,每次迭代都会有很多浮点运算.

谢谢!

对于不可判断的问题和NP难题之间的关系,我有点困惑.NP难题是否是不可判定问题的一个子集,或者它们是否相同且相同,还是它们不具有可比性？

对我而言,我一直在与朋友争辩说,不可判断的问题是NP难题的超集.存在一些不是NP难以解决的问题但是不可判定的问题.但我发现这个论点很弱,而且有点困惑.是否存在不完全的NP完全问题.在NP hard中有任何问题是可判定的吗？

一些讨论会有很大的帮助!谢谢!

编写一个程序来找到最大可能的字母矩形,这样每行形成一个单词(从左到右),每一列形成一个单词(从上到下).

我发现了这个有趣的问题.这不是家庭作业,尽管听起来可能如此.(我不在学校).我这样做是为了好玩.

例

从cat,car,ape,api,rep,tip我们得到以下矩形(这是一个正方形):

c a r
a p e
t i p

Run Code Online (Sandbox Code Playgroud)

我最初的想法是构建一种前缀树,以便我可以检索以特定字符串开头的所有单词.当我们已经有2个或更多单词(从上到下或从左到右阅读)并且我们需要找到要添加的下一个单词时,这将非常有用.

还有其他想法吗？

编辑

这可以用长方体(3D矩形)来完成吗？

如果它需要在对角线上有有效的单词怎么办(想法信用:user645466); 如何优化它的算法？

给定二进制矩阵(值为0或1),相邻的1表示"丘陵".另外,给定一些数字k,找到你需要"翻转"为1的最小数量0,以便形成至少大小的山丘k.

编辑:为了澄清,相邻意味着左右上下社区.对角线也不能算作相邻.例如,

[0 1 0 1]

是一个2号山,

[0 1 1 0]

定义2个大小为1的山丘,

[0 1 1 1]

定义1个大小为3的小山,和

[1 1 1 1]

定义1个4号山.

同样为了澄清,尺寸由相邻的1的斑点形成的区域定义.

我的初始解决方案涉及将每个现有的山变换为图的节点,并将成本作为到达每个其他节点的最小路径.然后,执行DFS(或类似算法)以找到最低成本.

如果选择某条路径可以降低另一条边的成本,那么就会失败,而解决这个问题的解决方案(我能想到的)与蛮力解决方案太接近了.