Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Dezmound_m
3 / 3 / 3
Регистрация: 25.02.2014
Сообщений: 20
#1

Задача о точках и отрезках. Метод динамического программирования - Алгоритмы

26.10.2014, 20:09. Просмотров 763. Ответов 7
Метки нет (Все метки)

Добрый вечер, помогите пожалуйста разработать алгоритм для решения задачи:
На прямой задано N точек. Каждая точка должна быть соединена со следующей или с предыдущей отрезком. Соединить точки так, чтобы суммарная длина отрезков была минимальной.
Как решить эту задачу с помощью метода динамического программирования? Хотя бы подскажите литературу которая поможет разобраться в этом методе.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.10.2014, 20:09
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Задача о точках и отрезках. Метод динамического программирования (Алгоритмы):

Задача о размене -задача динамического программирования?
Является ли задача о размене суммы задачей динамического программирования? Мне...

Метод динамического программирования для задачи поиска наибольшей чередующейся подпоследовательности
Задача о поиске наибольшей чередующейся подпоследовательности. Имеется...

Алгоритм решения задач динамического программирования
Здравствуйте, нужно решить следующую задачу посредством метода динамического...

Задача линейного программирования
Помогите решить задачу.

Задача о ранце. Для ее решения использовать метод динамического программирования
Товарищи, помогите пожалуйста с программной реализацией задачи о ранце. ...

Метод динамического программирования
Доброго времени суток! Ребят такая ситуация, на носу сдача диплома, а я ещё не...

7
echs
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
27.10.2014, 08:46 #2
Задача не совсем понятна. Если точки лежат на прямой.
То их можно просто соединить с соседними и получить
минимум. Или я не понял? Или условия иные?
0
Dezmound_m
3 / 3 / 3
Регистрация: 25.02.2014
Сообщений: 20
04.11.2014, 15:16  [ТС] #3
geh, Задача сводится к нахождению такого решения:
0
Миниатюры
Задача о точках и отрезках. Метод динамического программирования  
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
05.11.2014, 10:33 #4
Все равно неясно. Можно привести пример др отрезков для тех же точек? (неважно оптимальный или нет)
0
Dezmound_m
3 / 3 / 3
Регистрация: 25.02.2014
Сообщений: 20
05.11.2014, 11:14  [ТС] #5
Igor3D, Я покажу на примере. Допустим на оси X лежат 4 точки 0,2,5,7. То есть у нас получается 3 отрезка с длинами 2,3,2 соответственно. Так как каждая точка обязательно должна быть соединена в отрезок со следующей или предыдущей мы получаем, то что точки 0 и 2, нужно обязательно соединить в отрезок размера 2 и точки 5 и 7 в отрезок размера 2 (так как точки 0 и 7 - конечные).
Ну, а точки 2 и 5 соединять не обязательно, так как они уже имеют связь. И мы получаем, что минимальная сумма длин отрезков = 2. Решение показано на первом рисунке.

С увеличением числа точек, увеличивается количество ненужных отрезков, которые соединяют точки. Если в предыдущем примере добавить еще одну точку 8. То у нас будет выбор, какой из отрезков удалить, а какой оставить. То есть удалить (2;5) или удалить (5;7). Выбираем (2;5) так как его длина максимальна. И получается что суммарная длина отрезков = 5. Ответ показан на рисунке 2.
0
Миниатюры
Задача о точках и отрезках. Метод динамического программирования   Задача о точках и отрезках. Метод динамического программирования  
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
05.11.2014, 17:47 #6
Лучший ответ Сообщение было отмечено Dezmound_m как решение

Решение

Спасибо, понял. Да, тут просто динамика.
C++
1
2
3
4
struct CPoint {
  int x;   // координата
  int len0, len1;
};
len0 - это длина пути от первой точки к данной если есть отрезок предыдущая/данная. Как бы "пришли отрезком"

len1 - это длина пути от первой точки к данной если такого отрезка нет, "пришли прыжком из предыдущей"

Сканируем оба пути
C++
1
2
3
4
5
6
7
8
9
10
11
12
CPoint pt[N];
// задаете x по возрастающей
pt[0].len0 = pt[0].len1 = 0;
pt[1].len0 = pt[1].len1 = 0;
 
for (i = 2; i < N - 1; ++i) {
// "отрезок"
 pt[i].len0 = MIN(pt[i - 1].len0, pt[i - 1].len1) + (pt[i].x - pt[i - 1].x);   
 
// "прыжок"
 pt[i].len1 = pt[i - 1].len0;
}
Имеем 2 длины в каждой точке. Теперь раскручиваем назад

C++
1
2
3
4
5
6
7
8
9
int sum = 0,  sum1 = 0;
for (int i = N - 2; i > 1; --i) {
// путь "отрезком" короче 
 if (pt[i].len0 - sum0 < pt[i].len1 - sum1) {
  printf("segment %d-%d\n", i - 1, i); 
  sum1 = sum;
  sum0 += pt[i].x - pt[i - 1].x;
 }
}
1
Dezmound_m
3 / 3 / 3
Регистрация: 25.02.2014
Сообщений: 20
05.11.2014, 18:26  [ТС] #7
Igor3D, Огромное вам спасибо! Все сразу стало понятно, один вопрос только - должна ли на "раскрутке" быть ветка else? На моих тестовых данных это условие постоянно не выполнялось.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
05.11.2014, 19:53 #8
Цитата Сообщение от Dezmound_m Посмотреть сообщение
один вопрос только - должна ли на "раскрутке" быть ветка else? На моих тестовых данных это условие постоянно не выполнялось
Тут я маленько насвистел, не минус а плюс
C++
1
2
3
4
5
6
7
8
9
10
int sum0 = 0, sum1 = 0;
for (int i = N - 2; i > 1; --i) {
 if (pt[i].len0 + sum0 <= pt[i].len1 + sum1) {
  printf("segment %d-%d\n", i - 1, i); 
  sum1 = sum0;
  sum0 += pt[i].x - pt[i - 1].x;
 }
 else 
   sum0 = sum1;
}
Смысл такой: находясь точке мы уже знаем длину до конца (sum1). И у нас есть выбор как подключить начало - через отрезок (len0 + sum1 + отрезок) или прыжком (len1 + sum1), выбираем меньшее. А вот в случае прыжка надо забыть об отрезке (что был добавлен к sum0). Все-таки нужен else!
0
05.11.2014, 19:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2014, 19:53
Привет! Вот еще темы с решениями:

Задача методом динамического программирования
Добрый день. Передо мной стоит решение задачи методом динамического...

Задача коммивояжера методом динамического программирования
Помогите пожалуйста переделать коммивояжера методом динамического...

Задача о выборе траектории методом динамического программирования
Очень нужна программа. Помогите пожалуйста.

Задача о выборе траектории методом динамического программирования
Необходимо проехать от Киева до Симферополя. Возможны несколько путей...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru