Ағаштардағы қашықтығы ораки

Салмақсыз ағашты ескере отырып, $ T = (V, E) $ $ v $ әрбір түйіннің бағанында позицияны анықтауға мүмкіндік беретін қашықтықтағы орақшалардың ең аз саны қандай?

Қашықтағы оракула $ d $ ($ u $) функциясын білдіретін $ d (u, v) $ «арнайы түйін» болып табылады, ол тұрақты $ u $ бастап $ v $ аралығына тұрақты қашықтықты береді.

Менде бұл мәселе барлық жұп ең қысқа жол мәселесіне, әсіресе Dijkstra алгоритміне қатыстылығымен байланысты, бірақ оракуларды анықтау үшін жарамды алгоритмді таба алмады. Сондай-ақ, бұл мәселе үшін кері сканерлеу процедурасы ақылға қонымды. Мүмкін сенде жақсы түйсігі бар шығар.

0
Мен әлі күнге дейін бұл мәселені түсінбеймін: ағашта тамыры өте тиімді қашықтықты оракула бола алады, бірақ бұл «позицияны анықтау» дегенді білдіреді.
қосылды автор Kalid, көзі
«Графикалы топологияны қайта құру» арқылы сіз бастапқыда изоморфтық графасын табуды қалайсыз ба? Егер сіз шынымен графиктің топологиясын іздесеңіз, онда сіздің топологиялық кеңістік дегеніміз не?
қосылды автор Saeed, көзі
Мен өзіңіздің сұрағыңды өңдеп, графиктің орнына ағашты жаздым, бірақ сонымен бірге «графикалық топологияны қайта құру» деген сөздерді редакциялауға тырыстым, «изоморфтық ағашты қайта құру», бірақ мен бұны білдіретініне сенімді емеспін, сондықтан мен бұл бөлікті өңдемеді.
қосылды автор Saeed, көзі
Шындығында бұл ағаш. Мен сондай-ақ мәселенің мәтінін сәл өзгертуге тура келеді. Мен тораптар түйіндерінің ең аз санын таба алғым келеді, олар сұралған кезде олар $ n $ түйінінің ағашында позицияны анықтауға мүмкіндік береді.
қосылды автор KARASZI István, көзі

Жауап жоқ

0