Оптимизация алгоритма

@DevExpress · Регистрация: 16.03.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте, решаю следующую задачу:
Задан граф с K вершинами и отметками на ребрах – целыми числами от 1 до K. В базе данных хранится N векторов длины M, компоненты которых – номера вершин графа - числа от 1 до K. Значения разных компонент вектора могут совпадать. Запрос – такой же вектор длины M. Требуется найти в базе данных вектор, ближайший к запросу. Расстояние между двумя векторами (a1,..,aM) и (b1,..,bM) вычисляется как сумма от 1 до M расстояний d(ai,bi) между вершинами графа с номерами ai и bi.
Пусть мне известна таблица расстояний между вершинами, и я могу непосредственно сравнивать вектор запроса и вектора в базе данных. Делаю это перебором векторов из базы, что очевидно)). Но теперь мне нужно оптимизировать этот перебор. Пока не представляю как это можно сделать...помогите с идеями, заранее благодарю!

@Mysterious Light · 24.01.2016, 00:57

Вычисление расстояния между двумя векторами — лёгкая операция, O(M). Поэтому в принципе задача сводится к следующей:
Имеется N объектов и функция-метрика D. Для заданного объекта a найти объект b из N объектов, который был бы ближе всего к a.

Вам принципиально то, что метрика определяется графом?
Может, имеется какие-то соотношения параметров? Например, K<<M<<N.
Просто иначе непонятно, в какую сторону оптимизировать-то.

@Excalibur921 · 24.01.2016, 12:05

Сообщение от DevExpress

Делаю это перебором векторов из базы, что очевидно))

Просто последовательный перебор? Я бы сделал так(что очевидно):
Создаете базу данных длин, сортируете по возрастанию. Разбиваете на группы:
0: длинна от 0 до 2
1: длинна от 2 до 4 и т.д.
От количества групп зависит скорость алгоритма.

Добавлено через 3 минуты
Кстати можно сделать наподобие веток дерева(натуральное дерево как в природе). Группы и подгруппы.
0: длинна от 0 до 2
Подгруппа 0.1: длинны от 0 до 2 делим еще на группы.
1: длинна от 2 до 4 и т.д.
Подгруппа 1.1: длинны от 2 до 4 делим еще на группы.

@DevExpress · 24.01.2016, 23:56 **[ТС]**

Вам принципиально то, что метрика определяется графом?

Да, метрика определяется только графом. Что касается соотношений параметров, то они не оговорены в задаче, но для оптимизации можно самому придумать эти соотношения если это поможет...
Excalibur921, а можно поподробнее про базу данных длин, не очень понятно, что вы имели ввиду?

@Excalibur921 · 25.01.2016, 00:38

Издеваетесь?)) Вы оперируете терминами метрика и граф и не поняли по примеру разбивку на интервалы?
У вас 100 разных длин не по порядку. Искомая например будет 98.
Вы перебираете все с 0 до 100 т.к не знаете где какой номер совпадет?

Сортируете все 100 длинн по размеру.
Делите на 5 интервалов по 20 длинн.
Внутри каждого делите на 4 интервала по 5 длинн.

Теперь вместо 100 переборов. Будет перебор 5 интервалов. Попадание в 5 интервал. В нем перебор 4 интервалов. В найденном перебор 5 длинн.

В итоге в самом худшем варианте поиска по 100 значений вместо сверки 100 значений будет сверка 5+4+5=14 значений. Ускорение в 7 раз. Больше уровней \ больше интервалов = быстрей расчет. Я думал это очевидный прием =).

@DevExpress · 25.01.2016, 16:32 **[ТС]**

Я не издеваюсь, я пытаюсь понять, что вы подразумеваете под длинной) если длину вектора, то она постоянна, то есть все векторы одинаковой длины М.
Мне кажется я не очень хорошо описал условие задачи.
Пусть множество вершин вектора содержит 3 вершины {1 2 3}.
Таблица смежности такая:
0 2 5
2 0 3
5 3 0
(Элемент матрицы - растояние от вершины i до вершины j)
База данных содержит векторы:
А(1; 2; 1; 3; 2)
В(1; 1; 1; 2; 1)
С(3; 3; 3; 3; 2)
Вектор запроса следущий:
Q(2; 2; 3; 1; 1)
Растояние между векторами Q и A вычисляется так:
p(2;1) + p(2;2) + p(3;1) + p(1;3) + p(1;2), где p(i,j) - растояние между вершинами i и j в графе.
2 + 0 + 5 + 5 + 2 = 12 - растояние между векторами A и Q. Как найти вектор, ближайший к Q, быстрее чем простым перебором?

@Excalibur921 · 25.01.2016, 23:35

Похоже и я и вы не поняли друг друга.
Тогда я не знаю что тут можно сделать. Гляньте kdtree. В любом случае перебор всех самый медленный из вариантов. Я бы гуглил этот вопрос типа “ оптимизация поиска по двумерному графу”.Либо перевести задачу в более известную типа: “ поиск в несортированном массиве.”

Мое представление графа

:
Это как паутинка с кружками. Задача выбираем кружочек нужно найти те первые и ближайшие с кем он связан. Но зачем?)).
Можно перебрать каждый и смотреть с кем он связан заранее создав базу данных. Т.е. ассоциативную базу данных. В итоге выбрали кружочек и уже знаем с кем он связан…

Можно поделить поиск на определенные сектора перебора. Например экран на 4 части делим. Если выбрали первую четверть то перебор всех кто в ней( заранее сортировали, уже в 4 раза меньше работы).

@Shamil1 · 26.01.2016, 00:56

Таблица расстояний и вектора в БД не меняются, а запросов к БД много. Так?

@DevExpress · 26.01.2016, 11:35 **[ТС]**

Таблица расстояний не меняется, запрос всего один). Это чисто академическая задача)

@Shamil1 · 26.01.2016, 12:18

Если запрос всего один, то нет ничего оптимальней перебора.
Другие варианты потребуют подготовки данных, которая займёт больше времени, чем полный перебор.

(Точно так же, проще найти перебором в неотсортированном массиве, чем сортировать массив для бинарного поиска).

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@DevExpress 0 / 0 / 0 Регистрация: 16.03.2013 Сообщений: 6

	Оптимизация алгоритма 23.01.2016, 23:33. Показов 614. Ответов 9 Метки нет (Все метки) Здравствуйте, решаю следующую задачу: Задан граф с K вершинами и отметками на ребрах – целыми числами от 1 до K. В базе данных хранится N векторов длины M, компоненты которых – номера вершин графа - числа от 1 до K. Значения разных компонент вектора могут совпадать. Запрос – такой же вектор длины M. Требуется найти в базе данных вектор, ближайший к запросу. Расстояние между двумя векторами (a1,..,aM) и (b1,..,bM) вычисляется как сумма от 1 до M расстояний d(ai,bi) между вершинами графа с номерами ai и bi. Пусть мне известна таблица расстояний между вершинами, и я могу непосредственно сравнивать вектор запроса и вектора в базе данных. Делаю это перебором векторов из базы, что очевидно)). Но теперь мне нужно оптимизировать этот перебор. Пока не представляю как это можно сделать...помогите с идеями, заранее благодарю! 0

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,204 Записей в блоге: 24
	24.01.2016, 00:57
	Вычисление расстояния между двумя векторами — лёгкая операция, O(M). Поэтому в принципе задача сводится к следующей: Имеется N объектов и функция-метрика D. Для заданного объекта a найти объект b из N объектов, который был бы ближе всего к a. Вам принципиально то, что метрика определяется графом? Может, имеется какие-то соотношения параметров? Например, K<<M<<N. Просто иначе непонятно, в какую сторону оптимизировать-то. 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	25.01.2016, 00:38
	Издеваетесь?)) Вы оперируете терминами метрика и граф и не поняли по примеру разбивку на интервалы? У вас 100 разных длин не по порядку. Искомая например будет 98. Вы перебираете все с 0 до 100 т.к не знаете где какой номер совпадет? Сортируете все 100 длинн по размеру. Делите на 5 интервалов по 20 длинн. Внутри каждого делите на 4 интервала по 5 длинн. Теперь вместо 100 переборов. Будет перебор 5 интервалов. Попадание в 5 интервал. В нем перебор 4 интервалов. В найденном перебор 5 длинн. В итоге в самом худшем варианте поиска по 100 значений вместо сверки 100 значений будет сверка 5+4+5=14 значений. Ускорение в 7 раз. Больше уровней \ больше интервалов = быстрей расчет. Я думал это очевидный прием =). 0

@DevExpress 0 / 0 / 0 Регистрация: 16.03.2013 Сообщений: 6
	25.01.2016, 16:32 [ТС]
	Я не издеваюсь, я пытаюсь понять, что вы подразумеваете под длинной) если длину вектора, то она постоянна, то есть все векторы одинаковой длины М. Мне кажется я не очень хорошо описал условие задачи. Пусть множество вершин вектора содержит 3 вершины {1 2 3}. Таблица смежности такая: 0 2 5 2 0 3 5 3 0 (Элемент матрицы - растояние от вершины i до вершины j) База данных содержит векторы: А(1; 2; 1; 3; 2) В(1; 1; 1; 2; 1) С(3; 3; 3; 3; 2) Вектор запроса следущий: Q(2; 2; 3; 1; 1) Растояние между векторами Q и A вычисляется так: p(2;1) + p(2;2) + p(3;1) + p(1;3) + p(1;2), где p(i,j) - растояние между вершинами i и j в графе. 2 + 0 + 5 + 5 + 2 = 12 - растояние между векторами A и Q. Как найти вектор, ближайший к Q, быстрее чем простым перебором? 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	25.01.2016, 23:35
	Похоже и я и вы не поняли друг друга. Тогда я не знаю что тут можно сделать. Гляньте kdtree. В любом случае перебор всех самый медленный из вариантов. Я бы гуглил этот вопрос типа “ оптимизация поиска по двумерному графу”.Либо перевести задачу в более известную типа: “ поиск в несортированном массиве.” Мое представление графа : Это как паутинка с кружками. Задача выбираем кружочек нужно найти те первые и ближайшие с кем он связан. Но зачем?)). Можно перебрать каждый и смотреть с кем он связан заранее создав базу данных. Т.е. ассоциативную базу данных. В итоге выбрали кружочек и уже знаем с кем он связан… Можно поделить поиск на определенные сектора перебора. Например экран на 4 части делим. Если выбрали первую четверть то перебор всех кто в ней( заранее сортировали, уже в 4 раза меньше работы). 0

@Shamil1 Модератор 3135 / 2282 / 469 Регистрация: 26.03.2015 Сообщений: 8,883
	26.01.2016, 00:56
	Таблица расстояний и вектора в БД не меняются, а запросов к БД много. Так? 0

@DevExpress 0 / 0 / 0 Регистрация: 16.03.2013 Сообщений: 6
	26.01.2016, 11:35 [ТС]
	Таблица расстояний не меняется, запрос всего один). Это чисто академическая задача) 0

@Shamil1 Модератор 3135 / 2282 / 469 Регистрация: 26.03.2015 Сообщений: 8,883
	26.01.2016, 12:18
	Если запрос всего один, то нет ничего оптимальней перебора. Другие варианты потребуют подготовки данных, которая займёт больше времени, чем полный перебор. (Точно так же, проще найти перебором в неотсортированном массиве, чем сортировать массив для бинарного поиска). 0