BruteForceGuilherme.java.zip

  • PUDN用户
    了解作者
  • Java
    开发工具
  • 1KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 2
    下载次数
  • 2009-08-20 01:06
    上传日期
Brute force solution for the traveling salesman problem
BruteForceGuilherme.java.zip
  • BruteForceGuilherme.java
    4.2KB
内容介绍
import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.HashMap; import java.util.Map; public class BruteForceGuilherme { //public static final int MAX_VERTICES = 60; public static final int WHITE_COLOR = 0; public static final int GRAY_COLOR = 1; public static final int BLACK_COLOR = 2; public static final int INT_MAX = 2147483647; private Map<Integer, int[]> Graph = new HashMap<Integer, int[]>(); private int NumVertices; private int GraphDelta = 0; private long GraphTotal; private int Visited; private int[] Path;// = new int[MAX_VERTICES]; private int[] VertColor;// = new int[MAX_VERTICES]; private long MinGraphTotal; private int[] MinPath;// = new int[MAX_VERTICES]; public BruteForceGuilherme (String FName) { int i = 0; initializeGraph(new File(FName)); for (i=0;i<NumVertices;i++) { VertColor[i] = WHITE_COLOR; } MinGraphTotal = INT_MAX; VertColor[0] = GRAY_COLOR; Visited = 1; GraphTotal = 0; RecursiveBFGuilherme(); } public void RecursiveBFGuilherme () { int u = Path[Visited - 1]; int v; int[] aux = new int[NumVertices];; // Loop para procurar o proximo vertice for (v = 0; v < NumVertices; v++) { if (VertColor[v] != WHITE_COLOR) continue; VertColor[v] = GRAY_COLOR; Path[Visited] = v; aux = Graph.get(u); GraphTotal += aux[v]; //Todos os vertices ja foram visitados? if (Visited == (NumVertices - 1)) { aux = Graph.get(v); GraphTotal = GraphTotal + aux[Path[0]]; // Checa distancia minima if (MinGraphTotal > GraphTotal) { MinGraphTotal = GraphTotal; MinPath = Path.clone(); } // Ainda ha vertices setados em branco } else { Visited++; //Recursao RecursiveBFGuilherme(); Visited--; } GraphTotal -= Graph.get(u)[v]; // Seta a cor do vertice em branco VertColor[v] = WHITE_COLOR; } } //Le o grafo to arquivo e o insere num Hash public void initializeGraph(File text) { BufferedReader in; String str; String[] tempStr = null; int i,j; try { in = new BufferedReader(new FileReader(text)); str = in.readLine(); NumVertices = Integer.parseInt(str); int[] tempInt = new int[NumVertices]; Path = new int[NumVertices]; VertColor = new int[NumVertices]; MinPath = new int[NumVertices]; for (j=0;j<NumVertices;j++) { for (i=0;i<(NumVertices-1);i++) { str = in.readLine(); tempStr = str.split(" "); tempInt[Integer.parseInt(tempStr[1])] = Integer.parseInt(tempStr[2]); if (Integer.parseInt(tempStr[2]) > GraphDelta) GraphDelta = Integer.parseInt(tempStr[2]); } tempInt[Integer.parseInt(tempStr[0])] = 0; Graph.put(Integer.parseInt(tempStr[0]),tempInt); tempInt = new int[NumVertices]; } in.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } // Imprime o caminho public void printMinPath() { int i; for (i = 0; i < NumVertices; i++) { System.out.println(MinPath[i]); } System.out.println(MinGraphTotal); } public static void main(String[] args) { if (args.length < 1) { System.out.println ("Not enough arguments!!! java BruteForceGuilherme [inputFile]"); System.exit(0); } String FName = args[0]; BruteForceGuilherme TSP = new BruteForceGuilherme (FName); TSP.printMinPath(); } }
评论
    相关推荐
    • tsp_dp1.zip
      traveling salesman problem - brute search algorithm
    • tsp-brute-force.zip
      Traveling Salesman problem
    • traveling-salesman-prolem.rar
      In this paper I will discuss a genetic approach to &#... Lastly, I will discuss the diffi culties in creating a program to fi nd near-optimal solutions to asymmetric traveling salesman problems.
    • VRPC_OR_tool:具有容量限制的车辆路径问题-使用Google ORtools
      多目标优化(MOO)| 数据科学优化| 车辆路线 问题 :delivery_truck: 在这篇文章中,我将解释并实施具有需求和容量约束的VRP 什么是车辆路径问题? 车辆路线图示 车辆路线选择问题是组合优化和整数规划问题,它问...
    • qatsp:旅行商问题的量子退火
      qatsp软件包 用R语言执行的旅行推销员问题的量子退火。 描述 旅行推销员问题(TSP)是一组城市和每两个城市之间的距离的组合,通过一次环游所有城市并返回出发地的旅行,找到总旅行距离最小的城市优化问题。...
    • Genetic-Salesman-Challenge:算法挑战我挑战别人并展示了一个关于性能的小案例研究
      首先作为一个快速说明,我并不声称已经编写了这个算法问题。 我添加到作业的原始表格中以使其更加直观,并为其他感兴趣的个人重新托管。 这个问题的最初创造者是 。 几个实现的前言、解释和性能可以在找到 ...
    • sommatlab代码-PortfolioMichielMaas16136640:投资组合MichielMaas16136640
      som matlab代码Portfolio Michiel Maas-16136640-达能电厂 数据营 我已经完成了所有必需的Datacamp作业。 。 我在HBO-ICT的较早部分:软件工程培训中做了所有这些精确的任务。...这就是为什么它很无聊的原因,我冲了...
    • Salesman:遗传(类似)方法解决旅行商问题
      ./salesman.exe 已知的问题 SDL2 v2.0.10会导致绘制错误:渲染某些内容会更改最后绘制的对象的特定像素的颜色。 但是,此错误在2.0.8和2.0.14版本中不存在。 如果出现这种情况,请卸载libsdl2-dev软件包,然后安装...
    • Travelling-Salesman-Problem-Solver:一个可扩展的 API,用于使用内置策略(包括蛮力、最近邻、
      旅行商问题 (TSP) 求解器 ##Introduciton 这是一个可扩展的 API,用于在 Java 中对 TSP 进行建模,并通过内置策略或用户编写的扩展策略来解决它。 目前内置的策略有: 蛮力 最近的邻居 最远插入 ...
    • BBS_system_on_java.rar
      BBS论坛系统由JAVA和JSP实现,开发中涉及JavaBean,JSP和服务器Tomcat5.0.7的设置,数据库用SQL2000。有注册登陆,浏览,发帖 回帖,帖子管理,论坛设置,管理版块,用户管理等模块。