华为OD机试2024年真题（基站维修工程师）

基站维修工程师（200分）

小王是一名基站维护工程师，负责某区域的基站维护。
某地方有n个基站(1<n<10)，已知各基站之间的距离s(0<s<500)，并且基站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);
    }


}

原文地址：https://blog.csdn.net/qq_45151158/article/details/143065468

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！