Einfaches hill-climbing-Algorithmus?

Ich versuche, den Einfachen hill-climbing-Algorithmus zur Lösung des travelling salesman problem. Erstellen Sie ein Java-Programm, dies zu tun. Ich weiß, es ist nicht die beste, jedoch möchte ich hauptsächlich, um zu sehen, die Ergebnisse und vergleichen Sie anschließend die Ergebnisse mit den folgenden, die ich auch erstellen:

  • Stochastische Hill-Climber
  • Random-Restart Hill-Climber
  • Simulated Annealing.

Sowieso zurück zu den einfachen hill-climbing-Algorithmus habe ich bereits diese:

import java.util.*;
public class HCSA 
{
    static private Random rand; 
    static public void main(String args[])
    {
        for(int i=0;i<10;++i) System.out.println(UR(3,4));
    }
    static public double UR(double a,double b)
    {
        if (rand == null) 
        {
            rand = new Random();
            rand.setSeed(System.nanoTime());
        }
        return((b-a)*rand.nextDouble()+a);
    }
}

Ist das alles, was ich brauche? Ist dieser code auch richtig..? Ich habe eine Reihe von verschiedenen Datensätze in text-Dokumente, die ich will, das Programm zu Lesen und dann Ergebnisse produzieren.

Würde wirklich zu schätzen jede Hilfe bei diesem.

- - - - - - EDIT - - - - -

Ich war ein idiot und öffnete die Java-Datei direkt in Eclipse, wenn ich sollte Sie öffnen im Editor erstmal.. hier ist der code den ich nun habe.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.util.ArrayList;

{
    //Print a 2D double array to the console Window
    static public void PrintArray(double x[][])
    {
        for(int i=0;i<x.length;++i)
        {
            for(int j=0;j<x[i].length;++j)
            {
                System.out.print(x[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
    //reads in a text file and parses all of the numbers in it
    //is for reading in a square 2D numeric array from a text file
    //This code is not very good and can be improved!
    //But it should work!!!
    //'sep' is the separator between columns
    static public double[][] ReadArrayFile(String filename,String sep)
    {
        double res[][] = null;
        try
        {
            BufferedReader input = null;
            input = new BufferedReader(new FileReader(filename));
            String line = null;
            int ncol = 0;
            int nrow = 0;

            while ((line = input.readLine()) != null) 
            {
                ++nrow;
                String[] columns = line.split(sep);
                ncol = Math.max(ncol,columns.length);
            }
            res = new double[nrow][ncol];
            input = new BufferedReader(new FileReader(filename));
            int i=0,j=0;
            while ((line = input.readLine()) != null) 
            {

                String[] columns = line.split(sep);
                for(j=0;j<columns.length;++j)
                {
                    res[i][j] = Double.parseDouble(columns[j]);
                }
                ++i;
            }
        }
        catch(Exception E)
        {
            System.out.println("+++ReadArrayFile: "+E.getMessage());
        }
        return(res);
    }
    //This method reads in a text file and parses all of the numbers in it
    //This code is not very good and can be improved!
    //But it should work!!!
    //It takes in as input a string filename and returns an array list of Integers
    static public ArrayList<Integer> ReadIntegerFile(String filename)
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Reader r;
        try
        {
            r = new BufferedReader(new FileReader(filename));
            StreamTokenizer stok = new StreamTokenizer(r);
            stok.parseNumbers();
            stok.nextToken();
            while (stok.ttype != StreamTokenizer.TT_EOF) 
            {
                if (stok.ttype == StreamTokenizer.TT_NUMBER)
                {
                    res.add((int)(stok.nval));
                }
                stok.nextToken();
            }
        }
        catch(Exception E)
        {
            System.out.println("+++ReadIntegerFile: "+E.getMessage());
        }
        return(res);
    }
}
  • "Ist dieser code auch richtig.. ?" -- der richtige für was? Ich kann nicht sehen, hill climbing Algorithmus in es. Außerdem würde ich nur initialisieren rand innen main() und loszuwerden, den test innerhalb UR().
  • Gut für den Gang durch ein paar Datensätze mit dem hill climbing Algorithmus. Die datasets, die als tour-Strecken. Wie es aussieht nicht, was ich dachte, es Tat. Etwas verwirrt jetzt. Danke für den anderen Tipp.
  • Gerade festgestellt, dass die Beschreibung für den java-snippet oben geschrieben "drei Methoden in eine TSP-java-Klasse, zum Lesen in ein array (Stadt Entfernung-Datei), drucken Sie ein array und lese in einer tour-Datei (integer-Liste-Datei)." Bin ich etwas fehlt?
  • Simulated Annealing wird ziemlich schwer zu bekommen Recht (und einfach falschen). Werfen Sie einen Blick auf die Quellcode von Drools Planner (java, open source)
  • Ist das, was ich oben eigentlich eine einfache hill climb-Algorithmus? Ich Suche simulated annealing ein wenig später, aber ich kann nicht sogar das noch..
InformationsquelleAutor RED_ | 2011-03-15
Schreibe einen Kommentar