算法题-遍历五个坐标的最短路径

心已赠人 2023-06-15 11:15 2阅读 0赞

**题目描述**

> 平原上，一群蜜蜂离开蜂巢采蜜，要连续采集5片花丛后归巢，已知5片花丛相对蜂巢的坐标，请你帮它们规划一下到访花儿的顺序，以使飞行总距离最短。

**输入描述**

以蜂巢为平面坐标原点的5片花丛A、B、C、D、E的坐标，坐标值为整数。

**输出描述**

从出发到返回蜂巢最短路径的长度取整值，取整办法为舍弃小数点后面的值。

> ### **示例** ###
> 
> **输入**
> 
> 200 0 200 10 200 50 200 30 200 25
> 
> **输出**
> 
> 456
> 
> **本解法思路**
> 
> 把问题当成全排列，使用回溯法遍历所有可能。（并不是最优解法）

import java.util.*;
    public class Main {
        public static int min = Integer.MAX_VALUE;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int[] xy = new int[10];
            while (in.hasNextInt()) {
                for(int i=0;i<10;i++){
                    xy[i] = in.nextInt();
                }
                Queue<Integer> queue = new LinkedList<>();
                help(0,xy,queue);
                System.out.println(min);
            }
    
        }
        public static void help(int i,int[] xy,Queue<Integer> queue){
            if(i>=xy.length-2){
                int x=0,y=0;
                double tempSum = 0.;
                queue.offer(xy[i]);
                queue.offer(xy[i+1]);
                int cnt = 5;
                while(!queue.isEmpty()){
                    int xx = queue.peek();
                    System.out.print("("+xx+",");
                    queue.poll();
                    int yy = queue.peek();
                    System.out.print(yy+"),");
                    queue.poll();
                    tempSum += Math.sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y)) ;
                    x = xx;y=yy;
                }
                tempSum += Math.sqrt((0-x)*(0-x)+(0-y)*(0-y));
                System.out.println("sum="+(int)tempSum);
                if((int)tempSum<min){
                    min = (int)tempSum;
                    return;
                }
            }else {
                for(int j=i;j<xy.length;j+=2){
                    swap(i,j,xy);
                    swap(i+1,j+1,xy);
                    Queue copyQueue = new LinkedList();
                    copyQueue.addAll(queue);
                    copyQueue.offer(xy[i]);
                    copyQueue.offer(xy[i+1]);
                    help(i+2,xy,copyQueue);
                    swap(i,j,xy);
                    swap(i+1,j+1,xy);
                }
            }
        }
        public static void swap(int i,int j,int[] xy){
            int temp = xy[i];
            xy[i] = xy[j];
            xy[j] = temp;
        }
    }

运行结果：

> (200,0),(200,10),(200,50),(200,30),(200,25),sum=476  
> (200,0),(200,10),(200,50),(200,25),(200,30),sum=482  
> (200,0),(200,10),(200,30),(200,50),(200,25),sum=476  
> (200,0),(200,10),(200,30),(200,25),(200,50),sum=466  
> (200,0),(200,10),(200,25),(200,30),(200,50),sum=456  
> (200,0),(200,10),(200,25),(200,50),(200,30),sum=472  
> (200,0),(200,50),(200,10),(200,30),(200,25),sum=516  
> (200,0),(200,50),(200,10),(200,25),(200,30),sum=512  
> (200,0),(200,50),(200,30),(200,10),(200,25),sum=506  
> (200,0),(200,50),(200,30),(200,25),(200,10),sum=490  
> (200,0),(200,50),(200,25),(200,30),(200,10),sum=500  
> (200,0),(200,50),(200,25),(200,10),(200,30),sum=512  
> (200,0),(200,30),(200,50),(200,10),(200,25),sum=506  
> (200,0),(200,30),(200,50),(200,25),(200,10),sum=490  
> (200,0),(200,30),(200,10),(200,50),(200,25),sum=516  
> (200,0),(200,30),(200,10),(200,25),(200,50),sum=496  
> (200,0),(200,30),(200,25),(200,10),(200,50),sum=496  
> (200,0),(200,30),(200,25),(200,50),(200,10),sum=500  
> (200,0),(200,25),(200,50),(200,30),(200,10),sum=490  
> (200,0),(200,25),(200,50),(200,10),(200,30),sum=512  
> (200,0),(200,25),(200,30),(200,50),(200,10),sum=490  
> (200,0),(200,25),(200,30),(200,10),(200,50),sum=496  
> (200,0),(200,25),(200,10),(200,30),(200,50),sum=486  
> (200,0),(200,25),(200,10),(200,50),(200,30),sum=502  
> (200,10),(200,0),(200,50),(200,30),(200,25),sum=486  
> (200,10),(200,0),(200,50),(200,25),(200,30),sum=492  
> (200,10),(200,0),(200,30),(200,50),(200,25),sum=486  
> (200,10),(200,0),(200,30),(200,25),(200,50),sum=476  
> (200,10),(200,0),(200,25),(200,30),(200,50),sum=466  
> (200,10),(200,0),(200,25),(200,50),(200,30),sum=482  
> (200,10),(200,50),(200,0),(200,30),(200,25),sum=526  
> (200,10),(200,50),(200,0),(200,25),(200,30),sum=522  
> (200,10),(200,50),(200,30),(200,0),(200,25),sum=516  
> (200,10),(200,50),(200,30),(200,25),(200,0),sum=490  
> (200,10),(200,50),(200,25),(200,30),(200,0),sum=500  
> (200,10),(200,50),(200,25),(200,0),(200,30),sum=522  
> (200,10),(200,30),(200,50),(200,0),(200,25),sum=516  
> (200,10),(200,30),(200,50),(200,25),(200,0),sum=490  
> (200,10),(200,30),(200,0),(200,50),(200,25),sum=526  
> (200,10),(200,30),(200,0),(200,25),(200,50),sum=506  
> (200,10),(200,30),(200,25),(200,0),(200,50),sum=506  
> (200,10),(200,30),(200,25),(200,50),(200,0),sum=500  
> (200,10),(200,25),(200,50),(200,30),(200,0),sum=490  
> (200,10),(200,25),(200,50),(200,0),(200,30),sum=522  
> (200,10),(200,25),(200,30),(200,50),(200,0),sum=490  
> (200,10),(200,25),(200,30),(200,0),(200,50),sum=506  
> (200,10),(200,25),(200,0),(200,30),(200,50),sum=496  
> (200,10),(200,25),(200,0),(200,50),(200,30),sum=512  
> (200,50),(200,10),(200,0),(200,30),(200,25),sum=492  
> (200,50),(200,10),(200,0),(200,25),(200,30),sum=488  
> (200,50),(200,10),(200,30),(200,0),(200,25),sum=522  
> (200,50),(200,10),(200,30),(200,25),(200,0),sum=496  
> (200,50),(200,10),(200,25),(200,30),(200,0),sum=496  
> (200,50),(200,10),(200,25),(200,0),(200,30),sum=518  
> (200,50),(200,0),(200,10),(200,30),(200,25),sum=492  
> (200,50),(200,0),(200,10),(200,25),(200,30),sum=488  
> (200,50),(200,0),(200,30),(200,10),(200,25),sum=522  
> (200,50),(200,0),(200,30),(200,25),(200,10),sum=506  
> (200,50),(200,0),(200,25),(200,30),(200,10),sum=506  
> (200,50),(200,0),(200,25),(200,10),(200,30),sum=518  
> (200,50),(200,30),(200,0),(200,10),(200,25),sum=482  
> (200,50),(200,30),(200,0),(200,25),(200,10),sum=496  
> (200,50),(200,30),(200,10),(200,0),(200,25),sum=482  
> (200,50),(200,30),(200,10),(200,25),(200,0),sum=486  
> (200,50),(200,30),(200,25),(200,10),(200,0),sum=456  
> (200,50),(200,30),(200,25),(200,0),(200,10),sum=466  
> (200,50),(200,25),(200,0),(200,30),(200,10),sum=506  
> (200,50),(200,25),(200,0),(200,10),(200,30),sum=488  
> (200,50),(200,25),(200,30),(200,0),(200,10),sum=476  
> (200,50),(200,25),(200,30),(200,10),(200,0),sum=466  
> (200,50),(200,25),(200,10),(200,30),(200,0),sum=496  
> (200,50),(200,25),(200,10),(200,0),(200,30),sum=488  
> (200,30),(200,10),(200,50),(200,0),(200,25),sum=538  
> (200,30),(200,10),(200,50),(200,25),(200,0),sum=512  
> (200,30),(200,10),(200,0),(200,50),(200,25),sum=508  
> (200,30),(200,10),(200,0),(200,25),(200,50),sum=488  
> (200,30),(200,10),(200,25),(200,0),(200,50),sum=518  
> (200,30),(200,10),(200,25),(200,50),(200,0),sum=512  
> (200,30),(200,50),(200,10),(200,0),(200,25),sum=498  
> (200,30),(200,50),(200,10),(200,25),(200,0),sum=502  
> (200,30),(200,50),(200,0),(200,10),(200,25),sum=498  
> (200,30),(200,50),(200,0),(200,25),(200,10),sum=512  
> (200,30),(200,50),(200,25),(200,0),(200,10),sum=482  
> (200,30),(200,50),(200,25),(200,10),(200,0),sum=472  
> (200,30),(200,0),(200,50),(200,10),(200,25),sum=538  
> (200,30),(200,0),(200,50),(200,25),(200,10),sum=522  
> (200,30),(200,0),(200,10),(200,50),(200,25),sum=508  
> (200,30),(200,0),(200,10),(200,25),(200,50),sum=488  
> (200,30),(200,0),(200,25),(200,10),(200,50),sum=518  
> (200,30),(200,0),(200,25),(200,50),(200,10),sum=522  
> (200,30),(200,25),(200,50),(200,0),(200,10),sum=492  
> (200,30),(200,25),(200,50),(200,10),(200,0),sum=482  
> (200,30),(200,25),(200,0),(200,50),(200,10),sum=522  
> (200,30),(200,25),(200,0),(200,10),(200,50),sum=488  
> (200,30),(200,25),(200,10),(200,0),(200,50),sum=488  
> (200,30),(200,25),(200,10),(200,50),(200,0),sum=512  
> (200,25),(200,10),(200,50),(200,30),(200,0),sum=506  
> (200,25),(200,10),(200,50),(200,0),(200,30),sum=538  
> (200,25),(200,10),(200,30),(200,50),(200,0),sum=506  
> (200,25),(200,10),(200,30),(200,0),(200,50),sum=522  
> (200,25),(200,10),(200,0),(200,30),(200,50),sum=482  
> (200,25),(200,10),(200,0),(200,50),(200,30),sum=498  
> (200,25),(200,50),(200,10),(200,30),(200,0),sum=516  
> (200,25),(200,50),(200,10),(200,0),(200,30),sum=508  
> (200,25),(200,50),(200,30),(200,10),(200,0),sum=476  
> (200,25),(200,50),(200,30),(200,0),(200,10),sum=486  
> (200,25),(200,50),(200,0),(200,30),(200,10),sum=526  
> (200,25),(200,50),(200,0),(200,10),(200,30),sum=508  
> (200,25),(200,30),(200,50),(200,10),(200,0),sum=476  
> (200,25),(200,30),(200,50),(200,0),(200,10),sum=486  
> (200,25),(200,30),(200,10),(200,50),(200,0),sum=516  
> (200,25),(200,30),(200,10),(200,0),(200,50),sum=492  
> (200,25),(200,30),(200,0),(200,10),(200,50),sum=492  
> (200,25),(200,30),(200,0),(200,50),(200,10),sum=526  
> (200,25),(200,0),(200,50),(200,30),(200,10),sum=516  
> (200,25),(200,0),(200,50),(200,10),(200,30),sum=538  
> (200,25),(200,0),(200,30),(200,50),(200,10),sum=516  
> (200,25),(200,0),(200,30),(200,10),(200,50),sum=522  
> (200,25),(200,0),(200,10),(200,30),(200,50),sum=482  
> (200,25),(200,0),(200,10),(200,50),(200,30),sum=498  
> 456