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 below:
Solve

Solution Stats

70.0% Correct | 30.0% Incorrect
Last Solution submitted on Jan 09, 2024

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers14

Suggested Problems

More from this Author19

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!