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:
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers14
Suggested Problems
-
1756 Solvers
-
334 Solvers
-
Convert given decimal number to binary number.
2028 Solvers
-
Combined Ages 3 - Non-symmetric, n ≥ 3
84 Solvers
-
Combined Ages 4 - Non-symmetric with multiples, n ≥ 3
71 Solvers
More from this Author19
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!