Я уже несколько дней пытаюсь реализовать этот алгоритм на Python. Я постоянно возвращаюсь к этому, просто сдаюсь и расстраиваюсь. Я не знаю, что происходит. Мне не к кому обратиться за помощью, и я пришел сюда.
Предупреждение в формате PDF: http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf
Я не думаю, что это четко объяснено, я точно не поймите.
Я понимаю, что происходит так:
У нас есть набор точек (x1, y1), (x2, y2) ... и мы хотим найти некоторые линии, которые лучше всего подходят для этих данных. У нас может быть несколько прямых линий, и эти линии взяты с заданных форумов для a и b (y = ax + b).
Теперь алгоритм начинается с конца (?) И предполагает, что точка p (x_i, y_i) является частью отрезка линии. Тогда в примечаниях говорится, что оптимальное решение - это оптимальное решение для {p1,. . . pi − 1} плюс (лучшая) прямая, проходящая через {pi,. . . pn} '. Для меня это просто означает, что мы идем в точку p (x_i, y_i), идем назад и находим другой отрезок прямой через остальные точки. Теперь оптимальным решением являются оба этих отрезка.
Затем выполняется логический переход, за которым я не могу следить, и он говорит: «Предположим, последняя точка pn является частью сегмента, который начинается в p_i. Если Opt (j) обозначает стоимость первых j точек, а e (j , л)