想請問一下 有關遊戲城市裡最常碰到的問題 我想請教依下有關最短路徑建置 也就是相關TSP問題 請各位高手給予幫助 有程式可以提供嗎 謝謝

引言: 想請問一下 有關遊戲城市裡最常碰到的問題 我想請教依下有關最短路徑建置 也就是相關TSP問題 請各位高手給予幫助 有程式可以提供嗎 謝謝

請問TSP的原名為何?是Trace Sortest Path嗎? 若要找最短路徑也可用Tree Trace再從中選節點(Node)數最少的Path即可! 若要範例,可否將問題更明確定義,比如給一個二維陣列Array當地圖... ～～～Delphi K.Top討論區站長～～～

traveling salesman problem 從原點出發，經過所有已知結點， 最後回到原點，但是反走過之結點不能重複走過， 求其最短路徑，麻煩告知一下。 謝謝站長大人

最常碰到的問題就是需要高手給予幫助解決困難...............

引言: 最常碰到的問題就是需要高手給予幫助解決困難...............

所謂高手只是相對的,一山還有一山高,但懂遊戲設計的高手確實不多, 又願意給予幫助解決困難的就少之又少, 我是覺得台灣的軟體設計師都很封閉,又把自己的作品當作寶貝, 應該大家分享共同成長,這也是本討論區的宗旨! 請網友多多發表作品,一同成長! ～～～Delphi K.Top討論區站長～～～

我想請教的問題 不是以TREE的角度去想， 而是以一種路徑的方式去看， 我自己有用JAVA寫出來 只是我希望能改成DELPHI... 我附檔上去... 請各位高手幫我一下... import java.applet.*; import java.awt.*; import java.awt.event.*; import javax.swing.*; import java.lang.reflect.*; import java.util.*; public class JAntColony extends Applet { boolean cityGenerated, antsTraveled, showPhMat; tsp myTsp; colony myColony; double averages[]; TextField textCity, textAnt, textVrate, textAmount, textRounds, textSeed; Label labelBestPath; Checkbox checkboxUseSeed; Button buttonGenerate, buttonGo, buttonShowPhMat; tspCanvas myCanvas; statCanvas myStatCanvas; //----------------------------------------------------------------- class bigLabel extends Canvas { public void paint(Graphics g) { g.setColor(new Color(185, 50, 0)); g.fill3DRect(0, 0, getSize().width, getSize().height - 4, true); g.setColor(Color.white); Font f = new Font("Serif", Font.BOLD, 14); g.setFont(f); String s = new String("JAnt Colony v1.0 by Roland Fox"); g.drawString(s, (getWidth() - g.getFontMetrics(f).stringWidth(s))/2 1, (getHeight() 12)/2 - 4); } } //----------------------------------------------------------------- class statCanvas extends Canvas { public void paint(Graphics g) { int w = getSize().width, h = getSize().height; g.setColor(Color.white); g.fill3DRect(0, 0, w, h, true); if (!cityGenerated) return; int n = Integer.parseInt( textRounds.getText() ); double minV = Double.MAX_VALUE, maxV = Double.MIN_VALUE; for(int i = 0; i < n; i ) { if (minV > averages[i]) minV = averages[i]; if (maxV < averages[i]) maxV = averages[i]; } double s = maxV - minV; g.setColor(Color.blue); int b = 298 / n, c; if (b < 1) b = 1; c = b; if (b > 1) c-=1; for(int i = 0; i < Math.min(w, n); i ) g.fillRect( i*b 1, h-1 - (int)((averages[i]-minV)/s*(h-2)), c, (int)((averages[i]-minV)/s*(h-2) 1)); } } //----------------------------------------------------------------- class tspCanvas extends Canvas { public void paint(Graphics g) { int w = getSize().width, h = getSize().height; g.setColor(Color.black); g.fillRect(0, 0, w, h); if (!cityGenerated) return; int n = myTsp.getNc(); g.setColor(Color.yellow); for(int i = 0; i < n; i ) { g.fill3DRect((int)(myTsp.city[i].x * w - 1), (int)(myTsp.city[i].y * h - 1), 3, 3, true); } if (showPhMat) { // find max and min of PhMat double minV = Double.MAX_VALUE, maxV = Double.MIN_VALUE; for(int i = 0; i < n-1; i ) for(int j = i 1; j < n; j ) { if (minV > myColony.phMat[i][j]) minV = myColony.phMat[i][j]; if (maxV < myColony.phMat[i][j]) maxV = myColony.phMat[i][j]; } double s = maxV - minV; for(int i = 0; i < n-1; i ) for(int j = i 1; j < n; j ) { float t = (float)((myColony.phMat[i][j] - minV) / s); g.setColor(new Color(t, t, t)); int x1 = (int)(myTsp.city[i].x * w); int y1 = (int)(myTsp.city[i].y * h); int x2 = (int)(myTsp.city[j].x * w); int y2 = (int)(myTsp.city[j].y * h); g.drawLine(x1, y1, x2, y2); } g.setColor(Color.yellow); for(int i = 0; i < n; i ) { g.fill3DRect((int)(myTsp.city[i].x * w - 1), (int)(myTsp.city[i].y * h - 1), 3, 3, true); } return; } if (!antsTraveled) return; g.setColor(Color.cyan); for(int i = 0; i < n - 1; i ) { int c1 = myColony.bestPath[i]; int c2 = myColony.bestPath[i 1]; int x1 = (int)(myTsp.city[c1].x * w); int y1 = (int)(myTsp.city[c1].y * h); int x2 = (int)(myTsp.city[c2].x * w); int y2 = (int)(myTsp.city[c2].y * h); g.drawLine(x1, y1, x2, y2); } int c1 = myColony.bestPath[n-1]; int c2 = myColony.bestPath[0]; int x1 = (int)(myTsp.city[c1].x * w); int y1 = (int)(myTsp.city[c1].y * h); int x2 = (int)(myTsp.city[c2].x * w); int y2 = (int)(myTsp.city[c2].y * h); g.drawLine(x1, y1, x2, y2); } } //----------------------------------------------------------------- class buttonAL implements ActionListener { public void actionPerformed(ActionEvent e) { if (e.getActionCommand() == "Go!") { //-------------------- labelBestPath.setBackground(Color.red); int n = Integer.parseInt( textRounds.getText() ); averages = new double[n]; for(int i = 0; i < n; i ) averages[i] = myColony.runOneCycle(); labelBestPath.setBackground(Color.yellow); antsTraveled = true; labelBestPath.setText( Double.toString( Math.rint( myColony.bestLength*10000 ) / 10000) ); myCanvas.paint(myCanvas.getGraphics()); myStatCanvas.paint(myStatCanvas.getGraphics()); buttonShowPhMat.setEnabled(true); } if (e.getActionCommand() == "Generate") { //-------------------- myTsp = new tsp(); if (checkboxUseSeed.getState()) myTsp.generateCitySet(Integer.parseInt(textCity.getText()), Long.parseLong(textSeed.getText())); else { long t = (new Date()).getTime(); myTsp.generateCitySet(Integer.parseInt(textCity.getText()), t); textSeed.setText(Long.toString(t)); } myColony = new colony( Integer.parseInt(textAnt.getText()), Double.parseDouble(textVrate.getText()), Double.parseDouble(textAmount.getText()), myTsp); cityGenerated = true; myCanvas.paint(myCanvas.getGraphics()); buttonGo.setEnabled(true); buttonShowPhMat.setEnabled(false); } if (e.getActionCommand() == "Show Ph Mat") { //------------------ showPhMat = true; myCanvas.paint(myCanvas.getGraphics()); ((Button)(e.getSource())).setLabel("Show Path"); showPhMat = false; } if (e.getActionCommand() == "Show Path") { //-------------------- myCanvas.paint(myCanvas.getGraphics()); ((Button)(e.getSource())).setLabel("Show Ph Mat"); } } } //----------------------------------------------------------------- public void init() { cityGenerated = false; antsTraveled = false; showPhMat = false; Panel panelRight = new Panel(new GridLayout(10, 2, 4, 4)); BorderLayout bl = new BorderLayout(); bl.setVgap(4); Panel panelLeft = new Panel(bl); Label labelCity = new Label("City", Label.RIGHT); Label labelAnt = new Label("Ant", Label.RIGHT); Label labelVrate = new Label("V Rate", Label.RIGHT); Label labelAmount = new Label("Ph Amt", Label.RIGHT); Label labelRounds = new Label("Rounds", Label.RIGHT); labelBestPath = new Label("0.0", Label.CENTER); labelBestPath.setBackground(Color.yellow); checkboxUseSeed = new Checkbox("Use Seed"); textCity = new TextField("30", 6); textAnt = new TextField("20", 6); textVrate = new TextField("0.95", 6); textAmount = new TextField("1", 6); textRounds = new TextField("40", 6); textSeed = new TextField("0", 6); buttonGenerate = new Button("Generate"); buttonGo = new Button("Go!"); buttonShowPhMat = new Button("Show Ph Mat"); buttonGo.setEnabled(false); buttonShowPhMat.setEnabled(false); buttonGenerate.addActionListener(new buttonAL()); buttonGo.addActionListener(new buttonAL()); buttonShowPhMat.addActionListener(new buttonAL()); panelRight.add(labelCity); panelRight.add(textCity); panelRight.add(labelAnt); panelRight.add(textAnt); panelRight.add(labelVrate); panelRight.add(textVrate); panelRight.add(labelAmount); panelRight.add(textAmount); panelRight.add(labelRounds); panelRight.add(textRounds); panelRight.add(checkboxUseSeed); panelRight.add(textSeed); panelRight.add(new Label()); panelRight.add(buttonGenerate); panelRight.add(new Label()); panelRight.add(buttonGo); panelRight.add(new Label()); panelRight.add(buttonShowPhMat); panelRight.add(new Label("Best Path", Label.RIGHT)); panelRight.add(labelBestPath); myCanvas = new tspCanvas(); myStatCanvas = new statCanvas(); myCanvas.setSize(300, 300); myStatCanvas.setSize(300, 50); panelLeft.add("Center", myCanvas); panelLeft.add("South", myStatCanvas); Panel panelMain = new Panel(); panelMain.add(panelLeft); panelMain.add(panelRight); bigLabel myLabel = new bigLabel(); myLabel.setSize(100, 24); Panel panelTop = new Panel(new BorderLayout()); panelTop.add("North", myLabel); panelTop.add("Center", panelMain); setBackground(new Color(100, 255, 100)); add(panelTop); } } class tsp { class node { double x, y; public node(double a, double b) { x = a; y = b; } public void setX(double t) { x = t; } public void setY(double t) { y = t; } public double getX() { return x; } public double getY() { return y; } } int nc; // number of cities public node city[]; double distMat[][]; public int getNc() { return nc; } //---------------------------------------- public void generateCitySet(int n, long s) { nc = n; Random r = new Random(s); city = new node[n]; for(int i = 0; i < n; i ) { city[i] = new node(r.nextDouble(), r.nextDouble()); } determineDistMat(); } //---------------------------------------- public void determineDistMat() { distMat = new double[nc][nc]; for(int i = 0; i < nc; i ) for(int j = i; j < nc; j ) { distMat[i][j] = dist(i, j); distMat[j][i] = dist(j, i); } } //---------------------------------------- public double dist(int i, int j) { double t1 = city[i].getX() - city[j].getX(), t2 = city[i].getY() - city[j].getY(); return Math.sqrt(t1*t1 t2*t2); } //---------------------------------------- public double pathLength(int p[]) { // note exception array_out_of_bound not caught double t = 0; for(int i = 0; i < nc - 1; i ) t = dist(p[i], p[i 1]); t = dist(p[nc-1], p[0]); return t; } //---------------------------------------- public double getDist(int i, int j) { return distMat[i][j]; } } class colony { public double phMat[][]; double phAmt; // pheromone amount each ant holds public int bestAnt; public int bestPath[]; public double bestLength; public ant myAnts[]; tsp myTsp; int na; // number of ants double vRate; // vaporization rate Random rg; //---------------------------------------- class ant { public int path[], mark[]; int currentCity; double traveledLength; public ant(int n) { mark = new int[n]; path = new int[n]; } public double getTraveledLength() { return traveledLength; } public double calculateTraveledLength() { traveledLength = myTsp.pathLength(path); return traveledLength; } public void reset() { currentCity = 0; path[0] = 0; // starts at city[0] for(int i = 0; i < myTsp.getNc(); i ) mark[i] = 0; mark[0] = 1; // the city[0] has been visited } //---------------------------------------- public void determineNextCity() { int n = myTsp.getNc(); int countCandi = 0; int[] candidate = new int[n]; double[] prCandi = new double[n]; for(int i = 0; i < n; i ) { if (mark[i] == 0) { candidate[countCandi] = i; prCandi[countCandi] = phMat[ path[currentCity] ][i] / myTsp.getDist( path[currentCity], i ); countCandi; } } // normalize prCandi double s = 0; for(int i = 0; i < countCandi; i ) s = prCandi[i]; for(int i = 0; i < countCandi; i ) prCandi[i] /= s; double hit = rg.nextDouble(), t = prCandi[0]; int w = 0; for(w = 0; w < countCandi - 1; w ) { if (t > hit) break; t = prCandi[w 1]; } currentCity; path[currentCity] = candidate[w]; mark[ candidate[w] ] = 1; } } //---------------------------------------- end of class ant public colony(int n, double t, double p, tsp s) { na = n; vRate = t; phAmt = p; myTsp = s; bestLength = Double.MAX_VALUE; bestPath = new int[myTsp.getNc()]; phMat = new double[myTsp.getNc()][myTsp.getNc()]; myAnts = new ant[n]; rg = new Random(); // (new Date()).getTime() for(int i = 0; i < n; i ) myAnts[i] = new ant(myTsp.getNc()); for(int i = 0; i < myTsp.getNc(); i ) for(int j = 0; j < myTsp.getNc(); j ) { phMat[i][j] = 1; phMat[j][i] = 1; } } //---------------------------------------- public void runOneAnt(int x) { myAnts[x].reset(); for(int i = 0; i < myTsp.getNc() - 1; i ) myAnts[x].determineNextCity(); myAnts[x].calculateTraveledLength(); } //---------------------------------------- public double runOneCycle() { for(int i = 0; i < na; i ) runOneAnt(i); return updatePhMat(); } //---------------------------------------- public double updatePhMat() { int n = Array.getLength( myAnts ); int m = myTsp.getNc(); double mean = 0; bestAnt = -1; for(int j = 0; j < myTsp.getNc(); j ) for(int k = 0; k < myTsp.getNc(); k ) phMat[j][k] *= vRate; for(int i = 0; i < n; i ) { double t = myAnts[i].getTraveledLength(); mean = t; if (t < bestLength) { bestAnt = i; bestLength = t; for(int j = 0; j < m; j ) bestPath[j] = myAnts[i].path[j]; } for(int j = 0; j < m - 1; j ) { phMat[ myAnts[i].path[j] ][ myAnts[i].path[j 1] ] = phAmt / t; phMat[ myAnts[i].path[j 1] ][ myAnts[i].path[j] ] = phAmt / t; } phMat[ myAnts[i].path[m-1] ][ myAnts[i].path[0] ] = phAmt / t; phMat[ myAnts[i].path[0] ][ myAnts[i].path[m-1] ] = phAmt / t; } return mean/n; } } 謝謝