Floyd算法应用-医院选址问题 - CSUER

本邮件内容由第三方提供，如果您不想继续收到该邮件，可 点此退订 。

Floyd算法应用-医院选址问题 - CSUER  阅读原文»

1)问题描述

n个村庄之间的交通图可以用有向网图来表示，图中边<v_i, v_j>上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？

2) 基本要求

(1) 建立模型，设计存储结构；

(2) 设计算法完成问题求解；

(3) 分析算法的时间复杂度。

3) 设计思想

医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。

设图G=（V，E），对任一顶点k，称E(k)=max{d(i, k)}（i∈V）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。

如图3(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。

【迷你微信】基于MINA、Hibernate、Spring、Protobuf的即时聊天系统：6.技术简介之Protobuf - 枫露霜阳  阅读原文»

欢迎阅读我的开源项目《迷你微信》服务器与《迷你微信》客户端

protocolbuffer(以下简称Protobuf)是google 的一种数据交换的格式，它独立于语言，独立于平台。google 提供了三种语言的实现：java、c++ 和 python，每一种实现都包含了相应语言的编译器以及库文件。由于它是一种二进制的格式，比使用 xml 进行数据交换快许多。可以把它用于分布式应用之间的数据通信或者异构环境下的数据交换。作为一种效率和兼容性都很优秀的二进制数据传输格式，可以用于诸如网络传输、配置文件、数据存储等诸多领域。――维基百科

使用原因

在不同语言的前后端交互时，由于不能直接调用，所以必须有一套相同的读写协议来规定数据的格式，也就是说，在服务器与客户端交互时，将要传输的内容按照规定模式转化为一种中间语言（byte数组），然后在另一端根据同样的格式转换回自己语言的对象，在这个过程中，可能会出现一些问题，如：

• 协议的内容需要繁琐的交流协商，以保证双方一致。
  
• 很可能出现在失误的情况下，导致数据对错位问题。
  
• 在协议变更的时候，双方都要进行修改，这是一种潜藏的隐患。
  
• 可能由于不同语言之间，变量类型的不同导致双方结果不同。

而Protobuf的出现，解决了这样一种隐患。首先Protobuf是用一种独立的Protob语言写的，简单易懂，并且从这一层直接去除掉语法错误问题；接着，Protobuff可以通过需要编译成不同的语言，从这一层解决了双方不一致和变更时衍生的问题。

定义Protobuf

在这里咱们简单的介绍一下Protobuf的几个常用语法：

package protocol;
import "Member.proto";

option java_package = "protocol.Data";

message UserItem{
enum Sex{
MALE = 0;
FEMALE = 1;
}
required string userName = 1;
required Sex sex = 2;
optional int32 father = 3;
repeated PersonalInfo personalInfo = 4;
}

咱们来解释一下这里面的代码分别是什么意思：

import "Member.proto";表示导入另一个Protobuf，这样就可以使用里面定义的message 对象PersonalInfo 了。

option java_package = "protocol.Data";表示将这个写好的Protobuf文件在编译时编译如protocol/Data文件夹下。

message UserItem表示对象的名称，比如编译成Java文件后，就是叫做UserItem.java的文件。

enum Sex是一个枚举的使用，下面就用到了这个Sex。

required string userName = 1;表示UserItem这个对象中有一个叫userName的参数，参数类型是String，requested表示在使用时，这个参数必须被填入，否则将报错！

optional与requested使用方式类似，表示在使用中这个参数可填可不填。

repeated PersonalInfo personalInfo = 4中的repeated则表示这个参数可能有多个（可以没有），PersonalInfo类型来自import "Member.proto";。

注意：.proto文件不能与定义的对象名（在这里是UserItem）相同，否则会编译失败！帖主就在此栽过跟头。o(>�<)o

使用

这里只介绍Java中对于Protobuf的使用（可参考《迷你微信》服务器），想了解C#对Protobuf的使用，请参考《迷你微信》客户端。

开始

想要在Java中使用Protobuf，首先要定义好Protobuf，然后用控制台指令进行编译，控制台在.proto文件的地址下，输入protoc --java_out=./ ./(我的proto文件名).proto

运行成功后，会在制定目录下出现(我的proto文件名).java文件，将其复制到你的Java项目中就可以使用了。

创建

当你要将你的数据转化为Protobuf对象时，需要这样创建：

import UserItemMsg;
..........

// 创建
UserItemMsg.UserItem.Builder builder = UserItemMsg.UserItem.newBuilder();
// 设置数值
builder.setUserName = "枫露霜阳";
builder.setSex(UserItemMsg.UserItem.Sex.MALE);
builder.addPhone = "18252060997";
builder.addPhone = "110";
// 要build起来
UserItemMsg uim = builder.build();
// 若是要转成byte数组
byte[] byteArray = uim.toByteArray();

上述代码将Protobuf在java中的类创建、设值、build、转为byte数组，最后用于网络传输。

反解

上面将Protobuf的Java类转化为byte数组，然后通过网络传输，到了接收端，如何将其解回Java对象呢？

import UserItemMsg;
...............

// 得到传过来的byte数组
byte[] byteArray = fromClientByteArray;
UserItemMsg.UserItem userItem = UserItemMsg.UserItem.parseFrom(byteArray);
// 获取数值
String userName = userItem.getUserName();

后话

至此，我们就把Protobuf的简单使用描述了一遍，若想看看帖主项目的详细使用请戳下面传送门。

欢迎阅读我的开源项目《迷你微信》服务器与《迷你微信》客户端

本文链接：【迷你微信】基于MINA、Hibernate、Spring、Protobuf的即时聊天系统：6.技术简介之Protobuf，转载请注明。

阅读更多内容