eu_tomat

Нормальный подход, в генетических алгоритмах именно так и делается. Какой-нибудь из новых вариантов окажется лучше предыдущих. А если не окажется, всегда можно попробовать еще раз. Будь я роботом, именно так бы и писал, только релизил бы почаще.

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

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

Статистику полезных руд, выкопанного мусора и пробега было бы крайне интересно увидеть.

Про сканирование всех слоев я сказал в общем. И если ты подобрал интервал с удовлетворяющим тебя уровнем помех, то нет смысла сканировать чаще. Главное, что ты уверен в каждом просканированном блоке.

А, понял, надо распознавать жилы/не жилы и бегать только по жилам. Это спорт такой, или есть практическое применение? Как по мне, тупая копалка туннелей с выжиранием встреченных жил намного эффективней и проще.

Велосипеды изобретаете. Все уже изобретено до нас. Какие коммивояжеры? Какие вычисления? Берем GPS API, берем Vector API, сканируем, перебором вычисляем рудные жилы (условие: несколько блоков ожидаемой плотности), заносим рудные жилы по-блочно в массив, в цикле трилатерируем ближайший нужный блок, едем в него, удаляем его из массива. И так далее, до каждого блока.

artem211, я долго не отвечал, т.к. при внимательном рассмотрении задача оказалась значительно сложнее, чем вчера, когда ты меня спросил о ней.

Нет не спорт, просто эффективный карьер с геосканером и мозгами, который будет копать все в заданном объёме, а не делать туннель бессмысленный и беспощадный) а вообще разрабатываемый алгоритм будет универсальным, хочешь туннель, хочешь шахта, а хочешь огромный плоский пласт от 0 до 20 уровня не останется ни блока руды. По мне - так туннель и рядом не стоит по эффективности

1) Тупая копалка, роющая пласт через два за полчаса, или же гипотетеческий алгоритм, выкапывающий все руды за 5 минут, но перед этим три часа вычисляющий оптимальный маршрут.

2) Прямо сейчас пользоваться уже существующим относительно простым и довольно эффективным алгоритмом, либо 10 лет искать идеальный алгоритм, ничего не копая и не разрабатывая других более-менее эффективных алгоритмов. Последний путь, кстати, не так плох, и при удачном стечении обстоятельств может привести к награждению какой-нибудь математической премией.

Цитата:

"Задача о кратчайшем пути"

Интересны две цитаты:

• Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
• Многие современные распространенные методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжера.

Теперь комментарии по имеющемуся алгоритму.

• В качестве расстояния, надеюсь, используешь не физическое расстояние, а прямоугольную метрику. Ее можно дополнительно улучшить, добавив затраты на поворот.
• Действительно, хорошей мыслью является рубка руды вперед, вверх и вниз, не обязательно перемещаясь в блок с рудой. Но алгоритм и без того сложный.
• На начальном этапе я бы не стал заморачиваться на выковыривании руды из бедрока. Отрезать по границе отрицательной плотности – хорошая мысль. Если очень надо, я бы вычищал бедрок отдельным алгоритмом. Добавил бы точки входа в определенные зоны бедрока в основном алгоритме, через эту же точку осуществлялся бы выход из бедрока, чтобы не усложнять. А по лабиринту бедрока проходим вспомогательным алгоритмом, учитывающим непроходимые блоки.
• Кстати, непроходимым может оказаться спонтанный коблоген. Тут тоже есть, над чем подумать.
• Сыпучка проходится легко. Можно сделать, как у Totoro, но я бы добавил задержку, чтобы робот не лупил еще не упавший гравий, а немного подождал, чтобы не создавать лишнюю нагрузку в цикле.
• В игровом чате мы обсуждали, стоит ли двигаться и сканировать только зону вперед и вправо. Тогда я сказал, что алгоритм обхода играет бОльшую роль. Сейчас думаю, что при существующем алгоритме лучше сканировать и обходить по всем сторонам света. При сплошной добыче это почти не играет роли, но в твоем алгоритме лучше двигаться от центра и возвращаться в центр.
• Предварительное построение цепочек руд – хорошая идея, которая может значительно сократить вычислительную сложность задачи.

Какие мысли возникают:

• Если руды мало, то можно воспользоваться полным перебором всех возможных маршрутов. До какого числа точек это оправдано, можно проверить экспериментально.
• Если точек слишком много, я бы искал скопления руд.
• Если скоплений руд мало, расстояния между ними большие, в первую очередь оптимизировал бы перемещения между скоплениями.
• Если скопления руд плотные и крупные, то внутри скоплений можно вообще использовать тупую копку ряд через два. Если нет, то разделяем их на скопления средних размеров.
• Средние скопления я бы разбил на малые суб-скопления.
• Оптимальный путь внутри малых скоплений можно находить полным перебором.
• Можно попробовать выполнять не полный перебор всех возможных точек, а только достаточно близких. Можно даже самых близких равноудаленных. Пока не знаю, насколько сильным будет отклонение маршрута от идеального, это надо проверять практически. Но могу сказать определенно: выбор в качестве следующей точки самой близкой из имеющихся не всегда даст оптимальный маршрут.
• Как разделять весь массив руд на скопления, пока не знаю. Я бы для начала взял результат сканирования по нескольким чанкам, нашел бы расстояния от каждой точки до каждой и построил бы гистограмму всех расстояний. Возможно, я бы там ничего не увидел, но попытаться стоит. Еще можно позаимствовать подход, аналогичный вычислению фрактальной размерности: внутри исследуемой области находим все возможные кубы со сторонами [1..n] и вычисляем среднюю плотность во всех кубах, содержащих хоть какие-то руды и опять же строим гистограмму, соотнося с расчетной средней плотностью. Так мы хотя бы получим представление о размерах скоплений, их количестве и плотности.
• Еще можно выбирать для сканирования и добычи площадь достаточно малую, чтобы выполнить полный перебор маршрутов. То есть, мы разбиваем задачу на более мелкие, конечно же, несколько теряя в эффективности полученного суммарного маршрута.
• В дополнение к предыдущему пункту можно добавить разбивку по высоте. Например, роем вертикальную шахту, выполняя сканирование каждого уровня. А потом поднимаемся вверх, заодно выкапывая всю отсканированную руду. Например, находясь на глубине 64 блоков, мы ищем оптимальный путь выработки 12 уровней, но достигнув 8-ого, производим пересчет верхних 12-и и снова проходим 8 уровней.

artem211, опиши здесь свой текущий алгоритм. Нет сил чат вычитывать. Я позже отвечу. А пока скажу кратко. Твой алгоритм хорош сочетанием простоты и эффективности, если я его правильно понял. Мой может быть эффективнее, а может и не быть, зависит от порядка подачи данных на вход и требует доработки. Но в любом случае, он более ресурсоемок.

Прости, но это машина. МАШИНА.

Прости и ты тоже, но это глупая машина. ГЛУПАЯ. И это излечимо.

В игровом чате попытался ответить ссылкой на форум.

Автомат выдал предупреждение.

Надо бы ему мозги вправить за такую дерзость.

Просто поставь после своего print('что-то') команду error() с пустыми скобками.

То, что доктор прописал. Спасибо.

error(smth) вместо print() в конце юзать?..

Да, это уже лучше. Но хотелось бы оставить только тот вывод, что я хочу.

Есть код для ComputerCraft:

function getPeripheral( p_type, p_side )
  if( peripheral.isPresent(p_side) )then
    if( peripheral.getType(p_side)==p_type )then
      return peripheral.wrap(p_side)
    end
  end
  print( "Error: "..p_type.." not found at "..p_side.." side" )
  exit()
end