class Base
公司專注于為企業(yè)提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、微信公眾號(hào)開(kāi)發(fā)、電子商務(wù)商城網(wǎng)站建設(shè)，微信小程序開(kāi)發(fā)，軟件按需開(kāi)發(fā)網(wǎng)站等一站式互聯(lián)網(wǎng)企業(yè)服務(wù)。憑借多年豐富的經(jīng)驗(yàn)，我們會(huì)仔細(xì)了解各客戶的需求而做出多方面的分析、設(shè)計(jì)、整合，為客戶設(shè)計(jì)出具風(fēng)格及創(chuàng)意性的商業(yè)解決方案，創(chuàng)新互聯(lián)更提供一系列網(wǎng)站制作和網(wǎng)站推廣的服務(wù)。
{
protected String name;
protected getScore(){return 0;};
}
class Team extends Base
{
private int gf;
private int ga;
private int pts;
private int gd;
public Team(int Gf,int Ga)
{
gf=Gf;
ga=Ga;
gd=gf-ga;
if(gd0)
{
pts=3
}
else if(gd==0)
{
pts=1;
}
else
{
pts=0;
}
}
public int getScore()
{
return pts*10 + gd*5 + gf;
}
}
//大概是這樣了,看在我大晚上給你寫(xiě)代碼的份上，給我分吧
通過(guò)遺傳算法走迷宮。雖然圖1和圖2均成功走出迷宮，但是圖1比圖2的路徑長(zhǎng)的多，且復(fù)雜，遺傳算法可以計(jì)算出有多少種可能性，并選擇其中最簡(jiǎn)潔的作為運(yùn)算結(jié)果。
示例圖1：
示例圖2：
實(shí)現(xiàn)代碼：
import?java.util.ArrayList;
import?java.util.Collections;
import?java.util.Iterator;
import?java.util.LinkedList;
import?java.util.List;
import?java.util.Random;
/**
* 用遺傳算法走迷宮
*
* @author Orisun
*
*/
public?class?GA {
int?gene_len;?// 基因長(zhǎng)度
int?chrom_len;?// 染色體長(zhǎng)度
int?population;?// 種群大小
double?cross_ratio;?// 交叉率
double?muta_ratio;?// 變異率
int?iter_limit;?// 最多進(jìn)化的代數(shù)
Listboolean[] individuals;?// 存儲(chǔ)當(dāng)代種群的染色體
Labyrinth labyrinth;
int?width;??????//迷宮一行有多少個(gè)格子
int?height;?????//迷宮有多少行
public?class?BI {
double?fitness;
boolean[] indv;
public?BI(double?f,?boolean[] ind) {
fitness = f;
indv = ind;
}
public?double?getFitness() {
return?fitness;
}
public?boolean[] getIndv() {
return?indv;
}
}
ListBI best_individual;?// 存儲(chǔ)每一代中最優(yōu)秀的個(gè)體
public?GA(Labyrinth labyrinth) {
this.labyrinth=labyrinth;
this.width = labyrinth.map[0].length;
this.height = labyrinth.map.length;
chrom_len =?4?* (width+height);
gene_len =?2;
population =?20;
cross_ratio =?0.83;
muta_ratio =?0.002;
iter_limit =?300;
individuals =?new?ArrayListboolean[](population);
best_individual =?new?ArrayListBI(iter_limit);
}
public?int?getWidth() {
return?width;
}
public?void?setWidth(int?width) {
this.width = width;
}
public?double?getCross_ratio() {
return?cross_ratio;
}
public?ListBI getBest_individual() {
return?best_individual;
}
public?Labyrinth getLabyrinth() {
return?labyrinth;
}
public?void?setLabyrinth(Labyrinth labyrinth) {
this.labyrinth = labyrinth;
}
public?void?setChrom_len(int?chrom_len) {
this.chrom_len = chrom_len;
}
public?void?setPopulation(int?population) {
this.population = population;
}
public?void?setCross_ratio(double?cross_ratio) {
this.cross_ratio = cross_ratio;
}
public?void?setMuta_ratio(double?muta_ratio) {
this.muta_ratio = muta_ratio;
}
public?void?setIter_limit(int?iter_limit) {
this.iter_limit = iter_limit;
}
// 初始化種群
public?void?initPopulation() {
Random r =?new?Random(System.currentTimeMillis());
for?(int?i =?0; i population; i++) {
int?len = gene_len * chrom_len;
boolean[] ind =?new?boolean[len];
for?(int?j =?0; j len; j++)
ind[j] = r.nextBoolean();
individuals.add(ind);
}
}
// 交叉
public?void?cross(boolean[] arr1,?boolean[] arr2) {
Random r =?new?Random(System.currentTimeMillis());
int?length = arr1.length;
int?slice =?0;
do?{
slice = r.nextInt(length);
}?while?(slice ==?0);
if?(slice length /?2) {
for?(int?i =?0; i slice; i++) {
boolean?tmp = arr1[i];
arr1[i] = arr2[i];
arr2[i] = tmp;
}
}?else?{
for?(int?i = slice; i length; i++) {
boolean?tmp = arr1[i];
arr1[i] = arr2[i];
arr2[i] = tmp;
}
}
}
// 變異
public?void?mutation(boolean[] individual) {
int?length = individual.length;
Random r =?new?Random(System.currentTimeMillis());
individual[r.nextInt(length)] ^=?false;
}
// 輪盤法選擇下一代,并返回當(dāng)代最高的適應(yīng)度值
public?double?selection() {
boolean[][] next_generation =?new?boolean[population][];?// 下一代
int?length = gene_len * chrom_len;
for?(int?i =?0; i population; i++)
next_generation[i] =?new?boolean[length];
double[] cumulation =?new?double[population];
int?best_index =?0;
double?max_fitness = getFitness(individuals.get(best_index));
cumulation[0] = max_fitness;
for?(int?i =?1; i population; i++) {
double?fit = getFitness(individuals.get(i));
cumulation[i] = cumulation[i -?1] + fit;
// 尋找當(dāng)代的最優(yōu)個(gè)體
if?(fit max_fitness) {
best_index = i;
max_fitness = fit;
}
}
Random rand =?new?Random(System.currentTimeMillis());
for?(int?i =?0; i population; i++)
next_generation[i] = individuals.get(findByHalf(cumulation,
rand.nextDouble() * cumulation[population -?1]));
// 把當(dāng)代的最優(yōu)個(gè)體及其適應(yīng)度放到best_individual中
BI bi =?new?BI(max_fitness, individuals.get(best_index));
// printPath(individuals.get(best_index));
//System.out.println(max_fitness);
best_individual.add(bi);
// 新一代作為當(dāng)前代
for?(int?i =?0; i population; i++)
individuals.set(i, next_generation[i]);
return?max_fitness;
}
// 折半查找
public?int?findByHalf(double[] arr,?double?find) {
if?(find ?0?|| find ==?0?|| find arr[arr.length -?1])
return?-1;
int?min =?0;
int?max = arr.length -?1;
int?medium = min;
do?{
if?(medium == (min + max) /?2)
break;
medium = (min + max) /?2;
if?(arr[medium] find)
min = medium;
else?if?(arr[medium] find)
max = medium;
else
return?medium;
}?while?(min max);
return?max;
}
// 計(jì)算適應(yīng)度
public?double?getFitness(boolean[] individual) {
int?length = individual.length;
// 記錄當(dāng)前的位置,入口點(diǎn)是（1,0）
int?x =?1;
int?y =?0;
// 根據(jù)染色體中基因的指導(dǎo)向前走
for?(int?i =?0; i length; i++) {
boolean?b1 = individual[i];
boolean?b2 = individual[++i];
// 00向左走
if?(b1 ==?false? b2 ==?false) {
if?(x ?0? labyrinth.map[y][x -?1] ==?true) {
x--;
}
}
// 01向右走
else?if?(b1 ==?false? b2 ==?true) {
if?(x +?1? width labyrinth.map[y][x +?1] ==?true) {
x++;
}
}
// 10向上走
else?if?(b1 ==?true? b2 ==?false) {
if?(y ?0? labyrinth.map[y -?1][x] ==?true) {
y--;
}
}
// 11向下走
else?if?(b1 ==?true? b2 ==?true) {
if?(y +?1? height labyrinth.map[y +?1][x] ==?true) {
y++;
}
}
}
int?n = Math.abs(x - labyrinth.x_end) + Math.abs(y -labyrinth.y_end) +?1;
//????? if(n==1)
//????????? printPath(individual);
return?1.0?/ n;
}
// 運(yùn)行遺傳算法
public?boolean?run() {
// 初始化種群
initPopulation();
Random rand =?new?Random(System.currentTimeMillis());
boolean?success =?false;
while?(iter_limit-- ?0) {
// 打亂種群的順序
Collections.shuffle(individuals);
for?(int?i =?0; i population -?1; i +=?2) {
// 交叉
if?(rand.nextDouble() cross_ratio) {
cross(individuals.get(i), individuals.get(i +?1));
}
// 變異
if?(rand.nextDouble() muta_ratio) {
mutation(individuals.get(i));
}
}
// 種群更替
if?(selection() ==?1) {
success =?true;
break;
}
}
return?success;
}
//? public static void main(String[] args) {
//????? GA ga = new GA(8, 8);
//????? if (!ga.run()) {
//????????? System.out.println("沒(méi)有找到走出迷宮的路徑.");
//????? } else {
//????????? int gen = ga.best_individual.size();
//????????? boolean[] individual = ga.best_individual.get(gen - 1).indv;
//????????? System.out.println(ga.getPath(individual));
//????? }
//? }
// 根據(jù)染色體打印走法
public?String getPath(boolean[] individual) {
int?length = individual.length;
int?x =?1;
int?y =?0;
LinkedListString stack=new?LinkedListString();
for?(int?i =?0; i length; i++) {
boolean?b1 = individual[i];
boolean?b2 = individual[++i];
if?(b1 ==?false? b2 ==?false) {
if?(x ?0? labyrinth.map[y][x -?1] ==?true) {
x--;
if(!stack.isEmpty() stack.peek()=="右")
stack.poll();
else
stack.push("左");
}
}?else?if?(b1 ==?false? b2 ==?true) {
if?(x +?1? width labyrinth.map[y][x +?1] ==?true) {
x++;
if(!stack.isEmpty() stack.peek()=="左")
stack.poll();
else
stack.push("右");
}
}?else?if?(b1 ==?true? b2 ==?false) {
if?(y ?0? labyrinth.map[y -?1][x] ==?true) {
y--;
if(!stack.isEmpty() stack.peek()=="下")
stack.poll();
else
stack.push("上");
}
}?else?if?(b1 ==?true? b2 ==?true) {
if?(y +?1? height labyrinth.map[y +?1][x] ==?true) {
y++;
if(!stack.isEmpty() stack.peek()=="上")
stack.poll();
else
stack.push("下");
}
}
}
StringBuilder sb=new?StringBuilder(length/4);
IteratorString iter=stack.descendingIterator();
while(iter.hasNext())
sb.append(iter.next());
return?sb.toString();
}
}
代碼實(shí)現(xiàn)(Java)
1. 輸入
(1) 代表地圖二值二維數(shù)組(0表示可通路，1表示路障)
int[][] maps = {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }
};123456789123456789
(2) 按照二維數(shù)組的特點(diǎn)，坐標(biāo)原點(diǎn)在左上角，所以y是高，x是寬，y向下遞增，x向右遞增，我們將x和y封裝成一個(gè)類，好傳參，重寫(xiě)equals方法比較坐標(biāo)(x,y)是不是同一個(gè)。
public class Coord
{
public int x;
public int y;
public Coord(int x, int y)
{
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj)
{
if (obj == null) return false;
if (obj instanceof Coord)
{
Coord c = (Coord) obj;
return x == c.x y == c.y;
}
return false;
}
}12345678910111213141516171819202122231234567891011121314151617181920212223
(3) 封裝路徑結(jié)點(diǎn)類，字段包括：坐標(biāo)、G值、F值、父結(jié)點(diǎn)，實(shí)現(xiàn)Comparable接口，方便優(yōu)先隊(duì)列排序。
public class Node implements Comparable
{
public Coord coord; // 坐標(biāo)
public Node parent; // 父結(jié)點(diǎn)
public int G; // G：是個(gè)準(zhǔn)確的值，是起點(diǎn)到當(dāng)前結(jié)點(diǎn)的代價(jià)
public int H; // H：是個(gè)估值，當(dāng)前結(jié)點(diǎn)到目的結(jié)點(diǎn)的估計(jì)代價(jià)
public Node(int x, int y)
{
this.coord = new Coord(x, y);
}
public Node(Coord coord, Node parent, int g, int h)
{
this.coord = coord;
this.parent = parent;
G = g;
H = h;
}
@Override
public int compareTo(Node o)
{
if (o == null) return -1;
if (G + H o.G + o.H)
return 1;
else if (G + H o.G + o.H) return -1;
return 0;
}
}1234567891011121314151617181920212223242526272829303112345678910111213141516171819202122232425262728293031
(4) 最后一個(gè)數(shù)據(jù)結(jié)構(gòu)是A星算法輸入的所有數(shù)據(jù)，封裝在一起，傳參方便。:grin:
public class MapInfo
{
public int[][] maps; // 二維數(shù)組的地圖
public int width; // 地圖的寬
public int hight; // 地圖的高
public Node start; // 起始結(jié)點(diǎn)
public Node end; // 最終結(jié)點(diǎn)
public MapInfo(int[][] maps, int width, int hight, Node start, Node end)
{
this.maps = maps;
this.width = width;
this.hight = hight;
this.start = start;
this.end = end;
}
}12345678910111213141516171234567891011121314151617
2. 處理
(1) 在算法里需要定義幾個(gè)常量來(lái)確定：二維數(shù)組中哪個(gè)值表示障礙物、二維數(shù)組中繪制路徑的代表值、計(jì)算G值需要的橫縱移動(dòng)代價(jià)和斜移動(dòng)代價(jià)。
public final static int BAR = 1; // 障礙值
public final static int PATH = 2; // 路徑
public final static int DIRECT_VALUE = 10; // 橫豎移動(dòng)代價(jià)
public final static int OBLIQUE_VALUE = 14; // 斜移動(dòng)代價(jià)12341234
(2) 定義兩個(gè)輔助表：Open表和Close表。Open表的使用是需要取最小值，在這里我們使用Java工具包中的優(yōu)先隊(duì)列PriorityQueue，Close只是用來(lái)保存結(jié)點(diǎn)，沒(méi)其他特殊用途，就用ArrayList。
Queue openList = new PriorityQueue(); // 優(yōu)先隊(duì)列(升序)
List closeList = new ArrayList();1212
(3) 定義幾個(gè)布爾判斷方法：最終結(jié)點(diǎn)的判斷、結(jié)點(diǎn)能否加入open表的判斷、結(jié)點(diǎn)是否在Close表中的判斷。
/**
* 判斷結(jié)點(diǎn)是否是最終結(jié)點(diǎn)
*/
private boolean isEndNode(Coord end,Coord coord)
{
return coord != null end.equals(coord);
}
/**
* 判斷結(jié)點(diǎn)能否放入Open列表
*/
private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y)
{
// 是否在地圖中
if (x 0 || x = mapInfo.width || y 0 || y = mapInfo.hight) return false;
// 判斷是否是不可通過(guò)的結(jié)點(diǎn)
if (mapInfo.maps[y][x] == BAR) return false;
// 判斷結(jié)點(diǎn)是否存在close表
if (isCoordInClose(x, y)) return false;
return true;
}
/**
* 判斷坐標(biāo)是否在close表中
*/
private boolean isCoordInClose(Coord coord)
{
return coord!=nullisCoordInClose(coord.x, coord.y);
}
/**
* 判斷坐標(biāo)是否在close表中
*/
private boolean isCoordInClose(int x, int y)
{
if (closeList.isEmpty()) return false;
for (Node node : closeList)
{
if (node.coord.x == x node.coord.y == y)
{
return true;
}
}
return false;
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454612345678910111213141516171819202122232425262728293031323334353637383940414243444546
(4) 計(jì)算H值，“曼哈頓” 法，坐標(biāo)分別取差值相加
private int calcH(Coord end,Coord coord)
{
return Math.abs(end.x - coord.x) + Math.abs(end.y - coord.y);
}12341234
(5) 從Open列表中查找結(jié)點(diǎn)
private Node findNodeInOpen(Coord coord)
{
if (coord == null || openList.isEmpty()) return null;
for (Node node : openList)
{
if (node.coord.equals(coord))
{
return node;
}
}
return null;
}123456789101112123456789101112
(6) 添加鄰結(jié)點(diǎn)到Open表
/**
* 添加所有鄰結(jié)點(diǎn)到open表
*/
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current)
{
int x = current.coord.x;
int y = current.coord.y;
// 左
addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE);
// 上
addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE);
// 右
addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE);
// 下
addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE);
// 左上
addNeighborNodeInOpen(mapInfo,current, x - 1, y - 1, OBLIQUE_VALUE);
// 右上
addNeighborNodeInOpen(mapInfo,current, x + 1, y - 1, OBLIQUE_VALUE);
// 右下
addNeighborNodeInOpen(mapInfo,current, x + 1, y + 1, OBLIQUE_VALUE);
// 左下
addNeighborNodeInOpen(mapInfo,current, x - 1, y + 1, OBLIQUE_VALUE);
}
/**
* 添加一個(gè)鄰結(jié)點(diǎn)到open表
*/
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value)
{
if (canAddNodeToOpen(mapInfo,x, y))
{
Node end=mapInfo.end;
Coord coord = new Coord(x, y);
int G = current.G + value; // 計(jì)算鄰結(jié)點(diǎn)的G值
Node child = findNodeInOpen(coord);
if (child == null)
{
int H=calcH(end.coord,coord); // 計(jì)算H值
if(isEndNode(end.coord,coord))
{
child=end;
child.parent=current;
child.G=G;
child.H=H;
}
else
{
child = new Node(coord, current, G, H);
}
openList.add(child);
}
else if (child.G G)
{
child.G = G;
child.parent = current;
// 重新調(diào)整堆
openList.add(child);
}
}
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606112345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
(7) 回溯法繪制路徑
private void drawPath(int[][] maps, Node end)
{
if(end==null||maps==null) return;
System.out.println("總代價(jià)：" + end.G);
while (end != null)
{
Coord c = end.coord;
maps[c.y][c.x] = PATH;
end = end.parent;
}
}12345678910111234567891011
(8) 開(kāi)始算法，循環(huán)移動(dòng)結(jié)點(diǎn)尋找路徑，設(shè)定循環(huán)結(jié)束條件，Open表為空或者最終結(jié)點(diǎn)在Close表
public void start(MapInfo mapInfo)
{
if(mapInfo==null) return;
// clean
openList.clear();
closeList.clear();
// 開(kāi)始搜索
openList.add(mapInfo.start);
moveNodes(mapInfo);
}
/**
* 移動(dòng)當(dāng)前結(jié)點(diǎn)
*/
private void moveNodes(MapInfo mapInfo)
{
while (!openList.isEmpty())
{
if (isCoordInClose(mapInfo.end.coord))
{
drawPath(mapInfo.maps, mapInfo.end);
break;
}
Node current = openList.poll();
closeList.add(current);
addNeighborNodeInOpen(mapInfo,current);
}
}
單元和區(qū)域和數(shù)值，，，中的最大
重慶分公司
重慶分公司
