Easyelectronics.ru

Электроника для всех
Текущее время: 16 окт 2019, 04:56

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/10pcs (Любой цвет!)
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 14 ] 
Автор Сообщение
 Заголовок сообщения: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 00:55 
Только пришел
Аватара пользователя

Зарегистрирован: 30 мар 2012, 23:43
Сообщения: 29
Откуда: Тихорецк
Доброго времени суток уважаемые форумчане, только только начал осваивать STM32 и появилась необходимость в написание алгоритма на МК.
Дан массив Float значений максимум 20, так же дано контрольное значение, методом перебора (перебором и суммирование всех значений в массиве) необходимо найти ближайшее значение к заданному.
Вывести какие именно значение в массиве соответствуют максимально приближенному к заданной переменной.
Вот и возник вопрос потянет ли STM32 если учесть что количество переборов составит (2^20)= 1048576, в наличие есть STM32F407IGT6 (168Мгц, 210DMIPS).
Необходимо хоть примерно знать на какое время можно рассчитывать по обработке этого алгоритма? т.к помимо этого алгоритма в нем еще много будет функций задействовано ( SPI, FSMC и пр.). Может с такой задачей вообще не стоит и смотреть в сторону STM32?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 01:04 
Старожил

Зарегистрирован: 17 дек 2014, 04:38
Сообщения: 679
Доброго времени суток !

Честно говоря я ничего не понял. Какой алгоритм вам нужен ? Вы выбрали алгоритм перебора, что же вам подсказать ? почему для поиска максимально приближённого значения нужно 2^20 а не просто 20 переборов ? Вы задачу опишите, тогда можно будет вам алгоритм подсказать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 01:19 
Только пришел
Аватара пользователя

Зарегистрирован: 30 мар 2012, 23:43
Сообщения: 29
Откуда: Тихорецк
Например есть массив чисел {210,2; 105,3; 56,0; и т.д всего 20 элементов} и дано контрольное число к примеру 600, так вот нужно просуммировать все возможные комбинации из этого массива для нахождения максимального приближенного значения к 600.
Хорошим примером являются двоичные числа. Например, для 3 чисел есть 8 комбинаций:
000
001
010
011
100
101
110
111
где 1 - число включено в сумму, 0 - не включено.
Поэтому что бы перебрать все комбинации из 20 значений необходимо сделать (2^20)= 1048576 переборов.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 01:52 
Старожил

Зарегистрирован: 26 ноя 2012, 10:28
Сообщения: 3996
Откуда: КЧР, поселок Нижний Архыз
Ну так формулировать задачу надо правильно! А то вопрос - "задача о рюкзаке", а формулировка - бред какой-то.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 01:58 
Старожил

Зарегистрирован: 27 мар 2015, 01:22
Сообщения: 1444
Мультиголовочный комбинационный весовой дозатор собираетесь делать ? )

_________________
less is more


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 02:02 
Старожил
Аватара пользователя

Зарегистрирован: 04 окт 2011, 10:19
Сообщения: 1762
Краску подбирать на день жестянщика


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 02:06 
Только пришел
Аватара пользователя

Зарегистрирован: 30 мар 2012, 23:43
Сообщения: 29
Откуда: Тихорецк
Не мультиголовочный но дозатор =)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 03:49 
Старожил

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3297
сложение в fpu 1 такт, за пару сотен мс поди справится если тупо перебирать.

ну и массив отсортировать можно, так часть вариантов для перебора с обоих концов сразу отпадёт, так как будет сильно меньше / сильно больше искомого числа.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 04:42 
Старожил
Аватара пользователя

Зарегистрирован: 30 мар 2015, 23:56
Сообщения: 742
Сортировка.
Приближение к нулю, сохраняем результат, откат первого элемента и новый цикл.
Поиск лучшего результата.
Проблемы?

_________________
Потоковая OS


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 10:42 
Старожил

Зарегистрирован: 26 ноя 2012, 10:28
Сообщения: 3996
Откуда: КЧР, поселок Нижний Архыз
Лучше сбалансированное дерево построить и сразу выкинуть слишком крайние ветви. Ну это, конечно, если не нужно знать наилучшего ответа, а достаточно приближения.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 11:04 
Старожил

Зарегистрирован: 27 мар 2015, 01:22
Сообщения: 1444
denveren0k писал(а):
Не мультиголовочный но дозатор =)

Утопия ) На одном мк такое не сделать, вообще ни на каком. И дело даже не в этих переборах, это вообще десятая с краю проблема )

_________________
less is more


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 11:32 
Старожил
Аватара пользователя

Зарегистрирован: 26 янв 2010, 21:48
Сообщения: 3965
Откуда: Звенигород
Если значения слишком разбросаны, то можно для начала перейти к целым числам. Хотя, думаю, не поможет)))

_________________
От Парижа до Находки с водкой лучше, чем без водки!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 11:49 
Старожил

Зарегистрирован: 24 июн 2011, 14:05
Сообщения: 294
Откуда: Новочеркасск
Может не так понял задачу, но как тут сказали отсортируйте массив по убыванию скажем, потом находите ближайший элемент с меньшей стороны (например дано число 600, и два ближайщих числа в массиве 550 и 650 -> берёте 550), потом накладываете своего рода двоичную маску на массив и согласно "двоичной" логике прибавляете соответствующие элементы массива (можно прибавлять не последовательно, чтоб ускорить процесс). Впринципе из всего тут написанного этот алгоритм и получается. Это будет конечно при самом худшем случае меньше чем 20^2 в два раза точно, но точность даст максимальную.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алогритм (задача о рюкзаке) на STM32
СообщениеДобавлено: 15 янв 2016, 13:09 
Только пришел
Аватара пользователя

Зарегистрирован: 30 мар 2012, 23:43
Сообщения: 29
Откуда: Тихорецк
Все, всем спасибо за конструктивные подсказки, написал на скорую руку черновой вариант и испытал на STM32F100RB(Дискаверина-24МГц), для тех кому интересно полный перебор всего массива методом рекурсии занимает максимум 200мс, если грамотно допилить и использовать STM32F407IGT6 можно получить весьма вкусную скорость. Но даже этих 200мс мне хватит =). Правда функция ищет не максимально приближённое, а точное совпадение, мне и этого достаточно. Массив сортировать нету смысла так как ни одно значение в массиве не превысит контрольную сумму, поэтому использовал полный перебор в лоб =)


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB