思路

  1. 優化枚舉法
  2. 如果過程當中已經超過預期時數則馬上結束不再做運算

實作

測試方法

import java.util.ArrayList;
import java.util.List;

public class Travelplan_backtracking_new {
    Integer[][] hours;

    // 配置國家
    String[] c_remained = new String[]{"NP", "IS", "CA", "UK", "US"}; //5

    // 測試案例
    public static void main(String[] args) {
        Travelplan_backtracking_new tp = new Travelplan_backtracking_new();
        tp.build_hour_table();
        Integer hour_constraint = 60; // 65 ~ 100, 目標低於這個時數
        tp.backtracking(hour_constraint);
    }

    // 建立行程時間
    private void build_hour_table() {
        // NP: 0 (North Pole)
        // IS: 1
        // CA: 2
        // UK: 3
        // US: 4

        this.hours = new Integer[5][5];
        hours[0][0] = 0;     // NP -> NP
        hours[0][1] = 14;    // NP -> IS
        hours[0][2] = 15;    // NP -> CA
        hours[0][3] = 17;    // NP -> UK
        hours[0][4] = 16;    // NP -> US

        hours[1][0] = 14;    // IS -> NP
        hours[1][1] = 0;     // IS -> IS
        hours[1][2] = 24;    // IS -> CA
        hours[1][3] = 8;     // IS -> UK
        hours[1][4] = 36;    // IS -> US

        hours[2][0] = 15;    // CA -> NP
        hours[2][1] = 24;    // CA -> IS
        hours[2][2] = 0;     // CA -> CA
        hours[2][3] = 34;    // CA -> UK
        hours[2][4] = 4;     // CA -> US

        hours[3][0] = 17;    // UK -> NP
        hours[3][1] = 8;     // UK -> IS
        hours[3][2] = 34;    // UK -> CA
        hours[3][3] = 0;     // UK -> UK
        hours[3][4] = 30;    // UK -> US

        hours[4][0] = 16;    // US -> NP
        hours[4][1] = 36;    // US -> IS
        hours[4][2] = 4;     // US -> CA
        hours[4][3] = 30;    // US -> UK
        hours[4][4] = 0;     // US -> US
    }

    // 查詢方法
    public Integer get_hour(String start, String end) {
        Integer x = get_index(start);
        Integer y = get_index(end);
        return this.hours[x][y];
    }

    // 定義
    private Integer get_index(String str){
        if (str.equals("NP")) return 0;
        if (str.equals("IS")) return 1;
        if (str.equals("CA")) return 2;
        if (str.equals("UK")) return 3;
        if (str.equals("US")) return 4;

        return null;
    }

具體

// 設定行程陣列
List<String> route = new ArrayList<>();
/** enumeration -> backtracking **/
public void backtracking(Integer hour_constraint) {
    String start_country = "NP"; // 從北極為起點出發
    route.add(start_country); // 加入開始城鎮
    c_remained[0] = null; // 去掉開始城鎮

    backtracking_recursion(hour_constraint); // 進入遞迴並開始跑每一個可能性
}

private void backtracking_recursion(Integer hour_constraint) {
    if (route.size() == 5) { //所有國家都去過了
        // get a complete trip plan
        int hour_total = get_hour_total(); //取得總航行時數
        if (hour_total < hour_constraint) { // 小於最低要求
            print_result(hour_total, route);
        }else{
            System.out.print("[X]:");
            print_result(hour_total, route);
        }
        return;
    } else { // backtracking 關鍵點
            /** backtracking **/
            int hour_total = get_hour_total();
            // 在過程中如果發現當前時數已經超過,則直接結束不再做運算
            if (hour_total >= hour_constraint) {
                System.out.print("(backtracked) ");
                print_result(hour_total, route);
                return;
            }
        }

    /** step01: just pick any child to continue each round **/
    // 開始探查每個國家拜訪時數
    for (int i = 0; i < c_remained.length; i++) {
        if (c_remained[i] == null) continue; // 如果已經去過則跳過
        String c_next = c_remained[i]; // 設定前往的下一個國家

        // take out
        route.add(c_next); // 加入前往國家
        c_remained[i] = null; // 將其配置成 null 表示已經前往過了

        /** next round **/
        backtracking_recursion(hour_constraint); // 遞迴繼續

        // 全部執行完之後
        // give back
        route.remove(c_next); //移除已經去過的國家
        c_remained[i] = c_next; //把移除的國家補回去
    }
}

// 取得總航行時數
private int get_hour_total() {
    if (route.size() == 0) return 0;
    int hour_total = 0;
    String start = route.get(0); //開始國家 直接取第一個
    String end = null; //結束國家
    for (int i = 1; i < route.size(); i++) {
        end = route.get(i);
        hour_total += get_hour(start, end);

        start = end; // 把開始國家更新成結束國家 NP<first> -> IS<updated> -> US
    }
    return hour_total;
}

private void print_result(int hour_total, List<String> route) {
    for (int i = 0; i < route.size(); i++) {
        System.out.print(route.get(i));
        if (i + 1 == route.size()) break; //最後一個不要加入 ->
        System.out.print("->");
    }

    System.out.println(" : " + hour_total);
}