Арақашықтық - Distance oracle - Wikipedia

Жылы есептеу, а қашықтық oracle (DO) Бұл мәліметтер құрылымы а-дағы төбелер арасындағы қашықтықты есептеу үшін график.

Кіріспе

Келіңіздер G(V,E), бағытталмаған, өлшенген график болуы керек n = |V| түйіндер және м = |E| шеттері. Біз «түйіндердің арақашықтығы қандай екенін» сұраныстарына жауап бергіміз келеді с жәнет?".

Мұны істеудің бір жолы - жай ғана іске қосу Dijkstra алгоритмі. Бұл уақытты қажет етеді , және қосымша орын қажет емес (графиктің өзінен басқа).

Көптеген сұрақтарға тиімді жауап беру үшін графикті алдын-ала өңдеуге және мәліметтердің көмекші құрылымын құруға біраз уақыт жұмсай аламыз.

Осы мақсатқа қол жеткізетін қарапайым мәліметтер құрылымы - а матрица әр түйін жұбы үшін олардың арасындағы қашықтықты анықтайды. Бұл құрылым сұрақтарға тұрақты уақытта жауап беруге мүмкіндік береді , бірақ талап етеді қосымша орын. Оны уақытында инициализациялауға болады сияқты барлық қысқа жұп жолдар алгоритмін қолдана отырып Floyd – Warshall алгоритмі.

DO осы екі шектен шығады. Ол аз қолданады сұрақтарға жауап беру үшін бос орын уақыт. DO-дің көпшілігі дәлдікке ымыраласуы керек, яғни дәл қашықтықты қайтармайды, керісінше оның тұрақты факторлық жуықтауы.

Шамамен

Торуп пен Цвик[1] 10-нан астам әртүрлі ДС сипаттаңыз. Содан кейін олар әрқайсысы үшін жаңа DO ұсынады к, кеңістікті қажет етеді , кез келген келесі қашықтықтағы сұраққа уақытында жауап беруге болатындай етіп . Шамамен қайтарылған арақашықтық - ең үлкен ұзындық , яғни есептелген қашықтықты нақты қашықтыққа бөлу арқылы алынған өлшем 1 мен аралығында болады . Іске қосу уақыты .

Кейбір ерекше жағдайларға мыналар жатады:

  • Үшін біз қарапайым қашықтық матрицасын аламыз.
  • Үшін пайдаланып құрылымды аламыз әр сұраққа тұрақты уақытта жауап беретін кеңістік және шамамен 3 коэффициенті.
  • Үшін , пайдаланып құрылымды аламыз кеңістік, сұрау уақыты және созыңыз .

K-нің жоғары мәндері кеңістікті немесе алдын-ала өңдеу уақытын жақсартпайды.

Жалпы метрикалық кеңістіктер үшін DO

Oracle азаятын коллекциядан тұрғызылған к+1 шыңдар жиынтығы:

  • Әрқайсысы үшін : -ның әрбір элементін қамтиды , дербес, ықтималдықпен . Күтілетін мөлшері екенін ескеріңіз болып табылады . Элементтері деп аталады i-орталықтар.

Әр түйін үшін v, осы жиынтықтардың әрқайсысынан қашықтығын есептеңіз:

  • Әрқайсысы үшін : және . Яғни, жақын орналасқан i-орталық v, және бұл олардың арасындағы қашықтық. Белгіленген үшін екенін ескеріңіз v, бұл қашықтық әлсіз артып келеді мен. Әрқайсысы үшін екенін ескеріңіз v, және .
  • .

Әр түйін үшін v, есептеңіз:

  • Әрқайсысы үшін : . барлық шыңдарды қамтиды оларға жақынырақ v барлық шыңдарға қарағанда . Ішінара кәсіподақтары s - диаметрі өсіп келе жатқан шарлар, оларда келесі деңгейдің бірінші шыңына дейінгі қашықтықтағы шыңдар бар.

Әрқайсысы үшін v, оны есептеңіз шоқ:

Күткен өлшемін көрсетуге болады ең көп дегенде .

Әр шоқ үшін , салу а хэш-кесте барлығына арналған , қашықтық .

Мәліметтер құрылымының жалпы мөлшері

Осы құрылымды инициализациялап, келесі алгоритм екі түйін арасындағы қашықтықты табады, сен және v:

  • уақыт :
    • (екі кіріс түйінін ауыстырыңыз; бұл графиканың бағыттамасыз болғандықтан, олардың арасындағы қашықтықты өзгертпейді).
  • қайту

Әр қайталану кезінде арақашықтықты көрсетуге болады өседі . Бастап , ең көп дегенде бар к-1 қайталау, сондықтан ақырында . Енді үшбұрыш теңсіздігі, , сондықтан қайтарылған қашықтық ең көп дегенде болады .

Жақсартулар

Жоғарыда келтірілген нәтижені кейінірек Патраску мен Родитти жақсартты[2] өлшемді DO ұсынатындар шамамен 2 коэффициентін қайтарады.

Белгіленген қиылысу оракелінен қысқарту

Егер жуықтау коэффициенті ең көбі 2 болатын DO болса, онда a құруға болады қиылысты орнатыңыз (SIO) сұрау уақытымен және ғарышқа қойылатын талаптар , қайда n бұл жиындардың саны және N олардың мөлшерінің қосындысы; қараңыз oracle қиылысын орнатыңыз.

SIO проблемасында қарапайым емес шешім жоқ деп саналады. Яғни, бұл қажет уақытында сұрақтарға жауап беретін кеңістік , мысалы. пайдалану арқылы n-n әрбір екі жиынның қиылысы бар кесте. Егер бұл болжам шын болса, бұл жуықтау коэффициенті 2-ден аз және тұрақты сұраныс уақыты болатын DO жоқ дегенді білдіреді.[2]

Әдебиеттер тізімі

  1. ^ Торуп, М.; Цвик, У. (2005). «Шамамен қашықтықтағы оракулдар». ACM журналы. 52: 1–24. CiteSeerX  10.1.1.295.4480. дои:10.1145/1044731.1044732.
  2. ^ а б Патраску, М .; Родитти, Л. (2010). Торак-Цвик шекарасынан тыс Oracle арақашықтық. 2010 IEEE Информатика негіздеріне арналған 51-ші жыл сайынғы симпозиум (ТОБЖ). б. 815. дои:10.1109 / FOCS.2010.83. ISBN  978-1-4244-8525-3.