亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標(biāo)題: 距離最近的點(diǎn)對問題算法 [打印本頁]

作者: plscareme 時(shí)間: 2007-07-11 09:43
標(biāo)題: 距離最近的點(diǎn)對問題算法
最近在看Sedgewick的那本Algorithms in C++，里面在28章有一個(gè)關(guān)于最近距離的點(diǎn)隊(duì)的問題求解的算法，分析研究了2天還是有所疑惑，有幾個(gè)點(diǎn)比較以后，拿出來請教大家，希望能給以一些分析。
主要算法：
算法的主要思想是先比較x坐標(biāo)，然后比較y坐標(biāo)，然后用合并排序來選擇距離最小的點(diǎn)對：
主要的數(shù)據(jù)結(jié)構(gòu)，點(diǎn)和鏈表節(jié)點(diǎn)：
struct point
{
int x;
int y;
};

struct node
{
struct point p;
struct node *next;
};
//全局變量
/* global */
int pass; // 表明比較x還是y坐標(biāo)
struct node *z; // 尾節(jié)電，無限大
float min; // 最短距離
struct point cp1, cp2; // 最短距離點(diǎn)對

//坐標(biāo)比較函數(shù)，pass為一比較x坐標(biāo)，否則（2）比較y坐標(biāo)：

int comp(struct node *t)
 { return (pass == 1) ? t->p.x : t->p.y; }
//合并排序函數(shù)
struct node *merge(struct node *a, struct node *b)
 {
struct node *c;
c = z;
do
 if (comp(a) < comp(b))
 { c->next = a; c = a; a = a->next; }
 else
 { c->next = b; c = b; b = b->next; }
while (c != z);
c = z->next; z->next = z;
return c;
 }
//距離比較函數(shù)

void check(struct point p1, struct point p2)
{
float dist;
if ((p1.y != z->p.y) && (p2.y != z->p.y))
{
 dist = sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
 if (dist < min)
 {
 min = dist; cp1 = p1; cp2 = p2;
 }
}
}

// 主要核心比較函數(shù)
struct node *sort(struct node *c, int number)
{
static int sort_i = 0;
int i;
struct node *a, *b, *tt;
float middle;
struct point p1, p2, p3, p4;
if (c->next == z)
 return c;
a = c;
for (i = 2; i <= number/2; i++)
 c = c->next;
b = c->next;
c->next = z;
if (pass == 2)
{
 middle = b->p.x;
}
//按照Sedgewick的說法,在調(diào)用這個(gè)merge之前,鏈表是以x坐標(biāo)排好序的.
c = merge(sort(a, number/2), sort(b, number - (number/2)));
//按照Sedgewick的說法,在這個(gè)merge之后, midlle的左右兩半的內(nèi)部點(diǎn)之間的距離,都大于min
// 這是為什么?
//為什么這里要比較四個(gè)點(diǎn),為什么四個(gè)點(diǎn)足夠了,這又是為什么?
if (pass == 2)
{
 p1 = z->p; p2 = z->p; p3 = z->p; p4 = z->p;
 for (a = c; a != z; a = a->next)
 if (fabs(a->p.x - middle) < min)
 {
 check(a->p, p1);
 check(a->p, p2);
 check(a->p, p3);
 check(a->p, p4);
 p1 = p2; p2 = p3; p3 = p4; p4 = a->p;
 }
}
return c;
}

//主函數(shù)

int main()
{
z = new node; z->p.x = max;
 z->p.y = max; z->next = z;
h = new node; h->next = readlist();
min = max;
//第一次pass為1，對x坐標(biāo)排序
pass = 1; h->next = sort(h->next, N);
//第二次pass為2，對y坐標(biāo)排序
pass = 2; h->next = sort(h->next, N);
}

作者: plscareme 時(shí)間: 2007-07-11 09:44
以前看過一個(gè)實(shí)現(xiàn)這個(gè)問題的算法，也是用的分而治之的算法，但是很復(fù)雜，這個(gè)算法很簡單，可是里面sort函數(shù)的實(shí)現(xiàn)，確實(shí)有些疑惑，不知道怎么實(shí)現(xiàn)的左右兩個(gè)半?yún)^(qū)的點(diǎn)對的距離都比全局的min大，又怎么實(shí)現(xiàn)通過比較四個(gè)點(diǎn)就能確保一定找到最近點(diǎn)對的原因？

謝謝！

作者: plscareme 時(shí)間: 2007-07-11 23:08
自己頂一下這個(gè)算法有什么問題么

作者: plscareme 時(shí)間: 2007-07-12 16:59
繼續(xù)關(guān)注

作者: plscareme 時(shí)間: 2007-07-13 11:23
readlist只是一個(gè)簡單的建立鏈表的偽函數(shù)，沒有什么特別的意義，這個(gè)算法的實(shí)現(xiàn)我是
第一次看到，我以前看到過一個(gè)實(shí)現(xiàn)，但是非常復(fù)雜。
這本書我看的是一本原版書，從別人手上借的，所以也沒有電子版。
我是有些迷迷糊糊，關(guān)于這個(gè)算法，尤其是比較四個(gè)點(diǎn)的那個(gè)地方，謝謝回復(fù)，我也在查找別的
資料，目前還沒有什么發(fā)現(xiàn)。

歡迎光臨 Chinaunix (http://www.72891.cn/)