Easyelectronics.ru

Электроника для всех
Текущее время: 02 июн 2020, 09:59

Часовой пояс: 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
Сообщения: 689
Доброго времени суток !

Честно говоря я ничего не понял. Какой алгоритм вам нужен ? Вы выбрали алгоритм перебора, что же вам подсказать ? почему для поиска максимально приближённого значения нужно 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
Сообщения: 4629
Откуда: КЧР, поселок Нижний Архыз
Ну так формулировать задачу надо правильно! А то вопрос - "задача о рюкзаке", а формулировка - бред какой-то.

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


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

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


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

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


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

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


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

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

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


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

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

_________________
Потоковая OS


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

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


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

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

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


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

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

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


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

Зарегистрирован: 24 июн 2011, 14:05
Сообщения: 307
Откуда: Новочеркасск
Может не так понял задачу, но как тут сказали отсортируйте массив по убыванию скажем, потом находите ближайший элемент с меньшей стороны (например дано число 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 часов


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

Сейчас этот форум просматривают: Google [Bot]


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

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

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