专门学设计的网站,芜湖效能建设网站,为什么做网站要用谷歌浏览器,广东网站建设推荐基站维修工程师#xff08;200分#xff09;
小王是一名基站维护工程师#xff0c;负责某区域的基站维护。 某地方有n个基站(1n10)#xff0c;已知各基站之间的距离s(0s500)#xff0c;并且基站x到基站y的距离#xff0c;与基站y到基站x的距离并不一定会…基站维修工程师200分
小王是一名基站维护工程师负责某区域的基站维护。 某地方有n个基站(1n10)已知各基站之间的距离s(0s500)并且基站x到基站y的距离与基站y到基站x的距离并不一定会相同。
小王从基站1出发途径每个基站1次然后返回基站1需要请你为他选择一条距离最短的路线。
输入描述 站点数n和各站点之间的距离(均为整数)。如: 3 {站点数}
0 2 1 {站点1到各站点的路程)
1 0 2 (站点2到各站点的路程}
2 1 0 {站点3到各站点的路程} 输出描述 最短路程的数值 示例1 输入 3
0 2 1
1 0 2
2 1 0 输出 3 思路
目标是解决典型的旅行商问题TSP, Travelling Salesman Problem即在一个给定的城市网络中找到一条从起点城市出发经过每个城市一次并最终返回起点的路径使得路径的总距离最短。算法使用了递归深度优先搜索结合状态标记来遍历所有可能的路径并通过回溯法不断比较最短路径。 输入给定一个 size x size 的二维数组 arr其中 arr[i][j] 表示城市 i 到城市 j 的距离。 输出求解从城市0出发经过每个城市一次并返回的最短路径长度。
步骤:数据输入读取城市数 size 和城市之间的距离矩阵 arr。 递归函数 recur递归尝试从一个城市访问未访问过的下一个城市记录当前路径长度并使用状态数组 st 标记某个城市是否已经访问过。 状态回溯递归探索完某条路径后返回上一步尝试其他未访问过的城市最终比较得到最短路径。 结果输出输出所有路径中的最小总距离。
代码段如下
package com.rich.huawei.od_test;import java.util.Scanner;/*** description* Title Test01* Author tang rui qi* Date 2024/10/14 5:17*/
public class Test03 {static int res; // 用于保存最短路径的总距离// 递归函数// u: 当前访问的第几个城市// pre: 上一个访问的城市编号// temRes: 当前路径的总距离// size: 城市的总数// arr: 城市之间的距离矩阵// st: 访问状态数组标记某个城市是否被访问过static void recur(int u, int pre, int temRes, int size, int[][] arr, boolean[] st) {// 如果已经访问完所有城市并回到起点城市if (u size - 1) {// 将当前路径的总距离与最小距离进行比较更新最小距离res Math.min(res, temRes arr[pre][0]);return;}// 遍历每个城市寻找下一个未访问过的城市for (int i 1; i size; i) {if (st[i]) { // 如果该城市已被访问则跳过continue;}st[i] true; // 标记该城市为已访问// 递归访问下一个城市并累加当前路径的距离recur(u 1, i, temRes arr[pre][i], size, arr, st);st[i] false; // 回溯时将该城市重置为未访问状态}}public static void main(String[] args) {Scanner cin new Scanner(System.in);int size cin.nextInt(); // 读取城市的总数res 0x3f3f3f3f; // 初始化最短路径为一个很大的值int[][] arr new int[size][size]; // 城市之间的距离矩阵boolean[] st new boolean[size]; // 访问状态数组// 读取距离矩阵的值for (int x 0; x size; x)for (int y 0; y size; y) arr[x][y] cin.nextInt();// 从城市0开始递归搜索recur(0, 0, 0, size, arr, st);// 输出最短路径的总距离System.out.println(res);}}
