Как рассчитать оптимальное решение?

Question

У меня есть мнимое оборудование. Он имеет ровно 2 адреса памяти и 2 регистра. Он имеет только две инструкции - вычесть адрес памяти из регистра и переместить значение регистра в память. Ему необходимо выполнить операцию перемещения значения с одного адреса памяти на другой. Каждое из четырех значений в памяти и регистрах имеет неизвестные значения. Все это выглядит следующим образом:

Хранение:

Memory #1 (m1) -> a 
Memory #2 (m2) -> b 
Register #1 (r1) -> c 
Register #2 (r2) -> d 

Инструкции:

mov m r //Copies value at r into m 
sub r m //Subtracts the value in m from r 

Возможные комбинации:

mov m1 r1 
mov m1 r2 
mov m2 r1 
mov m2 r2 
sub r1 m1 
sub r1 m2 
sub r2 m1 
sub r2 m2 

Цель:

Set the value in m2 to equal a (which is the value initially stored in m1). 

Возможное решение (Спойлер оповещения!):

//Comments show respective value for m1, m2, r1, r2 
//a b c d 
mov m2 r1 //a c c d 
sub r1 m2 //a c 0 d 
mov m2 r1 //a 0 0 d 
sub r1 m1 //a 0 -a d 
mov m1 r1 //-a 0 -a d 
sub r1 m1 //-a 0 0 d 
sub r1 m1 //-a 0 a d 
mov m2 r1 //-a a a d 

Это решение принял 8 ходов. Я пытался найти лучшее решение, написав программу для перебора всех решений (до 10 ходов). Я написал его на Java. Это то, что я придумал:

import java.util.ArrayList; 
import java.util.Random; 

public class AssemblyChallenge { 

    //This is the main logic. 
    public static void main(String[] args) { 
     Memory memory1 = new Memory(); 
     Memory memory2 = new Memory(); 
     while (memory1.value == memory2.value) { 
      memory2 = new Memory(); 
     } 
     Register register1 = new Register(); 
     Register register2 = new Register(); 
     for (int i = 0; i < 8; i++) { 
      for (int j = 0; j < 8; j++) { 
       for (int k = 0; k < 8; k++) { 
        for (int l = 0; l < 8; l++) { 
         for (int m = 0; m < 8; m++) { 
          for (int n = 0; n < 8; n++) { 
           for (int o = 0; o < 8; o++) { 
            for (int p = 0; p < 8; p++) { 
             for (int q = 0; q < 8; q++) { 
              for (int r = 0; r < 8; r++) { 
               ArrayList<Integer> instructions = new ArrayList<>(); 
               instructions.add(i); 
               instructions.add(j); 
               instructions.add(k); 
               instructions.add(l); 
               instructions.add(m); 
               instructions.add(n); 
               instructions.add(o); 
               instructions.add(p); 
               instructions.add(q); 
               instructions.add(r); 
               runInstructions(instructions, memory1, memory2, register1, register2); 
              } 
             } 
            } 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 

    //This runs an set of instruction sets 
    public static void runInstructions(ArrayList<Integer> instructions, Memory memory1, Memory memory2, Register register1, Register register2) { 
     int memoryValue1 = memory1.value; 
     for (int instruction : instructions) { 
      switch (instruction) { 
       case 0: 
        moveRegisterIntoMemory(memory1, register1); 
        break; 
       case 1: 
        moveRegisterIntoMemory(memory1, register2); 
        break; 
       case 2: 
        moveRegisterIntoMemory(memory2, register1); 
        break; 
       case 3: 
        moveRegisterIntoMemory(memory2, register2); 
        break; 
       case 4: 
        subtractMemoryFromRegister(register1, memory1); 
        break; 
       case 5: 
        subtractMemoryFromRegister(register1, memory2); 
        break; 
       case 6: 
        subtractMemoryFromRegister(register2, memory1); 
        break; 
       case 7: 
        subtractMemoryFromRegister(register2, memory2); 
        break; 
      } 
      if (memoryValue1 == memory2.value) { 
//    System.out.println(instructions + " succeeded in 10 moves or less!"); 
      } 
      System.out.println(instructions.size()); 
     } 
    } 

    //This takes the value in the register and copies it into the value at the memory 
    public static void moveRegisterIntoMemory(Memory memory, Register register) { 
     memory.value = register.value; 
    } 

    //This takes the value in the memory and subtracts it from the value in the register 
    public static void subtractMemoryFromRegister(Register register, Memory memory) { 
     register.value -= memory.value; 
    } 

    //This is the Memory class which stores a random value 
    static class Memory { 
     public int value; 

     public Memory() { 
      Random random = new Random(); 
      value = random.nextInt(20000) - 10000; 
     } 
    } 

    //This is the Register class which stores a random value 
    static class Register { 
     public int value; 

     public Register() { 
      Random random = new Random(); 
      value = random.nextInt(20000) - 10000; 
     } 
    } 
} 

Эта проблема в том, что он работает слишком медленно, и это не кажется, что он будет рассчитывать 1073741824 возможностей в реалистичное время. Как я могу исправить свою программу, чтобы найти оптимальное решение этой проблемы? Есть ли у вас подход с грубой силой?

Answer 1

Благодаря CptBartender и harold у меня есть решение! Он печатает все решения с менее чем 8 инструкциями примерно за 1 секунду.

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Random; 

public class AssemblyChallenge { 
    //Possible solutions to be confirmed. 
    private static ArrayList<int[]> solutions = new ArrayList<>(); 

    //This is the main logic. 
    public static void main(String[] args) { 
     Memory memory1 = new Memory(); 
     Memory memory2 = new Memory(); 
     while (memory1.value == memory2.value) { 
      memory2 = new Memory(); 
     } 
     Register register1 = new Register(); 
     Register register2 = new Register(); 
     int startingMemoryValue1 = memory1.value; 
     int startingMemoryValue2 = memory2.value; 
     int startingRegisterValue1 = register1.value; 
     int startingRegisterValue2 = register2.value; 
     for (int i = 0; i < 8; i++) { 
      for (int j = 0; j < 8; j++) { 
       for (int k = 0; k < 8; k++) { 
        for (int l = 0; l < 8; l++) { 
         for (int m = 0; m < 8; m++) { 
          for (int n = 0; n < 8; n++) { 
           for (int o = 0; o < 8; o++) { 
            for (int p = 0; p < 8; p++) { 
             memory1.value = startingMemoryValue1; 
             memory2.value = startingMemoryValue2; 
             register1.value = startingRegisterValue1; 
             register2.value = startingRegisterValue2; 
             int[] instructions = new int[8]; 
             instructions[0] = i; 
             instructions[1] = j; 
             instructions[2] = k; 
             instructions[3] = l; 
             instructions[4] = m; 
             instructions[5] = n; 
             instructions[6] = o; 
             instructions[7] = p; 
             runInstructions(instructions, memory1, memory2, register1, register2); 
            } 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
     confirmSolutions(); 
    } 

    //This runs an set of instruction sets 
    public static boolean runInstructions(int[] instructions, Memory memory1, Memory memory2, Register register1, Register register2) { 
     int memoryValue1 = memory1.value; 
     int numMoves = 0; 
     for (int instruction : instructions) { 
      numMoves++; 
      switch (instruction) { 
       case 0: 
        moveRegisterIntoMemory(memory1, register1); 
        break; 
       case 1: 
        moveRegisterIntoMemory(memory1, register2); 
        break; 
       case 2: 
        moveRegisterIntoMemory(memory2, register1); 
        break; 
       case 3: 
        moveRegisterIntoMemory(memory2, register2); 
        break; 
       case 4: 
        subtractMemoryFromRegister(register1, memory1); 
        break; 
       case 5: 
        subtractMemoryFromRegister(register1, memory2); 
        break; 
       case 6: 
        subtractMemoryFromRegister(register2, memory1); 
        break; 
       case 7: 
        subtractMemoryFromRegister(register2, memory2); 
        break; 
      } 
      if (memoryValue1 == memory2.value) { 
       int[] solution = Arrays.copyOfRange(instructions, 0, numMoves); 
       if (!isSolutionAlreadyFound(solution)) { 
        solutions.add(solution); 
       } 
       return true; 
      } 
     } 
     return false; 
    } 

    private static boolean isSolutionAlreadyFound(int[] solution) { 
     for (int[] foundSolution : solutions) { 
      if (Arrays.equals(solution, foundSolution)) { 
       return true; 
      } 
     } 
     return false; 
    } 

    private static void confirmSolutions() { 
     Memory memory1 = new Memory(); 
     Memory memory2 = new Memory(); 
     while (memory1.value == memory2.value) { 
      memory2 = new Memory(); 
     } 
     Register register1 = new Register(); 
     Register register2 = new Register(); 
     int startingMemoryValue1 = memory1.value; 
     int startingMemoryValue2 = memory2.value; 
     int startingRegisterValue1 = register1.value; 
     int startingRegisterValue2 = register2.value; 
     for (int i = 0; i < solutions.size(); i++) { 
      memory1.value = startingMemoryValue1; 
      memory2.value = startingMemoryValue2; 
      register1.value = startingRegisterValue1; 
      register2.value = startingRegisterValue2; 
      boolean success = runInstructions(solutions.get(i), memory1, memory2, register1, register2); 
      if (success && solutions.get(i).length < 8) { 
       System.out.println(Arrays.toString(solutions.get(i)) + " was successful in " + solutions.get(i).length + " moves!"); 
      } 
     } 
    } 

    //This takes the value in the register and copies it into the value at the memory 
    public static void moveRegisterIntoMemory(Memory memory, Register register) { 
     memory.value = register.value; 
    } 

    //This takes the value in the memory and subtracts it from the value in the register 
    public static void subtractMemoryFromRegister(Register register, Memory memory) { 
     register.value -= memory.value; 
    } 

    //This is the Memory class which stores a random value 
    static class Memory { 
     public int value; 

     public Memory() { 
      Random random = new Random(); 
      value = random.nextInt(20000) - 10000; 
     } 
    } 

    //This is the Register class which stores a random value 
    static class Register { 
     public int value; 

     public Register() { 
      Random random = new Random(); 
      value = random.nextInt(20000) - 10000; 
     } 
    } 
} 

Я искал только решения с менее чем за 8 ходов, а выход был:

[2, 4, 5, 0, 4, 4, 2] was successful in 7 moves! 
[2, 4, 5, 2, 5, 5, 2] was successful in 7 moves! 
[2, 5, 4, 0, 4, 4, 2] was successful in 7 moves! 
[2, 5, 4, 2, 5, 5, 2] was successful in 7 moves! 
[3, 6, 7, 1, 6, 6, 3] was successful in 7 moves! 
[3, 6, 7, 3, 7, 7, 3] was successful in 7 moves! 
[3, 7, 6, 1, 6, 6, 3] was successful in 7 moves! 
[3, 7, 6, 3, 7, 7, 3] was successful in 7 moves! 

Один икота мне пришлось преодолеть было Правильные решения по случайности. Мое решение состояло в том, чтобы снова запустить проверку с разными номерами. Это, конечно, имеет небольшой шанс иметь двойной ложный позитив.

Наименьшее количество инструкций возможно является 7.

Answer 2

Чтобы переместить m1 на м2, эта последовательность 7 инструкция только с использованием r1 кажется довольно простым:

   m1 m2 r1 r2 
       a b c d 
mov r1 m2  c 
sub m2 r1   0 
sub m1 r1   -a 
mov r1 m2  -a 
sub m2 r1   0 
sub m2 r1   a 
mov r1 m2  a 

Поскольку нет регистра в регистр инструкции, это немного вводит в заблуждение, чтобы включить r2, поскольку он не нужен.