我正在开发一种应用程序,可以最佳地为医院的护士分配班次.我认为这是一个带离散变量的线性规划问题,因此可能是NP难的:
因此,基本上存在大量(约20*30 = 600)变量,每个变量可以采用少量离散值.
目前,我的计划是使用修改后的Min-conflicts算法
有更好的想法吗？我有点担心它会陷入局部最佳状态.我应该使用某种形式的模拟退火吗？或者不仅考虑一次改变一个变量,而且特别考虑两个人之间的转换(当前手动算法中的主要部分)？我想避免将算法定制到当前约束,因为那些可能会改变.
编辑:没有必要找到严格的最佳解决方案; 名单目前是手工完成的,我很确定结果在大多数时候都是非常不理想的 - 不应该难以击败.短期调整和手动覆盖也一定是必要的,但我不认为这是一个问题; 将过去和手动分配标记为"已修复"实际上应该通过减少解决方案空间来简化任务.
algorithm mathematical-optimization linear-programming discrete-mathematics
我试图更好地理解在编程中如何使用离散数学概念(例如集合论).
我熟悉高中数学,对离散数学中使用的术语和概念有基本的了解
我理解像Haskell,Lisp,Ruby,Perl和所有基于C语言的语言.
我试图解决一个更大的问题,我认为该程序的一个重要部分是花在低效计算上.
我需要计算给定数N,区间[P,Q],其中P是<=到N的最大斐波纳契数,而Q是> =到N的最小斐波纳契数.
目前,我正在使用地图来记录斐波纳契数的值.查询通常涉及搜索最多为N的所有斐波纳契数,并且它不是非常节省时间,因为它涉及大量的比较.
这种类型的查询将在我的程序中经常出现,我对可以改进查找的方式感兴趣,最好是使用子线性复杂性.
我正在努力有效地解决SPOJ问题64:排列.
设A = [a1,a2,...,an]是整数1,2,...,n的排列.如果ai> aj,则一对索引(i,j),1 <= i <= j <= n,是置换A的反转.我们给出整数n> 0和k> = 0.包含正好k次反转的n元素排列的数量是多少？
例如,恰好1次反转的4元素排列的数量等于3.
为了使给定的示例更容易看到,这里有三个4元素排列,正好有1个反转:
(1, 2, 4, 3)
(1, 3, 2, 4)
(2, 1, 3, 4)
在第一个排列中,4> 3且指数4小于3的指数.这是单个反转.由于置换只有一次反转,因此它是我们试图计算的排列之一.
对于任何给定的n个元素序列,排列的数量是阶乘(n).因此,如果我使用强力n 2方法计算每个排列的反转次数,然后检查它们是否等于k,则该问题的解决方案将具有时间复杂度O(n!*n 2).
这个问题的一个子问题以前问这里在计算器上.给出了使用合并排序的O(n log n)解决方案,其计算单个排列中的反转次数.但是,如果我使用该解决方案来计算每个排列的反转次数,我仍然会得到O(n!*n log n)的时间复杂度,在我看来这仍然很高.
之前在Stack Overflow上也提到了这个确切的问题,但它没有收到任何答案.
如果没有数学公式来解决这个问题(我有点怀疑),那么我也看到人们提示有效的动态编程解决方案是可能的.使用DP或其他方法,我真的想制定一个比O(n!*n log n)更有效的解决方案,但我不确定从哪里开始.
欢迎任何提示,评论或建议.
编辑:我已经用DP方法回答了下面的问题来计算Mahonian数.
algorithm permutation dynamic-programming combinatorics discrete-mathematics
x衍生Sobel就是这样的:
-1 0 +1
-2 0 +2
-1 0 +1
假设我的图像中有两个样本看起来像那样(0 =黑色,1 =白色):
0 0 1 1 0 0
0 0 1 & 1 0 0
0 0 1 1 0 0
如果我执行卷积,我将分别以4和-4结束.
所以我的自然反应是将结果标准化为8并将其翻译为0.5 - 这是正确的吗？(我想知道找不到维基百科等提及任何规范化)
编辑: 我使用Sobel滤镜创建2D结构张量(衍生物dX和dY):
A B
Structure Tensor = C D
with A = dx^2
B = dx*dy
C = dx*dy
D = dy^2
最后我想将结果存储在[0,1]中,但是现在我只是想知道我是否必须规范化Sobel结果(默认情况下,不仅仅是为了存储它),即:
A = dx*dx
//OR
A = (dx/8.0)*(dx/8.0)
//OR
A = (dx/8.0+0.5)*(dx/8.0+0.5)
我不理解连续子序列的以下定义:
列表S的连续子序列是由S的连续元素组成的子序列.
如果S
{5, 15, -30, 10, -5, 40, 10}
则15, -30, 10是一个连续子序列.
什么15, -30, 10是连续的后续序列？
我没有参加任何基础大学微积分的数学课程.然而,在我的编程工作过程中,我从博客和阅读中学到了很多数学和能力科学,我真的相信我有一个不错的数学思维.例如,我喜欢Project Euler并且取得了成功.
我想潜入并真正开始学习一些很酷的数学,特别是离散数学,集理论,图论,数论,组合学,范畴论,lambda演算等.到目前为止,我的印象是我很有能力接受这些在概念层面,但我在数学语言和符号方面遇到了很多困难.我只是不"说语言",虽然我正在努力学习它,但我的进展非常缓慢.甚至一个公式或术语重段也可能需要几个小时才能完成.是的,我可以查找术语和定义,但这是一个非常繁重的过程,它极大地模糊了我正在努力学习的理论简单性.
我真的害怕我不得不回到我离开的地方,获得一本中级数学教科书,并投入一些时间进行练习,以这种思维方式训练自己.这听起来非常无聊,所以我想知道是否有其他人对此有任何想法或经验.
问题:
考虑添加两个n位二进制整数的问题,存储在两个n元素数组A和B中.两个整数之和应以二进制形式存储在(n + 1) - 元素数组C中.说明问题正式并写入伪代码以添加两个整数.
解:
题:
能用真实的例子解释上面的解决方案吗？谢谢.
我正在寻找一种有效的算法来计算任何给定整数的乘法分区.例如,12的这种分区的数量是4,即
12 = 12×1 = 4×3 = 2×2×3 = 2×6
我已经阅读了维基百科文章,但这并没有真正给我一个生成分区的算法(它只讨论了这些分区的数量,说实话,即使这对我来说也不是很清楚!) .
我正在看的问题要求我为非常大的数字(> 10亿)计算乘法分区,所以我试图为它提出一种动态编程方法(以便找到所有可能的分区,用于较小的数字可以是当较小的数字本身是一个较大数字的因素时重复使用),但到目前为止,我不知道从哪里开始!
任何想法/提示将不胜感激 - 这不是一个家庭作业问题,只是我试图解决的问题,因为它看起来很有趣!
algorithm combinatorics discrete-mathematics divide-and-conquer
我如何总结以下顺序:
?n/1? + ?n/2? + ?n/3? + ... + ?n/n?
这只是C++上的O(n)解决方案:
#include <iostream>
int main()
{
int n;
std::cin>>n;
unsigned long long res=0;
for (int i=1;i<=n;i++)
{
res+= n/i;
}
std::cout<<res<<std::endl;
return 0;
}
你知道比这更好的解决方案吗？我的意思是O(1)或O(log(n)).感谢您的时间:)和解决方案
编辑:谢谢你的所有答案.如果有人想要解决方案O(sqrt(n)):Python:
import math
def seq_sum(n):
sqrtn = int(math.sqrt(n))
return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2
n = int(input())
print(seq_sum(n))
C++:
#include <iostream>
#include <cmath>
int main()
{
int n;
std::cin>>n;
int sqrtn = (int)(std::sqrt(n));
long …