需要哪种算法来做到这一点？
我有这种形式的数据：
- 对于x=1，y是{1,4,6,7,9,18,16,19}之一
- 对于x=2，y是{1,5,7,4之一}
- 对于 x=3，y 是 {2,6,4,8,2} 之一
- ....
- 对于 x=100，y 是 {2,7,89,4,5} 之一
仅值之一每组中都是正确值，其余的是随机噪声。
我知道正确的值描述了参数未知的正弦函数。如何从每组中找到正确的值组合？ 我正在寻找类似“旅行推销员”的组合优化算法
I have data of this form:
- for x=1, y is one of {1,4,6,7,9,18,16,19}
- for x=2, y is one of {1,5,7,4}
- for x=3, y is one of {2,6,4,8,2}
- ....
- for x=100, y is one of {2,7,89,4,5}
Only one of the values in each set is the correct value, the rest is random noise.
I know that the correct values describe a sinusoid function whose parameters are unknown. How can I find the correct combination of values, one from each set?
I am looking something like "travelling salesman"combinatorial optimization algorithm
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您正在尝试进行曲线拟合，根据曲线拟合的类型，有多种算法您想要将曲线拟合到的曲线（线性、多项式等）。我不知道是否有正弦曲线（傅立叶近似）的特定算法，但我的第一个想法是使用具有正弦多项式近似的多项式拟合算法。
我想知道您是否需要在另一个更大的程序中执行此操作，或者您是否尝试单独完成此任务。如果是这样，那么您最好使用统计软件包，我首选的是 R 。它允许您导入数据并拟合曲线并仅用几行绘制图形，您还可以在批处理模式下使用 R 从脚本甚至程序中调用它（这是我倾向于做的）。
You're trying to do curve fitting, for which there are several algorithms depending on the type of curve you want to fit your curve to (linear, polynomial, etc.). I have no idea whether there is a specific algorithm for sinusoidal curves (Fourier approximations), but my first idea would be to use a polynomial fitting algorithm with a polynomial approximation of the sine.
I wonder whether you need to do this in the course of another larger program, or whether you are trying to do this task on its own. If so, then you'd be much better off using a statistical package, my preferred one being R. It allows you to import your data and fit curves and draw graphs in just a few lines, and you could also use R in batch-mode to call it from a script or even a program (this is what I tend to do).
这取决于你所说的“确切”是什么意思，以及你事先知道什么。如果您知道频率 w，并且正弦曲线是无偏的，则您有一个方程
a cos(w * x) + b sin(w * x)，
其中两个 (x,y) 点处于不同的 x 值，您可以找到 a 和b，然后对照所有其他点检查生成的曲线。选择 y 观测值数量最少的两个 x 值，并对所有 y 进行尝试。如果存在偏差，即您的方程为
您需要查看三个 x 值。
如果您不知道频率，您可以尝试相同的技术，不幸的是，解决方案可能不是唯一的，可能有多个 w 适合。
编辑 据我了解您的问题，每个 x 都有一个真正的 y 值和一堆不正确的值。你想找到真正的价值。最好的方法是通过少量点拟合曲线，并检查该曲线是否适合其他集合中的某些 y 值。
如果并非所有 x 值都具有有效的 y 值，则适用相同的技术，但您需要查看更大的一组对、三元组或四元组（基本上是具有不同 y 值的每对、三元组或四元组）
如果您的问题是别的问题，我怀疑是这样，请具体说明。
2 准确地描述成功是什么样子的。举个例子，比如 10 分而不是 100 分就好了。
目前还不清楚这与组合优化有什么关系。
It depends on what you mean by "exactly", and what you know beforehand. If you know the frequency w, and that the sinusoid is unbiased, you have an equation
a cos(w * x) + b sin(w * x)
with two (x,y) points at different x values you can find a and b, and then check the generated curve against all the other points. Choose the two x values with the smallest number of y observations and try it for all the y's. If there is a bias, i.e. your equation is
You need to look at three x values.
If you do not know the frequency, you can try the same technique, unfortunately the solutions may not be unique, there may be more than one w that fits.
Edit As I understand your problem, you have a real y value for each x and a bunch of incorrect ones. You want to find the real values. The best way to do this is to fit curves through a small number of points and check to see if the curve fits some y value in the other sets.
If not all the x values have valid y values then the same technique applies, but you need to look at a much larger set of pairs, triples or quadruples (essentially every pair, triple, or quad of points with different y values)
If your problem is something else, and I suspect it is, please specify it.
a cos(w * x) + b sin(w * x) + c. If you mean something different, specify it.2 Specify exactly what success looks like. An example with say 10 points instead of 100 would be nice.
It is extremely unclear what this has to do with combinatorial optimization.
正弦方程非常普遍，如果您取所有 y 的任何随机值，这些值都可以拟合到正弦函数中，除非您给出条件，例如。频率<100或所有参数都是整数，理论上不可能区分噪声和数据，因此首先要从数据源/实验中找到这样的条件。
Sinusoidal equations are so general that if you take any random value of all y's these values can be fitted in sinusoidal function unless you give conditions eg. Frequency<100 or all parameters are integers,its not possible to diffrentiate noise and data theorotically so work on finding such conditions from your data source/experiment first.
正弦曲线是指一个函数增加 n 步，然后减少 n 步，等等？如果是这样，您可以将数据建模为通过上行链路和下行链路连接的节点序列。对于每个节点（y的可能值），记录仅上升或下降链接的链的长度和结束值（每个节点将有多个链）。然后扫描长度相等、方向相反的连续运行，以某个初始偏移量为模。
By sinusoidal, do you mean a function that is increasing for n steps, then decreasing for n steps, etc.? If so, you you can model your data as a sequence of nodes connected by up-links and down-links. For each node (possible value of y), record the length and end-value of chains of only ascending or descending links (there will be multiple chain per node). Then you scan for consecutive runs of equal length and opposite direction, modulo some initial offset.