0

Efficient Search Algorithm

I have a database for an extended family tree in the form of an object like this: Members={ "1":{ "id":"1" "name":"Full Name", "dad":"2", "spouses":["3","4"], "kids":{ "3":["5"], "4":["6","7"] } ... } "2":{ ... ... } ... ... over 1200 members in total } I'm trying to make a search algorithm to determine the shortest path between 2 people so then I can identify their relation. I'm using depth-first search by iterating through all the data in Members and saving all possible paths to finally choose the shortest one. It turns out to be painfully slow. I would like to know if you have a more efficient approach to tackle this. https://code.sololearn.com/WyhZnISzBfau/?ref=app

16th Oct 2020, 8:57 AM
Fernando Moceces
Fernando Moceces - avatar
7 Answers
+ 1
sadly there isn't a faster solution to this problem this is known as the traveling salesman problem, it's one of hardest problems in computer science the traveling salesman problem: there is 33 cities and you need to visit them all and to take the shortest path from the 33! different paths approximately 10^37 path. if you run the answer in the fastest computer on earth (10^17 calculation in a second) you need to wait 20 times the age of the universe to see the answer, RIP
22nd Oct 2020, 11:33 PM
Alpha Zero
Alpha Zero - avatar
+ 1
Alpha Zero thank you very much for the insight.
23rd Oct 2020, 12:23 AM
Fernando Moceces
Fernando Moceces - avatar
+ 1
Coder Kitten you can find it here http://runayancigagak.rf.gd/JS/Members.js thank you very much for your response.
24th Oct 2020, 12:01 AM
Fernando Moceces
Fernando Moceces - avatar
+ 1
Coder Kitten thank you very much you just made my Monday :)
26th Oct 2020, 12:53 AM
Fernando Moceces
Fernando Moceces - avatar
+ 1
Coder Kitten you're very right. Thank you very much for everything :)
27th Oct 2020, 12:43 AM
Fernando Moceces
Fernando Moceces - avatar
0
Coder Kitten very glad to hear. Would really appreciate it if you implement the code :)
24th Oct 2020, 11:56 PM
Fernando Moceces
Fernando Moceces - avatar
0
Coder Kitten I'm truly sorry if this is too much to ask but could you please add an enqueue spouse part in your code? There are some cases in which the function returns empty array when the two parameters are spouses and have no kid. Also spouses connected by their kid instead of to each other which makes the returned array has length 3 instead of 2. I tried but no luck.
26th Oct 2020, 9:29 AM
Fernando Moceces
Fernando Moceces - avatar