Перейти к содержимому
whiskas

Поиск минимального пути

Рекомендуемые сообщения

Хмм иногда задумывался насчет роботов майнеров которых уже есть хренова туча. Но пришел седня такой вопрос "а у них самый оптимальный алгоритм?" Хмм.

Для самого лучшего алгоритма я думаю нужно представить что каждая руда ето точка. И найти минимальный путь прохода этих точек. То вопрос в том, есть ли уже какойто готовый алгоритм про то что я говорю? Если нет то давайте чтото придумаем. Нужно учитивать что это 3х вымерная система координат и то что мы можем не можем двигатся по диагонали. И еще также нужно учитивать что стоимость движения по пути по котором мы уже шли в 2 - 3 раза дешевле (не нужно ломать блок).

Изменено пользователем whiskas

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Ближайший сосед (NNS). Оптимальный по времени и памяти, но непредсказуемый по длине пути.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Хмм прикольная темка, да я не все учел. Нужно также учитивать повороты и также что робот может не ити на блок а только сломать его. И + место где он должен закончить.

Ну по твоей назве я понял что у тебя алгоритм расчитан ити к ближайшему соседу что следовательно не самое оптимальное.

Изменено пользователем whiskas

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
10 минут назад, whiskas сказал:

Ну по твоей назве я понял что у тебя алгоритм расчитан ити к ближайшему соседу что следовательно не самое оптимальное.

Самое оптимальное в каком смысле?

 

Абсолютный оптимум по количеству времени действий робота можно найти лишь полным перебором всех целей. Но времени на обработку придётся потратить очень много. Настолько много, что проще выкопать карьер сплошной копкой. Существуют итеративные методы, улучшающие решение на последующих шагах вычислений. С одной стороны, каждая последующая серия итераций позволяет сэкономить время движений робота, а с другой стороны, время расходуется и на сами вычисления тоже. Оценка соотношений затраченного и сэкономленного времени позволяет оптимизировать общее время, вовремя перейдя от вычислений к действиям. Это более-менее объективный критерий оптимума.

 

При этом надо помнить, что итеративные алгоритмы поиска оптимального пути обхода всех целей не детерминированы, и найденные пути могут отличаться даже при одинаковых данных и одинаковом количестве итераций. Кроме того, улучшение маршрута может происходить не на каждой из итераций вычисления, поэтому приходится искать способы предсказания хотя бы примерного количества итераций, необходимых для следующего улучшения маршрута. Но на это предсказание тоже приходится затрачивать время вычислений, поэтому оно не должно быть громоздким. В общем, постоянно приходится искать оптимум при поиске оптимума при поиске оптимума...

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

А что если определить критерии оптимума без учета времени вычисления, а алгоритм сделать достаточно быстрым, чтобы временные затраты на вычисление было достаточно малы и не влияли существенно на оптимальность системы в целом

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 час назад, hohserg сказал:

А что если определить критерии оптимума без учета времени вычисления, а алгоритм сделать достаточно быстрым, чтобы временные затраты на вычисление было достаточно малы и не влияли существенно на оптимальность системы в целом

Почему бы и нет. Какие у тебя есть идеи по созданию быстрого и при этом оптимального алгоритма поиска пути при большом количестве целей?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

 

Задачу можно решить только статистическим подходом. Можно взять генетические алгоритмы или reinforcement learning, за несколько дней получить модель, которая сможет подглядывать на 100 шагов вперед. Но я не знаю, как представить граф в памяти, особенно с учетом возможностей роботов. 2 мегабайта памяти это вообще ни о чем. В любом случае надо задействовать внешние ресурсы.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в тему...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...