Artificial Intelligence Asked by KGhatak on September 5, 2020
I have found that the K-means algorithm with K=20, has been mentioned as a solution for the below question,
A new mobile phone service chain store would like to open 20 service
centers in your city. Each service center should cover at least one
shopping center and 5000 households of annual income over $75000.
Design a scalable algorithm that decides locations of service centere
by taking all the aforementioned constraints into consideration.
However, I think Local Search algorithm, similar to solving N-Queen problem by local searches, can also be an alternate solution. In fact, below is the algorithm that I have in mind,
My Algorithm:
//Define constraints
// CT1 as - should cover at at least one shopping center, and
// and CT2 as - should cover 5000 households with min income 75K/anum
//Initialize locations of the service centers C_i for i=1,..,20
for i=1 to 20
C_i := randomly select location from map
end-for
//Iterate until cut-off T
for t=1 to T //T may be initialized with 1000
C_r := randomly select any of {C_1,..,C_20} such that they are currently not satisfying the constraints CT_1 and CT_2
if C_r is NULL$
return success //current assignments of C_1 to C_20 are valid
else
Assign C_r a new location that has lowest conflict w.r.t. CT_1 and CT_2
end-if
end-for
Further, in support of my suggestion, I have found quite a few papers that are suggesting that the local search is a better approximation. Few of such papers are:
Would you share your thoughts on the feasibility of the local search algorithm provided above, as a potential solution.
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP