查看: 7745|回复: 1

数学建模（5）——改良圈算法

[复制链接]

字体大小: 正常放大

浅夏110

542 主题	15 听众	1万积分

TA的每日心情

	开心 2020-11-14 17:15

签到天数: 74 天

[LV.6]常住居民II

群组: 2019美赛冲刺课程

群组: 站长地区赛培训

群组: 2019考研数学桃子老师

群组: 2018教师培训（呼伦贝

群组: 2019考研数学站长系列

电梯直达

1^#

发表于 2018-11-17 09:23 |只看该作者 |倒序浏览

|招呼Ta 关注Ta |邮箱已经成功绑定

摘要：本文讲的是数学建模（5）——改良圈算法，改良圈算法可得到旅行商问题的较好解，遗传算法那章就是利用该算法得到初始种群基本原理首先求得一个Hamilton圈，然后修改圈得到具有较小权的另一个Hamilton圈，直至无法改进则停止构建新圈。

改良圈算法可得到旅行商问题的较好解，遗传算法那章就是利用该算法得到初始种群基本原理

首先求得一个Hamilton圈，然后修改圈得到具有较小权的另一个Hamilton圈，直至无法改进则停止构建新圈

对于 1≤i<i+1<j≤n,构建新的Hamilton圈
Cij = v1v2…vivjvj-1vj-2…vi+1vJ+1vJ+2…vnv1
它是由C中将vi和vj之间的边逆序得到的。
若 w（vivj）+w（vi+1vj+1）<w（vivi+1）+w（vjvj+1）
则该圈替换有效

使用该算法得到的只是较好解，几乎可以肯定不是最优解代码实例

clear,clc a=[0 56 35 21 51 60 56 0 21 57 78 70 35 21 0 36 68 68 21 57 36 0 51 61 51 78 68 51 0 13 60 70 68 61 13 0]; L=size(a,1); c=[5 1:4 6 5];%选择初始圈 [circle,long]=modifycircle(a,L,c)function [circle,long]=modifycircle(a,L,c); for k=1

flag=0;%退出标志 for m=1

-2 %m为算法中的i for n=m+2

%n为算法中的j if a(c(m),c(n))+a(c(m+1),c(n+1))<a(c(m),c(m+1))+a(c(n),c(n+1)) c(m+1:n)=c(n:-1:m+1); flag=flag+1;%修改标志+1 end end end if flag==0%一条边也没修改，直接返回 long=0; for i=1

long=long+a(c(i),c(i+1)); end circle=c;%返回修改圈 return end end

以上是云栖社区小编为您精心准备的的内容，在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索matlab ，算法，数学建模解优化，以便于您获取更多的相关知识。

生命不止，继续 go go go !!!

上一篇博客跟大家介绍了，如何实现一个简单的tcp服务器和客户端，那么在此基础上，继续深耕一点点，介绍一下如何创建一个聊天室。

当然，还是还是一个要有一个服务端和若干个客户端。

server
net.Listen
Accept
这两个方法就不介绍了，之前都有提到过。

声明一个net.Conn数组，用于存放连接服务器的客户端：

var clients []net.Conn

大部分跟之前提到的tcp的server／client没有区别，最大的区别就是服务端收到消息后需要通知各个客户端，所以可以通过遍历数组cliQue来完成消息的通知。这里用到了for…range循环：

func notify(conn net.Conn, msg string) { for _, con := range clients { if con.RemoteAddr() != conn.RemoteAddr() { con.Write([]byte(msg)) } } }

顺便介绍一下RemoteAddr

func (c *IPConn) RemoteAddr() Addr

作用：
RemoteAddr returns the remote network address. The Addr returned is shared by all invocations of RemoteAddr, so do not modify it.

有一个客户端离开聊天室的时，要通知所有的客户端：

func disconnect(conn net.Conn, name string) { for index, con := range clients { if con.RemoteAddr() == conn.RemoteAddr() { disMsg := name + " has left the room." fmt.Println(disMsg) clients = append(clients[:index], clients[index+1:]...) notify(conn, disMsg) } } }

Go语言函数中有三个点…表示为可变参数，可以接受任意个数的参数。

append主要用于给某个切片（slice）追加元素

如果该切片存储空间（cap）足够，就直接追加，长度（len）变长；如果空间不足，就会重新开辟内存，并将之前的元素和新的元素一同拷贝进去

第一个参数为切片，后面是该切片存储元素类型的可变参数

client
客户端的代码就相对简单了很多。net.Dial也不再赘述。
注意就是从conn读数据，这里readStr[:length]用到了切片。

func read(conn net.Conn) { for { length, err := conn.Read(readStr) if err != nil { fmt.Printf("Error when read from server. Error:%s\n", err) os.Exit(0) } fmt.Println(string(readStr[:length])) } }

完整代码
服务端：

package main import ( "fmt" "net" "os" ) var clients []net.Conn func main() { var ( host = "localhost" port = "8000" remote = host + ":" + port data = make([]byte, 1024) ) fmt.Println("Initiating server...") lis, err := net.Listen("tcp", remote) defer lis.Close() if err != nil { fmt.Printf("Error when listen: %s, Err: %s\n", remote, err) os.Exit(-1) } for { var res string conn, err := lis.Accept() if err != nil { fmt.Println("Error accepting client: ", err.Error()) os.Exit(0) } clients = append(clients, conn) go func(con net.Conn) { fmt.Println("New connection: ", con.RemoteAddr()) // Get client's name length, err := con.Read(data) if err != nil { fmt.Printf("Client %v quit.\n", con.RemoteAddr()) con.Close() disconnect(con, con.RemoteAddr().String()) return } name := string(data[:length]) comeStr := name + " entered the room." notify(con, comeStr) // Begin recieve message from client for { length, err := con.Read(data) if err != nil { fmt.Printf("Client %s quit.\n", name) con.Close() disconnect(con, name) return } res = string(data[:length]) sprdMsg := name + " said: " + res fmt.Println(sprdMsg) res = "You said:" + res con.Write([]byte(res)) notify(con, sprdMsg) } }(conn) } } func notify(conn net.Conn, msg string) { for _, con := range clients { if con.RemoteAddr() != conn.RemoteAddr() { con.Write([]byte(msg)) } } func disconnect(conn net.Conn, name string) { for index, con := range clients { if con.RemoteAddr() == conn.RemoteAddr() { disMsg := name + " has left the room." fmt.Println(disMsg) clients = append(clients[:index], clients[index+1:]...) notify(conn, disMsg) } } }

客户端：

package main import ( "bufio" "fmt" "net" "os" ) var writeStr, readStr = make([]byte, 1024), make([]byte, 1024) func main() { var ( host = "localhost" port = "8000" remote = host + ":" + port reader = bufio.NewReader(os.Stdin) ) con, err := net.Dial("tcp", remote) defer con.Close() if err != nil { fmt.Println("Server not found.") os.Exit(-1) } fmt.Println("Connection OK.") fmt.Printf("Enter your name: ") fmt.Scanf("%s", &writeStr) in, err := con.Write([]byte(writeStr)) if err != nil { fmt.Printf("Error when send to server: %d\n", in) os.Exit(0) } fmt.Println("Now begin to talk!") go read(con) for writeStr, _, _ = reader.ReadLine() if string(writeStr) == "quit" { fmt.Println("Communication terminated.") os.Exit(1) } in, err := con.Write([]byte(writeStr)) if err != nil { fmt.Printf("Error when send to server: %d\n", in) os.Exit(0) } } } func read(conn net.Conn) { for { length, err := conn.Read(readStr) if err != nil { fmt.Printf("Error when read from server. Error:%s\n", err) os.Exit(0) } fmt.Println(string(readStr[:length])) } }

创建一个本地代码库

切换到你需要创建的代码库的目录下：

运行如下git命令

git --bare init

git下会出现一些隐藏的文件，这些文件时git本地库的描述文件

加载项目文件

git add .

最后的符号“.”是指 “所有的文件，文件夹，和子文件夹”。如果我们只想将特警的文件添加到库中去，我们可以指定它们：

git add my_file,my_file2 ,my_file3

提交添加的文件

git commit -m "initial commit"

这个命令之后就提交了所有加载的文件，如果需要查看状态可以使用：git status