ค้นหาจุดยอดที่ระยะ d

ฉันมีต้นไม้ที่มีจุดยอด N ฉันต้องการออกแบบอัลกอริทึมเพื่อตอบคำถามบางข้อได้อย่างรวดเร็ว เมื่อกำหนดจุดยอด V และจำนวนเต็ม d ฉันต้องการค้นหาจุดยอดที่ระยะ d จาก V หากมีจุดยอดมากกว่าหนึ่งจุดยอดที่ระยะ d ให้เอาท์พุตใดๆ เห็นได้ชัดว่าฉันรู้วิธีการใช้กำลังดุร้าย ฉันยังลองใช้แนวคิดบางอย่างที่คล้ายกับอัลกอริธึมการค้นหา LCA (คำนวณบรรพบุรุษที่ระยะ 1, 2, 4, 8...) แต่ไม่มีผลลัพธ์ใด ๆ

ฉันจะมีคำถามมากมาย เช่น 10^6 ดังนั้นฉันจึงอยากจะตอบในเวลา O(1) หรือ O(log N)


algorithm graph-theory
person user128409235    schedule 21.01.2016    source แหล่งที่มา
comment
หากต้องการค้นหาจุดในระยะที่กำหนด คุณเพียงวนซ้ำจุดทั้งหมดแล้วทดสอบ สำหรับการสืบค้นที่ซับซ้อนมากขึ้น เช่น k-จุดที่ใกล้ที่สุดและอื่นๆ ที่คล้ายกัน ให้ใช้ kd-tree, range tree หรือโครงสร้างข้อมูลอื่นที่คล้ายคลึงกัน   -  person Jaa-c    schedule 21.01.2016
comment
เหตุใดโซลูชันที่คล้ายกับ LCA จึงไม่ทำงาน   -  person Sorin    schedule 21.01.2016
comment
เพราะมันคำนวณระยะทางถึงบรรพบุรุษแต่ไม่ใช่คำนวณระยะทางถึงลูกหลาน   -  person user128409235    schedule 21.01.2016
comment
คุณต้องการจุดยอดที่มีเส้นทาง d ขอบระหว่างจุดนั้นกับราก หรือคุณต้องการให้ระยะทางขั้นต่ำเป็น d? เช่น. หากมีเส้นทาง a->b->c->d->e->f->g และ a->g แล้วจุดยอด g จะมีระยะห่าง 6 จากจุดยอด a หรือเป็นระยะทางเพียง 1 เท่านั้น (หรืออาจเป็นทั้งสองระยะทาง)   -  person MT0    schedule 21.01.2016
comment
@MT0 ในแผนผัง เส้นทาง (แบบธรรมดา) ระหว่างจุดยอดจะไม่ซ้ำกัน ดังนั้นจึงไม่มีสถานการณ์เช่นนี้เกิดขึ้นได้   -  person Niklas B.    schedule 21.01.2016
comment
@NiklasB. อ๋อ.. ฉันพลาดคำสำคัญคำหนึ่งไป   -  person MT0    schedule 21.01.2016

คำตอบ (4)


arrow_upward
1
arrow_downward

วิธีการนี้จะได้ผล

  1. คำนวณเซนทรอยด์ของเส้นทางที่ยาวที่สุดในแผนภูมิ ในการทำเช่นนั้น ให้ใช้การค้นหาเชิงลึกก่อนเพื่อค้นหาจุดยอด x โดยที่ความลึกสูงสุดของจุดยอดในต้นไม้ที่รากที่ x นั้นน้อยที่สุด
  2. คำนวณความลึกของจุดยอดทั้งหมดในต้นไม้ที่รากที่ x โดยใช้การสำรวจเส้นทางต้นไม้แบบง่ายๆ
  3. จัดกลุ่มแบบสอบถามตามดัชนีของส่วนประกอบที่เชื่อมต่อซึ่งแบบสอบถามจะตกอยู่หาก x ถูกลบออก
  4. วนซ้ำคำค้นหาทั้งหมดตามองค์ประกอบ สมมติว่าคำถามของคุณคือ (v, d) หาก deep(v) ‹= d คุณสามารถใช้บรรพบุรุษที่ d ของ v เป็นคำตอบได้ โดยใช้ แนวทางมาตรฐานใน O(log n) มิฉะนั้น ตรวจสอบว่ามีวิธีแก้ปัญหาจุดยอด w โดยมี path(v, w) ข้าม x และ dist(v, w) = d โดยการค้นหาความลึก d - ความลึก (v) ในองค์ประกอบอื่นอันใดอันหนึ่ง (เช่นใน O( 1) ผ่านการแฮช)

วิธีนี้ใช้ได้ผลเพราะหากมีคำตอบสำหรับการสืบค้น (v, d) ที่มีความลึก(v) >= d ก็จะมีเส้นทางที่มีความยาว d เริ่มต้นที่ v ซึ่งตัดผ่าน x เนื่องจากคุณสมบัติของ x

คุณสามารถใช้ขั้นตอนที่ 1 และ 2 ได้โดยใช้การค้นหาเชิงลึกก่อนเดียว

สำหรับขั้นตอนที่ 4 คุณต้องการเก็บตารางแฮชที่เชื่อมโยงความลึกกับจุดยอดในลักษณะที่คุณสามารถลบและเพิ่มจุดยอดใน O(1) จากนั้นคุณสามารถดำเนินการตามเวลาเชิงเส้นได้เมื่อทำงานทีละส่วนประกอบ

เวลารันทั้งหมดจะเป็น O((n + q) * log n)

ซึ่งสามารถทำได้ทางออนไลน์โดยการคำนวณล่วงหน้าโครงสร้างข้อมูลเชิงลึกจากขั้นตอนที่ 4 โดยใช้แผนผังการค้นหาแบบไบนารีถาวร อีกครั้งใน O(log n) ต่อแบบสอบถาม

person Niklas B.    schedule 21.01.2016
comment
หลังจากลบ x แล้ว ฉันจะต้องค้นหาเซนทรอยด์ในส่วนประกอบที่เชื่อมต่อหรือไม่ - person user128409235; 21.01.2016
comment
@ user128409235 หลังจากลบ x เพียงใช้อัลกอริธึมซ้ำกับส่วนประกอบที่เชื่อมต่อแต่ละอัน ใช่แล้ว นั่นเกี่ยวข้องกับการหาเซนทรอยด์ของแต่ละ CC - person Niklas B.; 21.01.2016
comment
หืม... มันจะไม่เพียงพอหรือไม่ที่จะหาเซนทรอยด์ สร้างอาร์เรย์ของจุดยอด vector‹int›จุดยอด[N] และเก็บไว้ในจุดยอด[1] จุดยอดที่ระยะ 1 จุดยอด[2] เก็บที่ระยะ 2 เป็นต้น และเส้นทางที่ยาวที่สุดจากเซนทรอยด์แล้วตอบทุกคำถามใน O(1)? - person user128409235; 21.01.2016
comment
@ user128409235 ฉันคิดว่าคุณพูดถูก จริงๆ แล้วเราไม่ต้องการการเรียกซ้ำ อย่างไรก็ตาม เราจำเป็นต้องเลือก x ที่แตกต่างกันเล็กน้อยเพื่อให้ใช้งานได้ (ดูการแก้ไข) และเราต้องจัดการกับกรณีที่แบบสอบถาม (v, d), deep(v) ‹= d คือคำตอบคือบรรพบุรุษที่ d ซึ่งสามารถทำได้ใน O(1) แต่มันซับซ้อน O(log n) นั้นง่ายกว่ามาก - person Niklas B.; 21.01.2016

arrow_upward
0
arrow_downward

เพิ่มน้ำหนักให้กับแต่ละขอบของต้นไม้ตามจำนวนลูกหลาน ซึ่งสามารถทำได้เพียงครั้งเดียวและเป็น O(N)

หากคุณต้องการหาจุดยอดที่ระยะทางที่กำหนด d คุณสามารถทำได้ในขั้นตอน O(d) โดยเพียงแค่เดินบนต้นไม้ขึ้นและลงในที่สุด ทันทีที่คุณ ค้นหาสาขาที่มีน้ำหนักมากพอที่จะไปถึง d ขั้น

หากคุณกำลังทำการสืบค้นหลายรายการบนแผนผังเดียวกัน สิ่งนี้จะทำงานได้ดีมาก

person Sklivvz    schedule 21.01.2016
comment
เป็นเรื่องง่ายมากที่จะออกแบบคลาสอินพุตโดยที่อัลกอริธึมที่คุณเสนอจะมีรันไทม์ Omega(q*n) โดยที่ q คือจำนวนข้อความค้นหา ตัวอย่างเช่น จะเกิดอะไรขึ้นถ้าต้นไม้เป็นเพียงเส้นทางที่มีความยาว n และการสืบค้นทั้งหมดอยู่ที่จุดสิ้นสุดจุดใดจุดหนึ่ง? - person Niklas B.; 21.01.2016
comment
ในกรณีนั้น แต่ละแบบสอบถามจะใช้ O(d) ไม่ใช่ O(N) กรณีเดียวที่เราต้องผ่านต้นไม้ทั้งหมดคือเมื่อ d = N - person Sklivvz; 21.01.2016
comment
ใช่ แต่ละแบบสอบถามคือ (1, N - 1) และคุณมีขอบ 1 - 2 - 3 - ... - N - person Niklas B.; 21.01.2016
comment
@NiklasB. คุณช่วยอธิบายตัวเองให้ดีขึ้นได้ไหม? แต่ละแบบสอบถาม (1,N) หมายถึงอะไร มีองค์ประกอบ N ในแผนผัง ข้อความค้นหา q แต่ละองค์ประกอบมีระยะทางเฉพาะ d (ซึ่งน้อยกว่าหรือเท่ากับ N) อัลกอริทึมนี้ทำงานเป็น O(q * d) ซึ่งน้อยกว่าหรือเท่ากับ O(q * N) - person Sklivvz; 21.01.2016
comment
แน่นอน แต่ OP ต้องการอัลกอริทึม O(N + q) หรือ O((N + q) log N) เพียงชี้ให้เห็นว่าแนวทางนี้มีเวลากรณีที่แย่ที่สุด Ω(N) ต่อการสืบค้น - person Niklas B.; 21.01.2016
comment
@ NiklasB ฉันเห็นว่าในฐานะ O(N) สำหรับแต่ละคำถามมันไม่สมเหตุสมผลเลยที่จะถามเป็นอย่างอื่น (แน่นอนคุณต้องตอบแต่ละคำถามอย่างน้อยหนึ่งครั้ง!) - person Sklivvz; 21.01.2016
comment
แต่ก็เป็นไปได้อย่างแน่นอนที่คุณสามารถแก้ไขแบบสอบถามได้เช่นในเวลา O(log N) หลังจากการประมวลผลล่วงหน้าของเวลา O(N log N) หรือน้อยกว่า นั่นคือสิ่งที่โครงสร้างข้อมูลมีไว้เพื่อ - person Niklas B.; 21.01.2016
comment
ให้เราสนทนาต่อในการแชท - person Sklivvz; 21.01.2016

arrow_upward
0
arrow_downward

ในขณะที่สร้างกราฟ/ลิงก์เพิ่ม สำหรับโหนดที่กำหนด คุณสามารถจัดเก็บแผนที่ของขอบสำหรับจุดยอดนั้น โดยที่ระยะทางเป็นกุญแจสำคัญ และขอบที่ระยะทางนั้นเป็นค่า วิธีนี้คุณสามารถสร้างและดึงข้อมูลใน O(1)

class Vertex{
  String vertexLabel;
  Map<Integer,List<Edge> edgeMap;
}
person Pranalee    schedule 21.01.2016

arrow_upward
-1
arrow_downward

รันอัลกอริทึม Floyd–Warshall หนึ่งครั้งบนกราฟของคุณเพื่อคำนวณเส้นทางที่สั้นที่สุดระหว่างคู่ทั้งหมด จากนั้นใช้สิ่งนี้ ? บางทีการค้นหาเชิงลึกก่อนโดยเริ่มจาก V และหยุดที่ความลึก d ก็เพียงพอแล้ว ขึ้นอยู่กับจำนวนข้อความค้นหาที่คุณตั้งใจจะดำเนินการ

person manuBriot    schedule 21.01.2016
comment
มันเป็นอัลกอริทึมแบบเดรัจฉานบังคับ และฉันกำลังมองหา O(n) หรือ O(n log n) - person user128409235; 21.01.2016
comment
การค้นหาเชิงลึกก่อนจะเป็น O(n) (และอาจน้อยกว่านั้นขึ้นอยู่กับ d) เนื่องจากมีการเยี่ยมชมจุดยอดทั้งหมดพร้อมกันมากที่สุด - person manuBriot; 21.01.2016