1、图的定义
我们知道，前面讨论的数据结构都有一个框架，而这个框架是由相应的算法实现的，比如二叉树搜索树，左子树上所有结点的值均小于它的根结点的值，右子树所有结点的值均大于它的根节点的值，类似这种形状使得它容易搜索数据和插入数据，树的边表示了从一个节点到另一个节点的快捷方式。
而图通常有个固定的形状，这是由物理或抽象的问题所决定的。比如图中节点表示城市，而边可能表示城市间的班机航线。如下图是美国加利福利亚简化的高速公路网：
①、邻接：
如果两个顶点被同一条边连接，就称这两个顶点是邻接的，如上图 I 和 G 就是邻接的，而 I 和 F 就不是。有时候也将和某个指定顶点邻接的顶点叫做它的邻居，比如顶点 G 的邻居是 I、H、F。
int nodeNum=10//顶点数int tu[nodeNum][nodeNum]={0}//初始化邻接矩阵
while(次数条件){
//随机生成有连接的顶点标号
int nodeBegin=random()
int nodeEnd=random()
//双向连接，实现无向
tu[nodeBegin][nodeEnd]=1
tu[nodeEnd][nodeBegin]=1
}
import javax.swing.*import java.awt.*
import java.awt.event.*
import java.util.Random
public class GAFrame extends JFrame {
private static final long serialVersionUID = 1L
static TopologyPanel tpnl = new TopologyPanel()
private String[] ipop = new String[10]// 染色体
private int gernation = 0// 染色体代号
public static final int GENE = 9// 基因数
public GAFrame(String title) {
super(title)
}
public static void main(String args[]) {
tpnl.setLayout(null)
GAFrame frame = new GAFrame("遗传算法寻找最优路径")
frame.setContentPane(tpnl)
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE)
frame.setSize(370, 330)
JButton button1 = new JButton()
button1.setText("生成参数")
button1.setBounds(5, 245, 90, 25)
button1.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
tpnl.refreshPanel1()
}
})
JButton button2 = new JButton()
button2.setText("生成路径")
button2.setBounds(245, 245, 90, 25)
button2.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
tpnl.refreshPanel2()
}
})
tpnl.add(button1)
tpnl.add(button2)
frame.setVisible(true)
}
}
class TopologyPanel extends JPanel {
private static int[][] params1 = new int[8][2]
private static int[] params2 = new int[13]
private static Random rnd = new Random()
public void paint(Graphics g) {
super.paint(g)
g.fillOval(30, 120, 10, 10)
g.fillOval(100, 30, 10, 10)
g.fillOval(80, 210, 10, 10)
g.fillOval(140, 130, 10, 10)
g.fillOval(210, 50, 10, 10)
g.fillOval(260, 120, 10, 10)
g.fillOval(160, 230, 10, 10)
g.fillOval(230, 190, 10, 10)
g.drawLine(35, 125, 105, 30)
g.drawLine(105, 35, 215, 55)
g.drawLine(215, 55, 265, 125)
g.drawLine(265, 125, 235, 195)
g.drawLine(235, 195, 165, 235)
g.drawLine(85, 215, 165, 235)
g.drawLine(35, 125, 85, 215)
g.drawLine(35, 125, 145, 135)
g.drawLine(85, 215, 235, 195)
g.drawLine(105, 35, 145, 135)
g.drawLine(215, 55, 145, 135)
g.drawLine(265, 125, 145, 135)
g.drawLine(85, 215, 145, 135)
g.drawString("A", 21, 120)
g.drawString("B", 92, 30)
g.drawString("C", 70, 220)
g.drawString("D", 225, 60)
g.drawString("E", 148, 148)
g.drawString("F", 160, 253)
g.drawString("G", 245, 202)
g.drawString("H", 270, 130)
g.drawString("( " + params1[0][0] + ", " + params1[0][1] + " )", 30,
120)// A
g.drawString("( " + params1[1][0] + ", " + params1[1][1] + " )", 100,
30)// B
g.drawString("( " + params1[2][0] + ", " + params1[2][1] + " )", 80,
210)// C
g.drawString("( " + params1[3][0] + ", " + params1[3][1] + " )", 140,
130)// E
g.drawString("( " + params1[4][0] + ", " + params1[4][1] + " )", 210,
50)// D
g.drawString("( " + params1[5][0] + ", " + params1[5][1] + " )", 255,
115)// H
g.drawString("( " + params1[6][0] + ", " + params1[6][1] + " )", 160,
230)// F
g.drawString("( " + params1[7][0] + ", " + params1[7][1] + " )", 230,
190)// G
g.drawString("" + params2[0], 70, 77)// A-B
g.drawString("" + params2[1], 160, 45)// BD
g.drawString("" + params2[2], 240, 90)// DH
g.drawString("" + params2[3], 250, 160)// GH
g.drawString("" + params2[4], 200, 215)// FG
g.drawString("" + params2[5], 125, 225)// CF
g.drawString("" + params2[6], 60, 170)// AC
g.drawString("" + params2[7], 90, 130)// AE
g.drawString("" + params2[8], 160, 205)// CG
g.drawString("" + params2[9], 125, 85)// BE
g.drawString("" + params2[10], 180, 95)// DE
g.drawString("" + params2[11], 205, 140)// EH
g.drawString("" + params2[12], 115, 175)// CE
}
public void refreshPanel1() {
for (int i = 0i <params1.lengthi++) {
params1[i][0] = (rnd.nextInt(21) + 10) * 100
params1[i][1] = rnd.nextInt(41) + 20
}
for (int i = 0i <params2.lengthi++)
params2[i] = ((rnd.nextInt(91)) + 10) * 10
repaint()
}
public void refreshPanel2() {
// TopologyPanel tt = new TopologyPanel()
//
// tt.tenacc()
GAFrame.tpnl.tenacc()
}
String inialPop() {
Character s[] = new Character[9]
String[] a = new String[9]
a[0] = "1"
for (int i = 0i <s.lengthi++) {
s[i] = '-'
}
if (Math.random() <1 / 3.0) {
s[0] = 'B'
} else if (Math.random() >= 1.0 / 3.0 &&Math.random() <2.0 / 3.0) {
s[0] = 'C'
} else
s[0] = 'E'
switch (s[0]) {
case 'B': {// ss[0]选择B
a[1] = "1"
a[2] = a[6] = a[3] = "0"
if (Math.random() <0.5) {
s[1] = 'D'
} else {
s[1] = 'E'
}
switch (s[1]) {
case 'D': {
a[4] = "1"
a[5] = "0"
if (Math.random() <0.5) {
s[4] = 'H'
} else {
s[4] = 'E'
}
switch (s[4]) {
case 'H': {
a[7] = a[8] = "0"
}
break
case 'E': {
a[7] = "1"
if (Math.random() <0.5) {
s[7] = 'H'
} else {
s[7] = 'C'
}
switch (s[7]) {
case 'H': {
a[8] = "0"
}
break
case 'C': {
a[8] = "1"
if (Math.random() <0.5) {
s[8] = 'G'
} else {
s[8] = 'F'
}
}
}
}
}
}
break
case 'E': {
a[4] = a[7] = "0"
a[5] = "1"
if (Math.random() <1 / 3.0) {
s[5] = 'H'
} else if (Math.random() >= 1.0 / 3.0
&&Math.random() <2.0 / 3.0) {
s[5] = 'C'
} else
s[5] = 'D'
switch (s[5]) {
case 'H':
case 'D': {
a[8] = "0"
}
break
case 'C': {
a[8] = "1"
if (Math.random() <0.5) {
s[8] = 'G'
} else {
s[8] = 'F'
}
}
}
}
}
}
break
case 'E': {// s[0]选择E
a[2] = "1"
a[1] = a[3] = a[4] = a[5] = a[7] = a[6] = "0"
if (Math.random() <0.25) {
s[2] = 'B'
} else if (Math.random() >= 0.25 &&Math.random() <0.5) {
s[2] = 'C'
} else if (Math.random() >= 0.5 &&Math.random() <0.75) {
s[2] = 'D'
} else
s[2] = 'H'
switch (s[2]) {
case 'H':
case 'D':
case 'B': {
a[8] = "0"
}
break
case 'C': {
a[8] = "1"
if (Math.random() <0.5) {
s[8] = 'G'
} else {
s[8] = 'F'
}
}
}
}
break
case 'C': {// ss[0]选择C
a[1] = a[2] = a[4] = a[5] = a[7] = a[8] = "0"
a[3] = "1"
if (Math.random() <1 / 3.0) {
s[3] = 'G'
} else if (Math.random() >= 1.0 / 3.0 &&Math.random() <2.0 / 3.0) {
s[3] = 'F'
} else
s[3] = 'E'
switch (s[3]) {
case 'G':
case 'F': {
a[6] = "0"
}
break
case 'E': {
a[6] = "1"
if (Math.random() <1 / 3.0) {
s[6] = 'H'
} else if (Math.random() >= 1.0 / 3.0
&&Math.random() <2.0 / 3.0) {
s[6] = 'D'
} else
s[6] = 'B'
}
}
}
}
String res = ""
StringBuffer bf = new StringBuffer()
for (int i = 0i <s.lengthi++) {
bf.append(s[i])
}
res = bf.toString()
return res
}
String[] inialPops() {
String[] ipop = new String[10]
for (int i = 0i <10i++) {
ipop[i] = inialPop()
System.out.println(ipop[i])
}
for (int i = 0i <params1.lengthi++) {
System.out.print(params1[i][0] + " ")
}
return ipop
}
double calcfit() {
int bw = 0
int delay = 0
int len = 0
String ss = inialPop()
char[] s = ss.toCharArray()
switch (s[0]) {
case 'B': {// A-B
if (params1[0][0] >params1[1][0]) {
bw = params1[1][0]
} else {
bw = params1[0][0]
}
delay = params1[0][1] + params1[1][1]
len += params2[0]
switch (s[1]) {
case 'D': {// ABD
if (params1[4][0] <bw) {
bw = params1[4][0]
}
delay += params1[4][1]
len += params2[1]
switch (s[4]) {
case 'H': {// ABDH
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1]
len += params2[2]
}
break
case 'E': {// ABDE
if (params1[3][0] <bw) {
bw = params1[3][0]
}
delay += params1[3][1]
len += params2[9]
switch (s[7]) {
case 'H': {// ABDEH
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1]
len += params2[11]
}
break
case 'C': {// ABDEC
if (params1[2][0] <bw) {
bw = params1[5][0]
}
delay += params1[2][1]
len += params2[12]
switch (s[8]) {
case 'G': {// ABDECGH
if (params1[7][0] <bw) {
bw = params1[7][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay = delay + params1[5][1] + params1[7][1]
len = len + params2[8] + params2[3]
}
break
case 'F': {// ABDECFGH
if (params1[6][0] <bw) {
bw = params1[6][0]
}
if (params1[7][0] <bw) {
bw = params1[7][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay = delay + params1[5][1] + params1[7][1]
+ params1[6][1]
len = len + params2[5] + params2[4] + params2[3]
}
}
}
}
}
}
}
break
case 'E': {// ABE
if (params1[3][0] <bw) {
bw = params1[3][0]
}
delay += params1[3][1]
len += params2[9]
switch (s[5]) {
case 'H': {// ABEH
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1]
len += params2[11]
}
break
case 'D': {// ABEDH
if (params1[4][0] <bw) {
bw = params1[4][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1] + params1[4][1]
len += params2[10] + params2[2]
}
break
case 'C': {// ABEC
if (params1[2][0] <bw) {
bw = params1[2][0]
}
delay += params1[2][1]
len += params2[12]
switch (s[8]) {
case 'G': {// ABECGH
if (params1[7][0] <bw) {
bw = params1[7][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1] + params1[7][1]
len += params2[8] + params2[3]
}
break
case 'F': {
if (params1[6][0] <bw) {
bw = params1[6][0]
}
if (params1[7][0] <bw) {
bw = params1[7][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay = delay + params1[5][1] + params1[7][1]
+ params1[6][1]
len = len + params2[5] + params2[4] + params2[3]
}
}
}
}
}
}
}
break
case 'E': {// AE
if (params1[0][0] <params1[3][0]) {
bw = params1[0][0]
} else {
bw = params1[3][0]
}
delay = params1[0][1] + params1[3][1]
len = params2[7]
switch (s[2]) {
case 'H': {// AEH
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1]
len += params2[11]
}
break
case 'D': {// AEDH
if (params1[4][0] <bw) {
bw = params1[4][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1] + params1[4][1]
len += params2[10] + params2[2]
}
break
case 'B': {// AEBDH
if (params1[1][0] <bw) {
bw = params1[1][0]
}
if (params1[4][0] <bw) {
bw = params1[4][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1] + params1[4][1] + params1[1][1]
len += params2[9] + params2[1] + params2[2]
}
break
case 'C': {// AEC
if (params1[2][0] <bw) {
bw = params1[5][0]
}
delay += params1[2][1]
len += params2[12]
switch (s[8]) {
case 'G': {// AECGH
if (params1[7][0] <bw) {
bw = params1[7][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay = delay + params1[5][1] + params1[7][1]
len = len + params2[8] + params2[3]
}
break
case 'F': {// AECFGH
if (params1[6][0] <bw) {
bw = params1[6][0]
}
if (params1[7][0] <bw) {
bw = params1[7][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay = delay + params1[5][1] + params1[7][1]
+ params1[6][1]
len = len + params2[5] + params2[4] + params2[3]
}
}
}
}
}
break
case 'C': {// AC
if (params1[0][0] <params1[2][0]) {
bw = params1[0][0]
} else {
bw = params1[2][0]
}
delay = params1[0][1] + params1[2][1]
len = params2[6]
switch (s[3]) {
case 'G': {// ACGH
if (params1[7][0] <bw) {
bw = params1[7][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay = delay + params1[5][1] + params1[7][1]
len = len + params2[8] + params2[3]
}
break
case 'F': {// ACFGH
if (params1[6][0] <bw) {
bw = params1[6][0]
}
if (params1[7][0] <bw) {
bw = params1[7][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay = delay + params1[5][1] + params1[7][1] + params1[6][1]
len = len + params2[5] + params2[4] + params2[3]
}
break
case 'E': {// ACE
if (params1[3][0] <bw) {
bw = params1[3][0]
}
delay += params1[3][1]
len += params2[12]
switch (s[6]) {
case 'H': {// ACEH
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1]
len += params2[11]
}
break
case 'D': {// ACEDH
if (params1[4][0] <bw) {
bw = params1[4][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1] + params1[4][1]
len += params2[10] + params2[2]
}
break
case 'B': {// AEBDH
if (params1[1][0] <bw) {
bw = params1[1][0]
}
if (params1[4][0] <bw) {
bw = params1[4][0]
}
if (params1[5][0] <bw) {
bw = params1[5][0]
}
delay += params1[5][1] + params1[4][1] + params1[1][1]
len += params2[9] + params2[1] + params2[2]
}
}
}
}
}
}
double fitness1 = ((bw - 2000) + (200 - delay) * 10)
double fitness = fitness1 / len
return fitness
}
private void cross() {
String temp1, temp2
for (int i = 0i <10i++) {
if (Math.random() <0.25) {
double r = Math.random()
int pos = (int) (Math.round(r * 1000)) % 9
if (pos == 0) {
pos = 1
}
Object[] ipop = null
temp1 = ((String) ipop[i]).substring(0, pos)
+ ((String) ipop[(i + 1) % 10]).substring(pos)
temp2 = ((String) ipop[(i + 1) % 10]).substring(0, pos)
+ ((String) ipop[i]).substring(pos)
ipop[i] = temp1
ipop[(i + 1) / 10] = temp2
}
}
}
private void mutation() {
for (int i = 0i <4i++) {
int num = (int) (Math.random() * 9 * 10 + 1)
int chromosomeNum = (int) (num / 9) + 1
int mutationNum = num - (chromosomeNum - 1) * 9
if (mutationNum == 0)
mutationNum = 1
chromosomeNum = chromosomeNum - 1
if (chromosomeNum >= 10)
chromosomeNum = 9
String temp
Object[] ipop = null
if (((String) ipop[chromosomeNum]).charAt(mutationNum - 1) == '0') {
if (mutationNum == 1) {
temp = "1" + ((String) ipop[chromosomeNum]).substring
(mutationNum)
} else {
if (mutationNum != 9) {
temp = ((String) ipop[chromosomeNum]).substring(0,
mutationNum -
1)
+ "1" + ((String) ipop
[chromosomeNum]).substring(mutationNum)
} else {
temp = ((String) ipop[chromosomeNum]).substring(0,
mutationNum - 1)
+ "1"
}
}
} else {
if (mutationNum == 1) {
temp = "0" + ((String) ipop[chromosomeNum]).substring
(mutationNum)
} else {
if (mutationNum != 9) {
temp = ((String) ipop[chromosomeNum]).substring(0,
mutationNum -
1)
+ "0" + ((String) ipop
[chromosomeNum]).substring(mutationNum)
} else {
temp = ((String) ipop[chromosomeNum]).substring(0,
mutationNum - 1)
+ "1"
}
}
}
ipop[chromosomeNum] = temp
}
}
public String process() {
String str = ""
for (int i = 0i <10000i++) {
this.inialPop()
this.cross()
this.mutation()
}
return str
}
double acc() {
double qwe = calcfit()
System.out.println(qwe)
return qwe
}
private void tenacc() {
double[] ds = new double[10]
String[] ipop = new String[10]
for (int i = 0i <10i++) {
ipop[i] = inialPop()
ds[i] = calcfit()
// System.out.println(ipop[i])
// System.out.println(ds[i])
}
for (int i = 1i <ds.lengthi++) {
if (ds[0] >ds[i]) {
ipop[0] = ipop[i]
}
}
Graphics g = null
g = getGraphics()
super.paint(g)
// g.clearRect(0, 0, 400, 400)
g.fillOval(30,120,10,10)
g.fillOval(100,30,10,10)
g.drawString("E",148,148)
g.drawString("F",160,253)
g.drawString("G",245,202)
g.drawString("H",270,130)
}
}
/*
* private void paintComponent(Graphics gg) { super.paintComponent(gg)
* Graphics2D g = (Graphics2D)ggg.setStroke(new BasicStroke(10))
* g.drawOval(100,50,200,200)this.repaint()}
*/
