商户地理位置查询 + K近邻图

本文主要是介绍商户地理位置查询 + K近邻图，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

任务一：商户地理位置查询：

随着智能手机的普及，地理信息在诸如高德地图、大众点评、饿了么等App中得到广泛的应用，此次数据结构期末大作业将模拟实际生活中的查询需求，完成基于地理信息和文本信息的查找任务。问题的说明如下：系统中已经收集到许多商户的信息，每家商户包括以下三项信息：  

l  位置(x,y)，x>0 && y>0；

l  商家名称；12位A-Z 字符串，不含小写；

l  菜系， 6位A-Z字符串，不含小写；

查询任务：用户输入自己感兴趣的商家名称如KFC，程序输出KFC的位置信息。在此保证查询成功时结果唯一，当查询的信息不存在时，查询失败，输出NULL。

【输入】

第1行：商户的数量m和查询的数量n，m和n为整数，均不超过10⁹；

第2-（m+1）行：商户的信息，包括商家名称，位置x，位置y和菜系；

最后的n行：查询的信息，即每行包括一家商户的名称；

【输出】

输出应该为n行，每一行对应的是每次查询的结果，即商户的位置。

例如：

【输入】

5 3

JEANGEORGES 260036 14362 FRENCH

HAIDILAO 283564 13179 CHAFINGDIS

KFC 84809 46822 FASTFOOD

SAKEMATE 234693 37201 JAPANESE

SUBWAY 78848 96660 FASTFOOD

HAIDILAO

SAKEMATE

SUBWAY

【输出】//查询的商家位置

283564 13179 // HAIDILAO

234693 37201 // SAKEMATE

78848 96660 // SUBWAY

请根据本学期学习的知识，设计算法实现查询功能，并尝试分析算法的空间复杂度和时间复杂度，可结合数据规模、原始数据的特性等分析查询影响因素等。

1） 数据规模：200个商家、4000个商家、8*10⁵个商家等等；

2） 数据特性：每个规模的数据包含1组按商家名称升序，1组按商家名称降序，10组随机数据共12组数据集； 

3） 查询任务中的1组数据的查找时间说明，在本次实践中1组数据的查找时间是指：对该组数据中的每个商家查询1次后所需的平均时间。例如：对于200个商家的数据，需要分别统计每个商家查询时间（200次查询），再计算200次查询的平均值。

4） 任务说明：统计每组数据下的平均查询时间；

5） 书写要求：若采用教材内的算法实现查询，仅仅需要说明所用算法名称；若实践过程中涉及到自己设计的数据结构或者书本外的知识请在“实验记录和结果”中说明算法的基本思想。

对于任务一，一个朴素的想法，观察数据量的大小，最大在800，000，因此我们需要设计一个算法的时间复杂度小于O（n√n），对于一般的查找和排序来说，我们可以设计一个O（nlog（n））的算法，对于每一个商铺，包含4个元素，即名字，食物种类和横纵坐标，使用一个结构体储存他们，依照名字进行快速排序，这里的时间复杂度为O（nlog（n）*常数），这里是针对字符串string进行排序，需要乘以一个常数，之后我们便的道路一个有序的结构体数组，可以考虑进行二分查找，找到了输出坐标，否组输出NULL，这里的时间复杂度是O（mlog（n））,本题n和m的数量级别相同，因此总体的时间复杂度为大于O（nlog（n）），需要注意的是由于cin的读入速度问题，时间大约是scanf的两倍之上，如果使用cin的话会tle。

对于课堂之外的算法，因为本题在一个实际问题的背景中，商铺的数量应该是动态增加或减少的，还会有改变，我们不可能对于每次变化东重新排个序，为了更加符合实际，我们可以运用stl之set，其本质是红黑树算法（一种二叉搜索树），将每个商铺的结构体存储为一个节点，可以在O（log（n））的时间内动态添加或删去节点，以及进行查找。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
const long long maxn = 1e6  ;
struct Node
{
    string name;
    int x,y;
}p[maxn];
int n,m;
bool cmp(Node a,Node b){return a.name<b.name;}
void binary(string goal)
{
    int l=1,r=m;
    while(l<r)
    {
        int mid = (l+r)>>1;
        if(goal<p[mid].name) r=mid;
        if(goal>p[mid].name) l=mid+1;
        if(goal==p[mid].name) break;    
    }
    if(p[(l+r)>>1].name!=goal) printf("NULL\n");
    else printf("%d %d\n",p[(l+r)>>1].x,p[(l+r)>>1].y);
}
string s;
char *str= (char*)malloc(sizeof(char)); 
Node tmp[maxn];
void mergesort(int l,int r){
    if(l >= r ) return;
    int mid =(l + r) >>1;
    mergesort(l,mid);
    mergesort(mid+1,r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j<=r){
        if(p[i].name < p[j].name) tmp[k++] = p[i++];
        else tmp[k++] = p[j++];
    }
    while(i <= mid) tmp[k++] = p[i++];
    while(j <= r) tmp[k++] = p[j++];
    for(int i = l,j = 0;i<=r;i++,j++){
        p[i] = tmp[j];
    }
}
int main()
{
     cin>>m>>n;
     for(int i=1;i<=m;i++)
     {
         scanf("%s %d%d",str,&p[i].x,&p[i].y);
         p[i].name=str;
         scanf("%s",str);
    }
    mergesort(1,m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str); 
        s=str;
        binary(s);
    }
    free(str);
    return 0;
}

任务二：K近邻图

K近邻问题在机器学习和数据管理等领域有着重要的应用，例如：机器学习邻域的k近邻分类、数据管理领域的k近邻查询等。本任务要求求解混合-k近邻图连通（无向图）的最小k值。问题的描述为：给定n个欧几里得空间的点，计算使其构造的混合-k近邻图连通（无向图）的最小k值。在此混合k近邻图的边生成的规则是：当空间中的点q是点p的k最近邻，同时点p也是点q的k最近邻时，p和q有一条边。

【参考材料】K近邻图的相关定义    KNN的相关工作

【输入格式】

    第一行以空格分隔的整数n，代表顶点个数, 0 <= n <= 4000

    第二行到第n+1行是顶点的坐标x和y，均为浮点数, 0<= x,y <= 10000

【输出格式】

    使得混合-k近邻图连通的最小k值

请根据本学期学习的知识，设计算法实现k值的计算，并尝试分析算法的空间复杂度和时间复杂度，可结合数据规模、原始数据的特性等分析查询影响因素等。

1） 数据规模：200、4000、80000等等；数据在空间中随机分布。为了客观起见，一个数据规模下可以产生多组数据，然后计算其平均值。

2） 任务说明：统计每组数据下的平均查询时间；

书写要求：若采用教材内的算法，仅仅需要说明算法名称；若实践过程中涉及到自己设计的数据结构或者书本外的知识请在“实验记录和结果”中说明算法的基本思想。

（2）对于任务二，knn这一经典问题，这里我并未采取特殊的算法，只是进行了朴素的深搜，首相将每个节点与其他节点的距离存储为链表，在对每个节点连接的节点按照距离进行排序，之后进行二分答案，判断k是否为可行解，判断方法为，将每个节点前k小的边加入边集，再去掉单向的保证为混合-k近邻图，之后从1号节点深搜判断连通性即可。通过简单的计算，排序的时间复杂度达到O(n^2log(n)),处理的时间复杂度为O(n^2log(k))，与题目给出的4000的数量级刚好满足，而顺序和倒序的时间复杂度理论最劣都是O(n^3)，但是由于问题的特殊性，一般k的值比较小，所以与二分答案相差不大，大多数时间都浪费在排序和判断上了，下面对于课堂外算法，将给出一些思路用于进一步优化时间复杂度。

对于课堂之外的算法，本人的竞赛中有一种常用算法，也就是线段树，可以在log的时间内进行删改查询，如果将线段树进行扩维，就会得到kdtree，其最大的用处就是可以在单次查询中获得距离样本最近的若干个样本，我们就可以在klog(n)的时间内完成查询，这也是常用的用来优化KNN算法的方法，具体实现方法就是将二维空间不断的进行二分，而查询操作就是进行递归，将方邻域看作区间，可以发现这本质上就是一颗线段树，具体实现较为复杂，这里不在赘述（线段树的debug真的反人类）。这里我们优化了后一步，对于前一步的排序，其实仔细想想，我们没有必要排序，我们只需要选出根据某个轴排序前n/2个数。也就是说这是一个选择问题，并不是排序问题，所以可以想到我们可以利用之前讲过的快速选择的方法来优化。使用快速选择，我们可以在O(n)的时间内完成数据的拆分。

在实际问题中，我们的n可能是会动态变化的，也就是可能会涉及增删改的操作，如果重现建树就会像任务一一样，成本太大，为了保证时间复杂度，我们需要维护树的平衡，但是因为这里kdtree是二维的，课内所学的AVL树以及上述的红黑树并不适用，这里会采取替罪羊树来重建以维护平衡，用以保证增删改的时间复杂度在一个可用的范围，详细内容也较为复杂，这里同样不在赘述。

Knn算法就是一种聚类算法，我在数模中也会用到基于贪心的k均值算法，他们都是最为基础的聚类算法，之后还有密度聚类、层次聚类等算法，他们在机器学习中都有着相应的作用。

对于kdtree，这里推荐https://zhuanlan.zhihu.com/p/127022333这篇博客。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 4000 + 10 ;
const int maxk = 400 + 10 ;
struct val
{
    int pos;
    double v;
}map[maxn][maxn];
struct Node
{
    double x,y;
}p[maxn];
int n;
double lens(int a,int b){return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));}
bool cmp(val a,val b){return a.v<b.v;}
bool vis[maxn];
int num=0;
bool new_map[maxn][maxn];
void dfs(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(!new_map[u][i]) continue;
        if(vis[i]) continue;
        vis[i]=1;
        num++;
        dfs(i);
    }
}
bool judge(int k)
{
    num=0;
    memset(vis,0,sizeof(vis));
    memset(new_map,0,sizeof(new_map));
    for(int i=1;i<=n;i++)
        for(int j=2;j<=k+1;j++)
            new_map[i][map[i][j].pos]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(new_map[i][j] && new_map[j][i]) continue;
            else new_map[i][j]=0,new_map[j][i]=0;
    dfs(1);
//    cout<<num<<endl;
    if(num==n) return true;
    return false;
}
void QuickSort(int pos,int l,int r){    //快排 
    if(l>=r){    //若待排序序列只有一个元素，返回空 
        return ;
    }
    int i=l;    //i作为指针从左向右扫描 
    int j=r;    //j作为指针从右向左扫描
    val key=map[pos][l];//第一个数作为基准数 
    while(i<j){
        while(map[pos][j].v>=key.v&&i<j){    //从右边找小于基准数的元素 （此处由于j值可能会变，所以仍需判断i是否小于j） 
            j--;    //找不到则j减一 
        }
        map[pos][i]=map[pos][j];    //找到则赋值 
        while(map[pos][i].v<=key.v&&i<j){    //从左边找大于基准数的元素 
            i++;    //找不到则i加一 
        }
        map[pos][j]=map[pos][i];    //找到则赋值 
    }
    map[pos][i]=key;    //当i和j相遇，将基准元素赋值到指针i处 
    QuickSort(pos,l,i-1);    //i左边的序列继续递归调用快排 
    QuickSort(pos,i+1,r);    //i右边的序列继续递归调用快排 
}
int main()
{
     cin>>n;
     for(int i=1;i<=n;i++)
         cin>>p[i].x>>p[i].y;//O(n)
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
         {
             map[i][j].v=lens(i,j);
             map[i][j].pos=j;
        }//O(n^2)

    for(int i=1;i<=n;i++)
        QuickSort(i,1,n);//O(n^2log(n))
    int l=1,r=min(n-1,400);
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(judge(mid)) r=mid;
        else l=mid+1;
    }//O(log(k)*n)
    cout<<l<<endl;
    return 0;
}

这篇关于商户地理位置查询 + K近邻图的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！