我有一组坐标
[{"X':1,"Y":2},{"X':2,"Y":20},{"X':10,"Y":20},{"X':2,"Y":2},{"X':1,"Y":3},{"X':10,"Y":2}]
按照客户的需求，排序方式按照坐标排序，但是这个排序既不是按照X也不是按照Y
而是要让坐标相近的排在一起，不相近的无所谓顺序了。想了好久没有想出什么好的方案，不知道大家有什么好的计策没有？

-- 
My Blog >> http://leejd.cndev.org
My QQ >> 9847243

什么叫坐标相近

在06-6-13，Gerald Lee <leejd80 at gmail.com> 写道：
>
> 我有一组坐标
>
> [{"X':1,"Y":2},{"X':2,"Y":20},{"X':10,"Y":20},{"X':2,"Y":2},{"X':1,"Y":3},{"X':10,"Y":2}]
> 按照客户的需求，排序方式按照坐标排序，但是这个排序既不是按照X也不是按照Y
> 而是要让坐标相近的排在一起，不相近的无所谓顺序了。想了好久没有想出什么好的方案，不知道大家有什么好的计策没有？
>
> --
> My Blog >> http://leejd.cndev.org
> My QQ >> 9847243
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>


-- 
devdoer
devdoer at gmail.com
http://project.mytianwang.cn/cgi-bin/blog
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060613/036576a8/attachment.html

这个需求本身比较模糊，最好能先把它量化成一个对结果准确程度的判定函数，然好才好衡量算法的优劣。

大致思路有这么几条：
1.最简单的贪心法，（随便按x坐标或y坐标）排序之后，从一个边缘的点开始，每次从剩下的点中选出和上一个点最近的。
2.点的数量不是很多，而结果的准确度要求高的话，以贪心法的结果为初始约束条件分枝定界搜索。
3.分治法，预先将整个空间粗分成许多子区域，每个区域内的点用1或者2的方法排序，然后再安排区域之间的顺序。
4.进一步优化的话，考虑怎样在分治法中更准确的划分子区域，如果预先知道点的分布规律的话可以针对性的作些处理。

具体的实现与精确的需求、问题的规模、数据的分布都有很大关系，对结果要求很高的话可能需要多试验比较几种方案才能找到最优算法。

On 6/13/06, Gerald Lee <leejd80 at gmail.com> wrote:
>
> 我有一组坐标
>
> [{"X':1,"Y":2},{"X':2,"Y":20},{"X':10,"Y":20},{"X':2,"Y":2},{"X':1,"Y":3},{"X':10,"Y":2}]
> 按照客户的需求，排序方式按照坐标排序，但是这个排序既不是按照X也不是按照Y
> 而是要让坐标相近的排在一起，不相近的无所谓顺序了。想了好久没有想出什么好的方案，不知道大家有什么好的计策没有？
>
> --
> My Blog >> http://leejd.cndev.org
> My QQ >> 9847243
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060614/8805d377/attachment.htm

对了，刚想到一个贪心法的改进版，也许效果会稍好。
"每次从剩下的点中选出和上一个点最近的"，改成"每次从剩下的点中选出和上k个点距离的加权和最小的"。
"加权和"的意思是（p是当前选出的点的序列，t是一个事先设定的常数序列，我估计一个递减数列效果会比较好）：

def k_dist(next):
    d = 0
    for i in range(k):
        d += dist(p[-i],next)*t[i]
    return d

参数k和t的值需要通过实验调整。

On 6/14/06, swordsp <sparas2006 at gmail.com> wrote:
>
> 这个需求本身比较模糊，最好能先把它量化成一个对结果准确程度的判定函数，然好才好衡量算法的优劣。
>
> 大致思路有这么几条：
> 1.最简单的贪心法，（随便按x坐标或y坐标）排序之后，从一个边缘的点开始，每次从剩下的点中选出和上一个点最近的。
> 2.点的数量不是很多，而结果的准确度要求高的话，以贪心法的结果为初始约束条件分枝定界搜索。
> 3.分治法，预先将整个空间粗分成许多子区域，每个区域内的点用1或者2的方法排序，然后再安排区域之间的顺序。
> 4.进一步优化的话，考虑怎样在分治法中更准确的划分子区域，如果预先知道点的分布规律的话可以针对性的作些处理。
>
> 具体的实现与精确的需求、问题的规模、数据的分布都有很大关系，对结果要求很高的话可能需要多试验比较几种方案才能找到最优算法。
>
> On 6/13/06, Gerald Lee < leejd80 at gmail.com> wrote:
>
> > 我有一组坐标
> [{"X':1,"Y":2},{"X':2,"Y":20},{"X':10,"Y":20},{"X':2,"Y":2},{"X':1,"Y":3},{"X':10,"Y":2}]
>
> 按照客户的需求，排序方式按照坐标排序，但是这个排序既不是按照X也不是按照Y
> 而是要让坐标相近的排在一起，不相近的无所谓顺序了。想了好久没有想出什么好的方案，不知道大家有什么好的计策没有？
>
> --
> My Blog >> http://leejd.cndev.org
> My QQ >> 9847243
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060614/f6bad74b/attachment.html

你这个描述有问题。

如果平面上有三个点，A， B，
C，它们之间的举例，AB>BC>AC，那么如果以A开头，这个顺序应该是ACB，如果以B开头，这个顺序应该是BCA，如果以C开头，这个顺序应该是CAB

也就是说你得告诉我们哪个点是头。

第二，如果有四个点ABCD，AB >BC>CD>AD，那么以A开头，照你的描述，这个顺序将会是ADADA.....

你先得把你的需求描述清楚。

On 6/13/06, swordsp <sparas2006 at gmail.com> wrote:
> 对了，刚想到一个贪心法的改进版，也许效果会稍好。
> "每次从剩下的点中选出和上一个点最近的"，改成"每次从剩下的点中选出和上k个点距离的加权和最小的"。
> "加权和"的意思是（p是当前选出的点的序列，t是一个事先设定的常数序列，我估计一个递减数列效果会比较好）：
>
> def k_dist(next):
>     d = 0
>     for i in range(k):
>         d += dist(p[-i],next)*t[i]
>     return d
>
> 参数k和t的值需要通过实验调整。
>
>
> On 6/14/06, swordsp <sparas2006 at gmail.com> wrote:
> >
> > 这个需求本身比较模糊，最好能先把它量化成一个对结果准确程度的判定函数，然好才好衡量算法的优劣。
> >
> > 大致思路有这么几条：
> > 1.最简单的贪心法，（随便按x坐标或y坐标）排序之后，从一个边缘的点开始，每次从剩下的点中选出和上一个点最近的。
> > 2.点的数量不是很多，而结果的准确度要求高的话，以贪心法的结果为初始约束条件分枝定界搜索。
> > 3.分治法，预先将整个空间粗分成许多子区域，每个区域内的点用1或者2的方法排序，然后再安排区域之间的顺序。
> > 4.进一步优化的话，考虑怎样在分治法中更准确的划分子区域，如果预先知道点的分布规律的话可以针对性的作些处理。
> >
> >
> 具体的实现与精确的需求、问题的规模、数据的分布都有很大关系，对结果要求很高的话可能需要多试验比较几种方案才能找到最优算法。
> >
> >
> >
> > On 6/13/06, Gerald Lee < leejd80 at gmail.com> wrote:
> >
> > >
> >
> > 我有一组坐标
> >
> [{"X':1,"Y":2},{"X':2,"Y":20},{"X':10,"Y":20},{"X':2,"Y":2},{"X':1,"Y":3},{"X':10,"Y":2}]
> > 按照客户的需求，排序方式按照坐标排序，但是这个排序既不是按照X也不是按照Y
> > 而是要让坐标相近的排在一起，不相近的无所谓顺序了。想了好久没有想出什么好的方案，不知道大家有什么好的计策没有？
> >
> > --
> > My Blog >> http://leejd.cndev.org
> > My QQ >> 9847243
> >
> >
> > _______________________________________________
> > python-chinese
> > Post: send python-chinese at lists.python.cn
> > Subscribe: send subscribe to
> python-chinese-request at lists.python.cn
> > Unsubscribe: send unsubscribe to
> python-chinese-request at lists.python.cn
> > Detail Info:
> http://python.cn/mailman/listinfo/python-chinese
> >
> >
> >
>
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to
> python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to
> python-chinese-request at lists.python.cn
> Detail Info:
> http://python.cn/mailman/listinfo/python-chinese
>
>

On 6/14/06, shhgs <shhgs.efhilt at gmail.com> wrote:
>
> 你这个描述有问题。
>
> 如果平面上有三个点，A， B，
> C，它们之间的举例，AB>BC>AC，那么如果以A开头，这个顺序应该是ACB，如果以B开头，这个顺序应该是BCA，如果以C开头，这个顺序应该是CAB
>
> 也就是说你得告诉我们哪个点是头。


本来就没有定义清楚评价函数，而且就算有了评价函数，这个问题也很难求得最优解。
所谓贪心，本来就是一种简便的近似解法。
其后的几种改进，也只能说是更好的近似。

第二，如果有四个点ABCD，AB >BC>CD>AD，那么以A开头，照你的描述，这个顺序将会是ADADA.....


A已经被选过，当然 不会再被选到了，next是在剩下的点中挑选。

你先得把你的需求描述清楚。
>
>
需求又不是我提的...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060614/223a1e7b/attachment.htm

呵呵，需求是我提的。其实我们实际生活中遇到的问题，很多时候是无法量化的表示的。如果真想量化表示，可能复杂度会变得很大。
就拿这个问题来说，对于软件的操作用户，人家只要看到你的坐标顺序排的时候跳跃比较小（有图形表示坐标的位置）就认为是可以接受的。所以简单的方法就是找最短路径，起始点设置对用户关系不是很大的。但是如果你想得到最优解，算法方面狠复杂，但是对于软件的操作员来说，差别可能不大，为了这个不大的差别而投入很大的精力，对于应用软件开发，我感觉意义不是很大的，毕竟软件开发是需要成本的。
不过我感觉这个算法确实有意思，如果大家有兴趣，可以继续研究。


在 06-6-14，shhgs<shhgs.efhilt at gmail.com> 写道：
> 你这个描述有问题。
>
> 如果平面上有三个点，A， B，
> C，它们之间的举例，AB>BC>AC，那么如果以A开头，这个顺序应该是ACB，如果以B开头，这个顺序应该是BCA，如果以C开头，这个顺序应该是CAB
>
> 也就是说你得告诉我们哪个点是头。
>
> 第二，如果有四个点ABCD，AB >BC>CD>AD，那么以A开头，照你的描述，这个顺序将会是ADADA.....
>
> 你先得把你的需求描述清楚。
>
> On 6/13/06, swordsp <sparas2006 at gmail.com> wrote:
> > 对了，刚想到一个贪心法的改进版，也许效果会稍好。
> > "每次从剩下的点中选出和上一个点最近的"，改成"每次从剩下的点中选出和上k个点距离的加权和最小的"。
> > "加权和"的意思是（p是当前选出的点的序列，t是一个事先设定的常数序列，我估计一个递减数列效果会比较好）：
> >
> > def k_dist(next):
> >     d = 0
> >     for i in range(k):
> >         d += dist(p[-i],next)*t[i]
> >     return d
> >
> > 参数k和t的值需要通过实验调整。
> >
> >
> > On 6/14/06, swordsp <sparas2006 at gmail.com> wrote:
> > >
> > > 这个需求本身比较模糊，最好能先把它量化成一个对结果准确程度的判定函数，然好才好衡量算法的优劣。
> > >
> > > 大致思路有这么几条：
> > > 1.最简单的贪心法，（随便按x坐标或y坐标）排序之后，从一个边缘的点开始，每次从剩下的点中选出和上一个点最近的。
> > > 2.点的数量不是很多，而结果的准确度要求高的话，以贪心法的结果为初始约束条件分枝定界搜索。
> > > 3.分治法，预先将整个空间粗分成许多子区域，每个区域内的点用1或者2的方法排序，然后再安排区域之间的顺序。
> > > 4.进一步优化的话，考虑怎样在分治法中更准确的划分子区域，如果预先知道点的分布规律的话可以针对性的作些处理。
> > >
> > >
> > 具体的实现与精确的需求、问题的规模、数据的分布都有很大关系，对结果要求很高的话可能需要多试验比较几种方案才能找到最优算法。
> > >
> > >
> > >
> > > On 6/13/06, Gerald Lee < leejd80 at gmail.com> wrote:
> > >
> > > >
> > >
> > > 我有一组坐标
> > >
> > [{"X':1,"Y":2},{"X':2,"Y":20},{"X':10,"Y":20},{"X':2,"Y":2},{"X':1,"Y":3},{"X':10,"Y":2}]
> > > 按照客户的需求，排序方式按照坐标排序，但是这个排序既不是按照X也不是按照Y
> > > 而是要让坐标相近的排在一起，不相近的无所谓顺序了。想了好久没有想出什么好的方案，不知道大家有什么好的计策没有？
> > >
> > > --
> > > My Blog >> http://leejd.cndev.org
> > > My QQ >> 9847243
> > >
> > >
> > > _______________________________________________
> > > python-chinese
> > > Post: send python-chinese at lists.python.cn
> > > Subscribe: send subscribe to
> > python-chinese-request at lists.python.cn
> > > Unsubscribe: send unsubscribe to
> > python-chinese-request at lists.python.cn
> > > Detail Info:
> > http://python.cn/mailman/listinfo/python-chinese
> > >
> > >
> > >
> >
> >
> > _______________________________________________
> > python-chinese
> > Post: send python-chinese at lists.python.cn
> > Subscribe: send subscribe to
> > python-chinese-request at lists.python.cn
> > Unsubscribe: send unsubscribe to
> > python-chinese-request at lists.python.cn
> > Detail Info:
> > http://python.cn/mailman/listinfo/python-chinese
> >
> >
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>


-- 
My Blog >> http://leejd.cndev.org
My QQ >> 9847243

我有一个想法，就是质心的概念。

这些点都再一个平面上，所以很容易求出所有点的质心。然后根据各个点到质心的距离来排序。

其实通过质心是适合找到第一个点。
然后其他的点则通过贪婪算法逼近。。（感觉还要与质心比较。。。）

在 06-6-15，hydon<hydonlee at gmail.com> 写道：
> 我有一个想法，就是质心的概念。
>
> 这些点都再一个平面上，所以很容易求出所有点的质心。然后根据各个点到质心的距离来排序。
>


-- 
我的GMail, 我的Google, 世界为我所用...

用户的确不需要量化的标准，但程序员自己应该把模糊的需求量化，把问题的条件量化。
问题太复杂，可以在建模的时候简化，但建模本身没办法省略。
对模型求解代价太大，可以用近似解法，但一个量化的评价函数不能少。
毕竟算法也好程序也好，都只是数学过程，只能建立在数学模型的基础上。

如果以所有点顺序连线的路径总长度最小为评价函数，就是一个典型的旅行商问题的变例，有很多成熟的近似算法。
我的另一个想法是，考虑一个"相邻点距离组成的数列"的概念，则"路径总长度最小"实际上等价于"数列的平均值最小"。除了考虑这个数列的平均值之外，也许在评价函数中还可以再结合方差或者标准差。

On 6/14/06, Gerald Lee <leejd80 at gmail.com> wrote:
>
> 呵呵，需求是我提的。其实我们实际生活中遇到的问题，很多时候是无法量化的表示的。如果真想量化表示，可能复杂度会变得很大。
>
> 就拿这个问题来说，对于软件的操作用户，人家只要看到你的坐标顺序排的时候跳跃比较小（有图形表示坐标的位置）就认为是可以接受的。所以简单的方法就是找最短路径，起始点设置对用户关系不是很大的。但是如果你想得到最优解，算法方面狠复杂，但是对于软件的操作员来说，差别可能不大，为了这个不大的差别而投入很大的精力，对于应用软件开发，我感觉意义不是很大的，毕竟软件开发是需要成本的。
> 不过我感觉这个算法确实有意思，如果大家有兴趣，可以继续研究。
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060615/83cf1304/attachment.html

这样的话整体趋势就是"从中间往外排列"，我觉得大多数时候不如"从一端往另一端排列"。
比如考虑极限情况，所有点都在一条直线上均匀分布。

On 6/15/06, hydon <hydonlee at gmail.com> wrote:
>
> 其实通过质心是适合找到第一个点。
> 然后其他的点则通过贪婪算法逼近。。（感觉还要与质心比较。。。）
>
> 在 06-6-15，hydon<hydonlee at gmail.com> 写道：
> > 我有一个想法，就是质心的概念。
> >
> > 这些点都再一个平面上，所以很容易求出所有点的质心。然后根据各个点到质心的距离来排序。
> >
>
>
> --
> 我的GMail, 我的Google, 世界为我所用...
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060615/fd08813a/attachment.htm