Algorithm for choosing unique options with least overall cost
Problem And Question
I am looking for pointers for an efficient algorithm for the following problem.
It is hard to explain without some data so first I will provide some example data:
Destination 1:
Source 1: Cost 26
Source 2: Cost 32
Source 3: Cost 98
Create New Source: Cost 100
Destination 2:
Source 1: Cost 12
Source 2: Cost 99
Source 3: Cost 51
Create New Source: Cost 88
Destination 3:
Source 1: Cost 55
Source 2: Cost 31
Source 3: Cost 76
Create New Source: Cost 99
I need to choose one of the sources for each destination, so that each source (excluding 'create new source', which can be used as many times as required) is used zero or one times, and the overall cost is low.
I do not need (although it would be nice) an algorithm that produces the absolute lowest cost, because I imagine this would require brute forcing. Instead, I just need an algorithm that is rather more efficient than blindly using source $n$ for destination $n$.
Example Output And Constraints
The above data was actually chosen completely at random, but the following general rules apply to the data:
* It will be very likely that, excluding the 'Create new source' option, the amount of sources will be equal to the amount of destinations.
* It will be very likely that the cheapest option for destination $n$ will be to use source $n$.
* It will be very likely that the cost of creating a new source will be one of highest costing options.
* The example data above uses 3 sources, therefore there are $(3+1)^{3}=64$ total options, and as such, the solution is brute-forcible. At the time of writing, I am actually currently working with 33 sources and counting, there the brute forcing the $(33+1)^{33}=3.45... 835
× 10^{50}$ options is not feasible.
For the above data, the following costs are generated:
/---------------+---------------+---------------+------------+--------\
| Destination 1 | Destination 2 | Destination 3 | Total Cost | Valid? |
+---------------+---------------+---------------+------------+--------+
| Source 1 (26) | Source 1 (12) | Source 2 (31) | 69 | FALSE |
| Source 2 (32) | Source 1 (12) | Source 2 (31) | 75 | FALSE |
| Source 1 (26) | Source 1 (12) | Source 1 (51) | 93 | FALSE |
| Source 2 (32) | Source 1 (12) | Source 1 (55) | 99 | FALSE |
| Source 1 (26) | Source 3 (51) | Source 2 (31) | 108 | TRUE |
\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/
Therefore
* Destination 1 should use Source 1.
* Destination 2 should use Source 3.
* Destination 3 should use Source 2.
* In actual fact, blindly using source $n$ for destination $n$ with this data actually has a cost of 201, almost double the best choice, and is ranked 15th of the 24 valid solutions.
Background To The Problem
I am working with a series of playlists, which when combined form one master playlist. Each playlist consists of a title in the format of (Master Playlist - Part $n$) and a list of items. These playlists are stored on a server.
The program I have written locally calculates the new state the master playlist needs to be in, splits it up with rules that are beyond the context of this question, and then starts making API calls to update the state of the playlists on the server accordingly.
The operations that can be done are
* Create a new empty playlist, giving it a name in the process.
* Delete an unwanted playlist, and any items inside.
* Add an item to an existing playlist.
* Remove an item from an existing playlist.
* Re-order an item to a new position in the playlist it is already in.
* Rename a playlist.
In the programs current form, for each local playlist part $n$, it will fetch the server state of playlist part $n$, work out whether it is cheaper to delete+recreate or add+remove, and then proceed accordingly. 835