Byte & Routerman
Routerman
Привет, Байт, вот думаю, как бы нам модифицировать классический A* поиск, чтобы он работал в реальном времени для динамической маршрутизации в меш-сети? Накидываю версию, которая использует простой аналоговый задержку для моделирования потока трафика, интересно, поможет ли это удерживать пакеты на наиболее эффективном маршруте.
Byte
Я понимаю, что ты имеешь в виду: A* отлично работает со статичными графами, но в сетях постоянно меняются стоимости связей. Идея с аналоговой задержкой для имитации перегрузки интересна, но главное — как обновлять эвристику. Если позволить задержке влиять на функцию стоимости на каждом такте, то по сути ты делаешь непрерывную переоценку пути. Это может быть затратно, особенно если ты каждый кадр запускаешь A* с нуля. Лучше использовать инкрементный алгоритм, типа D* Lite или даже упрощенную версию R*, которая сохраняет частичное решение и пересчитывает только затронутые области. Оставь задержку как легкий модификатор стоимости – например, простое скользящее среднее задержки пакетов на каждом соединении – и позволяй алгоритму поиска адаптироваться только когда изменение стоимости превышает определённый порог. Так ты удерживаешь поиск в пределах разумного, но при этом учитываешь динамику реального времени. И не забудь ограничить количество расширений за цикл, иначе заблокируешь основной поток. Короче говоря, используй A* как основу, оберни его в инкрементную систему поиска, и пусть задержка влияет на веса рёбер, а не заставляет тебя каждый раз запускать пересчёт всего.
Routerman
Звучит неплохо, хотя я всё ещё немного переживаю из-за этих колебаний скользящего среднего. Если линия задержки начнёт скакать с каждым тактом, функция стоимости может начать раскачиваться, как маятник. Попробуй ограничить дельту, чтобы не запускать повторный прогон, просто чтобы избежать этого кошмара с "звёздочкой на каждом такте". И не забудь поддерживать порядок в очереди приоритетов, иначе постепенные обновления начнут ощущаться как полный перебор. Следи за порогами – слишком агрессивные сделают систему похожей на суетливую мастерскую, а не на спокойный коридор. Держим цикл плотным и пусть пакеты, а не алгоритм, делают основную работу.
Byte
Ты прав – колебания могут сильно вздуть стоимость, поэтому ограничение дельты перед полным прогоном A* – хорошая мера предосторожности. Я бы еще добавил гистерезис к обновлениям очереди, чтобы мелкие колебания не вызывали каскад повторных вставок. Если приоритетная очередь начнет терять данные, схема легкой, отложенной очистки сохранит ее в порядке без полной перестройки. Поддерживай пороги достаточно строгими, чтобы замечать реальную перегрузку, но достаточно свободными, чтобы пакеты могли свободно проходить; иначе алгоритм превратится в систему управления, которая будет доминировать над потоком трафика. Короче говоря, зафиксируй изменения стоимости в небольшом диапазоне, лениво чисти очередь и позволь пакетам делать основную работу.
Routerman
Отлично. Задержка в очереди не позволит поиску превратиться в нервный эхо-канал. Ленивое удаление – неплохая хитрость: просто отмечай узлы как устаревшие и пропускай их при извлечении, перестраивать не нужно. Держи окно небольшого изменения достаточно узким, чтобы реагировать на реальное узкое место, но достаточно широким, чтобы избежать постоянной перестановки из-за обратной связи. Если заметишь, что размер очереди растет, добавь периодическую очистку, чтобы убрать совсем заброшенные записи. Так алгоритм останется легким, как и полагается, и сеть будет продолжать работать плавно.
Byte
Звучит как отличный план. Только убедись, чтобы сканирование не замедляло пересылку пакетов, и чтобы флаг устаревания был максимально легким – чтобы каждая операция была O(1). Это поможет поддерживать быстрый поиск, короткую очередь и стабильную работу сети.
Routerman
Отлично, что всё сходится. Я оставлю флаг "старого" в виде одного бита, а сканирование перекину на фоновый поток, чтобы оно не тормозило процесс. Как будто запасное колесо в багажнике – под рукой, но не мешает. Если очередь начнёт глючить, добавлю быстрый лог диагностики, просто чтобы убедиться, что система всё ещё под контролем.
Byte
Вот что я и хочу – лёгкие флаги, чистка фона и логи, которые сообщают о проблемах, а не приводят к полному коллапсу. Будь лаконично, и получишь сетку, которая реагирует плавно, без лишней болтовни.