如何在不使多線程的情況下使速度更快？

Question

我的程序在輸出方面工作正常，但對於我的一些測試用例來說，找到答案需要很長時間（有時需要18秒）。我想知道如何改善我的代碼的性能。我的代碼是： 這是Pebble Solitaire。用戶輸入n個遊戲，然後輸入長度爲23的字符串，其中只包含'o'（鵝卵石）和' - '（空白空間）的組合。如果有兩個相鄰的鵝卵石和任何一邊有空的空間，即（oo-或-oo），則移除中間的鵝卵石，並將另外兩塊彼此交換，如果「oo-」變成「 O」。

我目前的做法幾乎是一個詳盡的方法，它嘗試每一個可能的舉措，並結果移動設置與剩下的卵石數量最少。

我想知道如何改進這個解決方案，而不使它成爲多線程。

以下是我有：

package Pebble; 

import java.util.Scanner; 

public class PebbleSolitaire { 

    public static void main(String[] args){ 

     Scanner input = new Scanner(System.in); 
     int numOfGames = Integer.parseInt(input.nextLine()); 

     while (numOfGames > 0){ 

      char[] values = input.nextLine().toCharArray(); 
      long startTime = System.nanoTime(); 
      System.out.println(solve(values)); 
      System.out.println("Time to finish in ms: " + (System.nanoTime() - startTime)/1000000); 
      numOfGames--; 
     } 
     input.close(); 
    } 

    private static int solve(char[] game){ 

     if(game != null && game.length == 0){ 
      return -1; 
     } 

     int result = 0; 

     for (int i = 0; i < game.length; i++){ 
      if(game[i] == 'o'){ 
       result++; 
      } 
     } 

     //print(game); 

     for (int i = 0; i < game.length; i++){ 

      char[] temp = new char[game.length]; 
      copyArray(temp, game); 

      if (i-2 >= 0 && temp[i] == '-' && temp[i-2] == 'o' && temp[i-1] == 'o'){//move pebble forwards 
       temp[i-1] = temp[i-2] = '-'; 
       temp[i] = 'o'; 
       result = Math.min(result, solve(temp)); 
      } 

      copyArray(temp, game); 

      if(i+2 < temp.length && temp[i] == '-' && temp[i+1] == 'o' && temp[i+2] == 'o'){//move pebble backwards 
       temp[i+1] = temp[i+2] = '-'; 
       temp[i] = 'o'; 
       result = Math.min(result, solve(temp)); 
      } 
     } 
     return result; 
    } 

    private static void copyArray(char[] copy, char[] og){ 
     for(int x = 0; x < copy.length; x++){ 
      copy[x] = og[x]; 
     } 
    } 
    private static void print(char[] c){ 
     for(char ch: c){ 
      System.out.print(ch); 
     } 
     System.out.println(); 
    } 
} 

我的樣品輸入和輸出：

2 
-o----ooo----o----ooo-- 
6 
Time to finish in ms: 0 
oooooooooo-ooooooooooo- 
4 
Time to finish in ms: 18149 

編輯：會使得這種完全迭代大大提高性能？

Answer 1

也許你可以改善這種單方面：

for (int i = 0; i < game.length; i++){ 

     char[] temp = new char[game.length]; 
     copyArray(temp, game); 

     if (i-2 >= 0 && temp[i] == '-' && temp[i-2] == 'o' && temp[i-1] == 'o'){//move pebble forwards 
      temp[i-1] = temp[i-2] = '-'; 
      temp[i] = 'o'; 
      result = Math.min(result, solve(temp)); 
     } 

     copyArray(temp, game); 

     if(i+2 < temp.length && temp[i] == '-' && temp[i+1] == 'o' && temp[i+2] == 'o'){//move pebble backwards 
      temp[i+1] = temp[i+2] = '-'; 
      temp[i] = 'o'; 
      result = Math.min(result, solve(temp)); 
     } 
    } 

到：

for (int i = 0; i < game.length; i++){ 
     char[] temp = null; 

     if (i-2 >= 0 && game[i] == '-' && game[i-2] == 'o' && game[i-1] == 'o'){//move pebble forwards 
      temp = new char[game.length]; 
      copyArray(temp, game); 
      temp[i-1] = temp[i-2] = '-'; 
      temp[i] = 'o'; 
      result = Math.min(result, solve(temp)); 
     } 



     if(i+2 < game.length && game[i] == '-' && game[i+1] == 'o' && game[i+2] == 'o'){//move pebble backwards 

      if(temp == null) temp = new char[game.length];    

      copyArray(temp, game); 
      temp[i+1] = temp[i+2] = '-'; 
      temp[i] = 'o'; 
      result = Math.min(result, solve(temp)); 
     } 
    } 

基本上，只有創建和 「copyArray（溫度，遊戲）;」當嚴格需要時。