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

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

+ 1

Alpha Zero thank you very much for the insight.

+ 1

Coder Kitten you can find it here http://runayancigagak.rf.gd/JS/Members.js thank you very much for your response.

+ 1

Coder Kitten thank you very much you just made my Monday :)

+ 1

Coder Kitten you're very right.
Thank you very much for everything :)

0

Coder Kitten very glad to hear.
Would really appreciate it if you implement the code :)

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.