Thread: Cubes, networks and shortest path.

Please see the question in the image below:



I would be extremely grateful to anyone who could explain this question to me step-by-step, eventually arriving at the final answer, as I have spent almost a week on it, and I still do not think I am getting anywhere at all - it is not an easy question!!!

Originally Posted by yeah:)

Please see the question in the image below:



I would be extremely grateful to anyone who could explain this question to me step-by-step, eventually arriving at the final answer, as I have spent almost a week on it, and I still do not think I am getting anywhere at all - it is not an easy question!!!

Cool problem.

In advance I'll warn that you might have a hard time understanding my answer if you haven't worked with programming and algorithms before. I'll try my best to explain and be available to answer questions.

There is more than one way to approach the problem.

It's possible that due to lots of symmetry, this problem has a closed-form expression solution method, but with just 14 vertices it may be easier to look in other directions first.

One approach is to think of the problem as a Travelling salesman problem, where edges between non-connected vertices are given "infinite distance" (in practice, just assign a very high number). Although TSP is in general a hard problem, 14 vertices is certainly doable, but you would need to write a computer program or use existing software tools to get your answer. Solutions to TSP are, in the general case, given in terms of an algorithm rather than in terms of a closed-form expression.

There are TSP solvers that can be downloaded, like the Concorde TSP Solver, or you could try reading up on how to code your own algorithm.

I'll go for a different approach, which can be written without knowledge of TSP algorithms: I'll use a backtracking algorithm, which is similar to using brute force, but more optimized. (Brute force means trying every possible path.)

Consider that 8 of the vertices have 6 edges each, and the other 6 vertices have 4 edges each. We can encode a path by labeling the vertices, and then for each vertex store the value of the next vertex. We won't actually be using this encoding, it's just to get an estimate of how much time/memory the algorithm will take. For simplicity, allow the last vertex to point to another vertex. Then 6^8 * 4^6 = 6,879,707,136 is the number of possible codes in our encoding scheme, but not all codes correspond to valid paths, thus our estimate is high. Given modern computing power and the estimate, backtracking should be doable in a reasonable amount of run time.

So, we choose a labeling scheme, and while the choice is arbitrary, we can try to choose one that makes things easier to keep track of. The most straightforward way I can think of is to place the cube with one corner on the origin and the opposite corner on the point (1,1,1). With binary, we have

(0,0,0) -> 0
(0,0,1) -> 1
(0,1,0) -> 2
...
(1,1,1) -> 7

So we've labeled the corners of the cube, now we need to label the centers of each face. We can define a center from the four corners on the same face, and I assigned them lexicographically:

(0,1,2,3) -> 8
(0,1,4,5) -> 9
(0,2,4,6) -> 10
(1,3,5,7) -> 11
(2,3,6,7) -> 12
(4,5,6,7) -> 13

Now for distance, there are only two possibilities: 1, or .

One last thing needs to be addressed: it is possible that the start and end nodes are both corners, both centers, or one corner and one center. Without loss of generality, we can start with a corner and find the shortest distance, then start over with a center and find the shortest distance, and take whichever of the two is shortest.

Basically, everything is set up, and we just need to write the program. Where backtracking comes in: we store the shortest path distance achieved so far, and if any path exceeds that distance, we stop following the current path and go back to a previous state (we backtrack).

Note that the problem doesn't ask us what the shortest path is, just the length of the path. For fun, we'll keep track of the path itself too.

Here is some Java code:

Code:

// http://www.mathhelpforum.com/math-help/pre-algebra-algebra/140117-cubes-networks-shortest-path.html

import java.util.ArrayList;

public class CubeGraph {
  private static int[][] map;
  private static double min = 1000, min1, sq22 = Math.sqrt(2)/2.0;
  private static ArrayList<Integer> minPath;

  public static void init() {
    // map each vertex to either four or six other vertices
    // using hard-coded values; could also generate with method
    int[] v0 = {1, 2, 4, 8, 9, 10};
    int[] v1 = {0, 3, 5, 8, 9, 11};
    int[] v2 = {0, 3, 6, 8, 10, 12};
    int[] v3 = {1, 2, 7, 8, 11, 12};
    int[] v4 = {0, 5, 6, 9, 10, 13};
    int[] v5 = {1, 4, 7, 9, 11, 13};
    int[] v6 = {2, 4, 7, 10, 12, 13};
    int[] v7 = {3, 5, 6, 11, 12, 13};
    int[] v8 = {0, 1, 2, 3};
    int[] v9 = {0, 1, 4, 5};
    int[] v10 = {0, 2, 4, 6};
    int[] v11 = {1, 3, 5, 7};
    int[] v12 = {2, 3, 6, 7};
    int[] v13 = {4, 5, 6, 7};
    int[][] map1 = {v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13};
    map = deepCopy(map1);
  }

  public static void main(String[] args) {
    long time = System.currentTimeMillis();
    init();
    ArrayList<Integer> path = new ArrayList<Integer>();
    boolean[] visited = new boolean[14];
    backtrack(path, visited, 0, 0);
    min1 = min;
    System.out.println("Starting on corner: min dist = " + min + " and path = " + minPath);
    min = 1000;
    path = new ArrayList<Integer>();
    visited = new boolean[14];
    backtrack(path, visited, 8, 0);
    System.out.println("Starting on center: min dist = " + min + " and path = " + minPath);
    System.out.println("in " + ((System.currentTimeMillis() - time) / 1000.0) + " s");
  }

  public static void backtrack(ArrayList<Integer> path, boolean[] visited, int vertex, double dist) {
    if (dist > min) return;
    visited[vertex] = true;
    path.add(vertex);
    if (path.size() == 14) {
      if (dist < min) {
        min = dist;
        minPath = new ArrayList<Integer>();
        minPath.addAll(path);
      }
      return;
    }
    for (int i = 0; i < map[vertex].length; i++) {
      int nextV = map[vertex][i];
      if (!visited[nextV])
        backtrack(new ArrayList<Integer>(path), visited.clone(), nextV, dist + getDist(vertex, nextV));
    }
  }

  public static double getDist(int v1, int v2) {
    return (v1 > 7 || v2 > 7) ? sq22 : 1;
  }

  public static int[][] deepCopy(int[][] orig) {
    int[][] copy = new int[orig.length][];
    for (int i = 0; i < orig.length; i++)
      copy[i] = orig[i].clone();
    return copy;
  }
}

Output:

Code:

Starting on corner: min dist = 9.485281374238573 and path = [0, 1, 8, 2, 10, 4, 9, 5, 11, 3, 12, 6, 13, 7]
Starting on center: min dist = 9.778174593052025 and path = [8, 0, 1, 3, 11, 5, 9, 4, 10, 2, 12, 6, 13, 7]
in 0.375 s

Which is faster than I expected. I believe the code is bug-free, but confirmation is always welcome. It can be seen that the minimum path I got has a distance of .

My guess is that a TSP solver would get the same answer faster, but although I'm curious, I'm not quite curious enough to set it up and compare, haha.

Thanks for the fun problem!

i made this animation. hope that helps.

Originally Posted by Maya

i made this animation. hope that helps.

WOW! No wonder I was struggling to solve this one!!! Thank you so much for all your solutions!!! Is there any way of solving it without the programming???

Originally Posted by yeah:)

WOW! No wonder I was struggling to solve this one!!! Thank you so much for all your solutions!!! Is there any way of solving it without the programming???

Sorry but the program I presented seemed to me the easiest approach available . Besides that the only thing I can think of is trial and error (possibly using a model you can draw on), but perhaps someone else can think of a way.

The end solution my program gave followed the diagonal lines exclusively except for a single edge, so possibly one could discover it while playing around, but then there's the issue of proving that it is in fact the optimal solution.

By the way, Maya's animation looks really cool but I don't see how it could represent a solution to the problem. I think Maya misinterpreted the problem as asking for a path that visits each edge, rather than each vertex, and additionally I don't see how it folds into a cube; the usual 2-D unfolding is

Code:

   +--+
   |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
   |  |
   +--+

EDIT: I see how it folds into a cube now. It is a valid solution for visiting each edge exactly once.

i was not sure if your java-program would generate something similar. but my solution isn't ideal: no edge is crossed twice, but two corners(=vertexes) are. maybe one could fix this by drawing down instead of drawing from left to the right. i tried with pen and paper before putting everything together in the animation. maybe this could lead you to a solution without programming.

Originally Posted by Maya

i was not sure if your java-program would generate something similar. but my solution isn't ideal: no edge is crossed twice, but two corners(=vertexes) are. maybe one could fix this by drawing down instead of drawing from left to the right. i tried with pen and paper before putting everything together in the animation. maybe this could lead you to a solution without programming.

I wanted to do a 3D animation, but I'm not really set up for that and it would take forever. But here is a 2D illustration.

Originally Posted by undefined

I wanted to do a 3D animation, but I'm not really set up for that and it would take forever. But here is a 2D illustration.

Once again, I would like to thank you for your wonderful solutions - I think I am finally beginning to understand what I could not earlier - the visual illustrations certainly helped!

As for the programming, could you please suggest a website to me where I could start learning it, as I feel it could potentiallly be of immense use when it comes to Maths?

Originally Posted by yeah:)

Once again, I would like to thank you for your wonderful solutions - I think I am finally beginning to understand what I could not earlier - the visual illustrations certainly helped!

As for the programming, could you please suggest a website to me where I could start learning it, as I feel it could potentiallly be of immense use when it comes to Maths?

You're welcome!

There are many options for teaching yourself programming using free, online materials including software. Depending on your style of learning, it might be helpful if you know someone who knows programming who could help you get started and answer questions in person. Definitely start with the LOLCODE programming language. (Just kidding!) I don't have extensive experience with different languages so maybe the best way to decide which language to start with is to do internet searches, then once you've picked one, start applying it right away. What you learn in one language will be applicable in most other languages. In addition to typical programming languages, there are also computer algebra systems like PARI/GP--which is especially good for number theory and related fields.

If you enjoy math puzzles then I can highly recommend Project Euler as a means to solve problems while learning how to program, and vice versa. The problems get pretty tricky starting around the middle of the third page, and often there are elegant solutions that run in under a second, which might have seemed impossible to solve in under a year at first. Also, whenever you submit a correct answer you're brought to a forum page for that problem where people give valuable insights on various solution methods.

An interesting tool is CodingBat, which recently added Python support and changed their name from JavaBat--it's a series of exercises mostly testing basic logic and data manipulation (somewhat tedious, but useful), requiring minimal syntax, and you code directly into the website and it checks your result without having to download anything, so you can get a flavor.

Along a similar line, I stumbled across a site called wonderfl which lets you program flash online, without having to download anything.

Good luck!

FANTASTIC! Once again, thank you so very much for all of your help!!!