Cody

Problem 45464. Design a minimum-cost cable network for a power grid

You are given the 2-D point locations ( xi , yi ) of N components of a power grid. These components include power sources (power plants, wind farms, solar farms, etc.), loads (residential, commercial, etc.), storage stations, and substations. However, the cables between them are not yet installed.

Your task is to design a complete cable network by installing cables between pairs of components. A network is considered complete if and only if a path exists from any component A to any other component B. A completed network of cables is enough to deliver power from any source to any load or vice versa (excess power can be sent back to the grid). After all, cables can carry power in both directions.

However, the cost of installing a cable between components A & B is D dollars per unit straight-line distance between their point locations. This means that we don't want to install too many cables; we only need to install enough to make the network complete. Knowing the locations of all N components, can you design a complete cable network whose total installation cost is minimium?

Write a function that accepts variables P and D. Variable P is an N-by-2 matrix where each row is a location ( xi , yi ). Output the required minimum total installation cost, rounded to 2 decimal places. You are ensured that:

  • 2 <= N <= 100
  • 100 <= D <= 1000 and 1 <= xi, yi <= 100
  • D and all elements of P are integers
  • All point locations in a test case are distinct

A sample test case is given below.

>> P = [11 15; 4 14; 9 13; 13 12; 3 11; 6 11; 1 10; 9 9; ...
         5 7; 13 7; 7 6; 10 5; 3 4; 6 2; 11 1];
>> connect_grid(P,400)
ans = 
  18394.83

A visualization of this case is given here: https://drive.google.com/open?id=1wqnH0j6aihbD_Jm5pxrW7dhTm3VxrEAI

Solution Stats

66.67% Correct | 33.33% Incorrect
Last Solution submitted on Jul 15, 2020