DjangoBB LoFi version

Начало » Python для новичков » Оптимизация алгоритма

1 2

polsovatel

Дек. 24, 2016 19:56:08

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

Shaman

Дек. 24, 2016 20:56:46

Получилось такое

 from itertools import groupby
 
groups = [1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4]
 
amounts = {k: len(tuple(g)) for k, g in groupby(sorted(groups))}
x4 = amounts.get(4, 0)
x3 = amounts.get(3, 0)
x2 = amounts.get(2, 0)
x1 = amounts.get(1, 0)
 
x12 = x1 - x2 % 2 * 2
if x12 < 0:
    x12 = 0
x13 = x12 - x3
if x13 < 0:
    x13 = 0
y = x4 \
    + x2 // 2 \
    + x2 % 2 \
    + x3 \
    + x13 // 4 \
    + (x13 % 4 > 0)
 
print y

FishHook

Дек. 25, 2016 07:19:45

polsovatel
Может вы сможете его улучшить

Ваш алгоритм не дает решения в общем виде, вы захардкодили требование “четыре человека в машине”, а если мы захотим получить решение для пяти? Вашу программу в этом случае придется переписывать заново практически с нуля. Так, разумеется, не делают. Алгоритмические задачи решают в общем виде, вы должны только изменять константы, не трогая само тело программы.

polsovatel

Дек. 26, 2016 02:08:28

Shaman, Ваш алгоритм тоже неверный. При последовательности 1 1 1 2 2 3 программа вернет 4, но на самом деле будет 3.

FishHook

Дек. 26, 2016 04:50:51

polsovatel
Похоже, что это NP-полная задача, то есть решается только перебором всех вариантов. Ваше решение, как я выше уже писал, если оно работает, то работает только для частного случая, что не есть гуд.

polsovatel

Дек. 26, 2016 13:37:19

Разве если перебирать все варианты программа не будет медленно работать?

FishHook

Дек. 26, 2016 14:08:00

polsovatel
Тормозить - понятие относительное. Обычно в задачах перебора, степень торможения увеличивается с ростом итераций. Может увеличиваться линейно, а может квадратично, а может и экспоненциально. Зависит от алгоритма. Таких задач на самом деле много, взять хотя бы знаменитую задачу коммивояжера. Ваша - одна из таких, надо перебирать все варианты с учетом всех возможных оптимизаций. То есть вам надо придумать алгоритм так, чтобы он работал на любых целочисленных значениях констант MAX_CAR_COPACITY и MAX_GROUP_LEN и расходовал как можно меньше ресурсов. При этом (это чисто моя оценка, я могу быть не прав) вам придется решать NP-полную задачу.

Shaman

Дек. 26, 2016 18:55:08

polsovatel
Shaman, Ваш алгоритм тоже неверный. При последовательности 1 1 1 2 2 3 программа вернет 4, но на самом деле будет 3.

Значит я что-то пропустил, но идея должна быть ясна.

Shaman

Дек. 26, 2016 19:07:38

 y = x4 \
    + x2 // 2 \
    + x2 % 2 \
    + x3 \
    + x13 // 4 \
    + (x13 % 4 > 0) # тут поменялось

Shaman

Дек. 26, 2016 19:12:10

FishHook
вы захардкодили требование “четыре человека в машине”

Это часть условия задачи. Иногда требуется оптимизация именно для частного случая.