Недавно, на одном из форумов нашел такое объявление. Интересно узнать возможность реализации данной задачи на masm32 и ее стоимость. Я предполагаю, что это достаточно сложная задача с серьезной ценой.
На масме это не реально, а вот в приложении к автокаду вполне, нечто подобное было в теме моей научной работы, а где ты это объявление видел?
DarkAngel В данной задаче поиск оптимального решения невозможен. Решать сложно даже двумерные задачи вроде полного покрытия прямоугольника или круга минимальным количеством кругов меньшего радиуса. Даже в случае одного ребра не покрываемого одним кругом/сферой количество вариантов сделать это - бесконечно, а это всего лишь один шаг перебора. Поэтому можно искать только приближённые решения, при этому руководствоваться соображениями покрытия максимального количества углов/ребёр/граней/объёма. Ну а потом искать неэффективные датчики(имеющих большое перкрытие с соседями), удалять их, а соседние пытаться сдвигать чтобы опять получить полное покрытие. Но в любом случае оператор с помощью программы сможет найти более оптимальное решение, чем сама программа.
Можно разбить пространство на конечное число клеток и решать полным перебором вариантов. Решение будет не оптимальным, но близким к тому. А вот условие про masm32... гм... я еще понял бы, если собираются засунуть прогу в какой-нибудь микроконтроллер с сильной нехваткой ресурсов, но в этом случае и ассемблер был бы какой-то другой. А на PC, да еще под винду, писать расчетную задачу целиком на асме? Это какое-то извращение, имхо, типа чистки унитаза зубной щеткой или мытья полов носовым платком.
представить сферы покрытия из шаров в кубы, помещение в соответствии с преградами представить в виде набора выпуклых параллелепипедов. заполнить параллелепипеды кубами с учетом округления вверх (0.5 куба == 1 куб) если датчиков недостаточно для полного покрытия помещения - расположить их боле-мене равномерно. --- это первое, что в голову пришло. из 3д графики, вроде бы.
а лучше представить не в виде кубов, а в виде шестигранников (? не помню как их в 3д зовут). тогда количество таких датчиков в выпуклом прямоугольнике будет количеству шестигранников по осям. количество будет равно Lэтой оси / (sqrt(3)*Rсферы покрытия датчика) можно еще предусмотреть краевой эффект
Ну, примерно понятно, откуда такая формулировка появилась. Заказчик, находящийся не слишком в теме, начал прикидывать алгоритмы и тоже догадался (или подсказали), что проще всего - тупым перебором локаций. (Хотя, по идее, тут помог бы направленный перебор с отсечением вариантов, что-то из сферы действия генетических алгоритмов). Еще хватило ума сообразить (или намекнули), что брутфорс - это будет немножко медленно. А что позволяет любую медленную задачу ускорить в стопиццот раз? Правильно, полностью накодить ее на этом... как ево... асимблёре. Ну и т.п.
qqwe Если пытаться трёхмерное пространство забить правильными многогранниками, так чтобы не осталось свободного места, то единственный из правильных многогранников, который позволит это сделать -- куб.
Ну вообще-то, как подсказывают мои скудные познания, тесселяция лучше происходит треугольниками, так что фигура типа тетраэдра оптимальнее (и диаграмма направленности датчика больше смахивает на тетраэдр). Однако задача стоит не покрыть пространство полностью, а оптимизировать кол-во датчиков. То бишь если будет мертвая зона в середине помещения, или небольшие, непересекающиеся мертвые зоны, то условие можно считать выполненным. Хотя всё это уже офтоп, автор интересовался возможностью реализовать всё это на масме и ценой, и походу потерял уже интерес к своему топику.
r90 гдето также я и рассуждал в 1 случае. но на плоскости 6ти угольники дадут более оптимальное заполнение. если есть 3д фигура из правильных 6ти угольников (не помню есть ли такая и как зовется), то в 3д она, возможно, будет более оптимальна artkar тут и правда все зависит от направленности. например, если это камера, то конус, а если датчик влажности, то шар. разбиение на треугольники может быть неудобно, тк задача не разбить пространство вообще, а разбить пространство фигурами приближенными к определенной. просто, пропорционально увеличить размеры всех областей чувствительности. те, в рассчете получилось 110 датчиков. мы имеем 100 датчиков с шарообразной чувствительностью радиуса R. Rразмещения датчиков будет Rр = R*(110/100)1/3
qqwe Совершенно ведь очевидно, что из правильных шестиугольников составить многогранник не удастся, хотя бы потому, что три шестиугольника состыковать с общей вершиной можно лишь развернув их все три в одну плоскость. Есть многогранник из правильных пятиугольников, но толку-то с него? artkar Тетраэдрами тоже не удастся замостить. Ну тогда ещё надо вспомнить законы сохранения материи и энергии, вспомнить что ничего не берётся ниоткуда, и ставить датчики только там, где может что-то случиться. Ну, скажем, если речь идёт о датчике влажности, то глупостью будет ставить его в углу где нет ни одной трубы (сантехнической или вентиляционной) и где нет окон/дверей и пр. Если датчик дыма, то быть может его хватит одного, просто поставить его надо в вентиляцию? Там ведь дым концентрироваться будет. Может с вентиляцией задержка детекта будет больше, но зато можно обойтись одним датчиком и даже не использовать масм при этом. Короче я это к тому, что уходить от абстракции изложенной в задаче и вспоминать физический смысл этих абстракций имеет смысл в одном из двух случаев: 1) абстракции признаны неудачными; 2) в рамках этих абстракций было найдено удовлетворительное решение. Но с данной задачей 2) не был достигнут. 1) в общем тоже.
r90 вах, не подумал, что 120*3 = 360. но с кубами все остается в силе складское помещение - датчик дыма. пока дойдет до вентиляции - тушить будет нечего зернохранилище - датчик влажности. сухие и влажные области могут разделяться по очень резким границам. но если зерно гдето подтухнет - вся окрестная куча станет несъедобной до ядовитости. изза запаха и грибков. шахта - датчики газа. газ может выделяться участками. оттого в вентиляции суммарная концентрация будет небольшая, а в месте выброса шахтеры ласты посклеивают. опять же, пока дойдет еще. можно и еще вспомнить случаев когда желателен параноидальный контроль.
qqwe Вот и я о том же. Не зная исходной задачи уходить от предложенной абстракции не выглядит очень правильным.
