draugu ķēdes sociālajā tīklā

[Kristabs]

Sveiki. Kādi varētu būt efektīvākie paņēmieni lai veidotu draugu ķēdes (tipa, es <> draugs1 <> drauga1 draugs <> interesējošā persona).

Trīs līmeņos ir mierīgi - divi draugu masīvi un līdz pirmajam kopīgajam.

 

Ja ir četri (iespējamais scenārijs):

* Sameklēt ceturtā draugus

* Sameklēt kopīgo starp pirmo un katru no ceturtā draugiem, kamēr kāds sakrīt.

 

Bet kā lai es zinu vai viņš ir ceturtā līmeņa draugs, ko darīt, ja vēl vairāk līmeņos viss, utt...

Varbūt kāds zin ekskluzīvu algoritmu kā to izdarīt vis efektīvāk?

[bubu]

Nav vienkārša koka apstaigāšana?

Pseidokodā:

draugi getDraugus(level, persona)
{
if (level == 0) return persona.getDraugus()
draugi = []
for draugs in persona.getDraugus()
{
	draugi += getDraugus(level-1, draugs)
}
return draugi;
}

cetrutaa_liimenja_draugi = getDraugus(4, es)

 

Līdzīgi arī otrā punkta algoritms - dabū visus vajadzīgos draugus un meklē kopu šķēlumu.

[Aleksejs]

tā nav koka apstaigāšana, bet gan īsākā ceļa atrašana grafā.

[bubu]

Uff, jā pareiz. Tak grafs, ne koks jāņem. Nekas īpaši grūtāks nebūs - manā pseidokodā pamaini draugi masīvu uz asociatīvo masīvu, kur atslēga ir personas id kautkāds un strādās tāpat. Optimālākā gadījumā vajag atcerēties, kurām personām visi draugi jau savākti un tās draugus otreizēji neapskatīt.

 

A kas par ceļa atrašanu te vajadzīgs?

[Aleksejs]

Koks garantē, ka neveidojas cilpas. Grafā šādas garantijas vairs nav, tādēļ ir jāatceras, kuras virsotnes (draugi) jau iekļautas, citādi tās tiks iekļautas atkal un atkal. Īsākais ceļš jāatrod tādēļ, ka Ja no A ir ceļš uz B (A=B), tas neizslēdz, ka eksistē ceļš A=C=D=B un tas tiek atrasts pirmais.

lasāmviela pārdomām: http://mathworld.wolfram.com/All-PairsShortestPath.html http://mathworld.wolfram.com/ShortestPathProblem.html http://mathworld.wolfram.com/ReachingAlgorithm.html http://mathworld.wolfram.com/DijkstrasAlgorithm.html

Faktiski tā ir problēma - atrast visus ceļus ar garumu 1 (draugi) un 2 (draugu draugi) un varbūt 3 (draugu draugu draugi). Tādā gadījumā vajag izveidot šo: http://mathworld.wolfram.com/GraphDistanceMatrix.html

[bubu]

Ah, vajadzīgs atrast caur kādiem draugiem tiek pie tā drauga-N'tajā-pakāpē? Nu tad, protams, ka ceļa meklēšana grafā ir vispareizākais risinājums. Es tad laikam īsti nesapratu, ko autors jautāja.