Форум программистов, компьютерный форум CyberForum.ru

Оптимизация лифта - C++

Восстановить пароль Регистрация
 
byshlata
0 / 0 / 0
Регистрация: 25.01.2014
Сообщений: 2
25.01.2014, 11:16     Оптимизация лифта #1
пишу программу к курсовому. саму программу нашел, но выдает неправильное решение. просто не могу понять как связаны между собой функции и что вводить в main. Буду презнателен если кто поможет! Заранее спасибо всем
Пример разработки программы: оптимизация лифта



Я работаю в очень высоком здании с очень медленным лифтом. Особенно меня раздражает, когда люди нажимают кнопки нескольких соседних этажей (скажем, 13, 14 и 15-го), а я еду с нижнего этажа на верхний. Моя поездка наверх прерывается трижды, по разу на каждом из этажей. Было бы гораздо вежливее со стороны этих людей, если бы они нажали только 14-й, а люди с 13-го и 15-го этажей прошли бы по одному этажу пешком. В любом случае кто-то из них мог бы пройтись.

Ваша задача состоит в написании программы оптимизации лифта. Желаемый этаж каждого из пассажиров задается в начале поездки. Далее лифт должен решить, на каких этажах он будет останавливаться. Число остановок лифта не должно превышать к, при этом этажи нужно выбрать так, чтобы свести к минимуму полное число этажей, которое нужно пройти людям вверх или вниз. Можно считать, что лифт знает, сколько человек выходит на каждом этаже.

Мы полагаем, что стоимость подъема на один лестничный пролет равняется стоимости спуска; не забывайте, что у этих людей есть возможность поупражняться. Если однозначного решения не существует, руководство предлагает отдавать предпочтение тем случаям, когда лифт останавливается на минимально возможном этаже, так как на это требуется меньше электричества. Обратите внимание, что лифт вовсе не обязан останавливаться на этажах, указанных пассажирами. Если пассажиры указали 27 и 29 этажи, то лифт вместо этого может остановиться на 28.

Решение начинается ниже

Это пример обычной задачи на программирование/алгоритмы, которая прекрасно решается с помощью динамического программирования. Как мы до этого додумались и что делать дальше?

Вспомните, что алгоритмы динамического программирования основываются на рекурсивных алгоритмах. Решение о том, где лучшего всего сделать к-ю остановку, зависит от стоимости всех возможных решений для к - 1 остановки. Если вы сможете сказать мне стоимость лучшего из частных решений, то я смогу принять верное решение насчет последней остановки.

Эффективные алгоритмы динамического программирования нередко требуют упорядоченных входных данных. Нам важен тот факт, что требования пассажиров можно упорядочить от наименьшего этажа к наибольшему. К примеру, пусть лифт сначала остановился на этаже /у, а затем на этаже f2. Вторая остановка может не иметь никакого значения для пассажира, который хочет попасть на этаж/у или ниже. Это значит, что задачу можно разбить на части. Если мне нужно добавить третью остановку выше f2, то для выбора ее позиции мне не нужно ничего знать о/у.

Мы почувствовали, что задача имеет отношение к динамическому программированию. Как выглядит алгоритм? Для начала нам нужно определить функцию стоимости для частных решений, которая позволит нам принимать более важные решения. Что вы скажете о такой:

Пусть ш [ i ] [ j ] задает минимальную стоимость обслуживания всех пассажиров,

если делается ровно j остановок, последняя из которых делается на этаже /.

Может ли эта функция помочь нам разместить (/ + 1)-ю остановку так, чтобы общая стоимость уменьшилась? Да. (/ + 1)-я остановка по определению должна располагаться выше (j-й) остановки на этаже /. Значит, новая остановка будет интересовать только тех пассажиров, которые хотят выйти выше /-го этажа. Чтобы понять, как это может нам помочь, мы должны правильно разделить пассажиров между новой остановкой и i на основании того, к какой остановке ближе они находятся. Эта идея приводит к заданию следующей рекуррентной последовательности:

m> = mill (mk,j - floors _ walked (к, oo) + floors walked (&,/) + floors _ walked (7,oo)).

k=о

Что она значит? Если последняя остановка совершается на этаже /, то предыдущая должна быть на этаже к < i. Какова стоимость решения в таком случае? Мы должны вычесть из mk у стоимость обслуживания всех пассажиров выше к (то есть floors_walked(?, оо)) и заменить ее (предположительно) уменьшенной стоимостью добавления остановки на этаже i (то есть floors_walked(?, i) + floors_walked(z, оо)).

Основной здесь является функция f loors_walked (а, b). Она подсчитывает полное число этажей, проходимых пассажирами, которые направляются на этажи, лежащие между двумя последовательными остановками а и Ь. Каждый такой пассажир идет к своему этажу кратчайшим путем:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
floors_walked(int previous, int current) {int nsteps=0; int i ;
 
/
 
/* общее пройденное расстояние
 
/* счетчик */for(i=l; i<=nriders; i++)
 
if ((stops[i] > previous) && (stops[i] <= current)) nsteps += min(stops[i]-previous, current-
 
stops [i] ) ;
 
return(nsteps);
 
}
 
Как только вы ухватили основную идею, реализация алгоритма становится очевидной. Мы создаем глобальные матрицы для хранения таблиц динамического программирования. В одной из таблиц хранятся стоимости, в другой - родительские элементы:
 
#define NFLOORS
 
#define MAX_RIDERS 50
 
int stops[MAX_RIDERS]; int nriders; int nstops;
 
int m[NFLOORS+1][MAX_RIDERS]; int p[NFLOORS+1][MAX_RIDERS];
 
/* высота здания в этажах /* вместимость лифта */
 
/* кто на каком этаже выходит */ /* количество пассажиров */ /* число разрешенных остановок */
 
/
 
/* таблица стоимости */ /* таблица родительских элементов */Функция оптимизации - это непосредственная реализация рекуррентного соотношения. Особое внимание уделяется такому расположению циклов, чтобы все величины были подсчитаны к тому моменту, когда они могут понадобиться.int optimize_floor() {
 
int i,j,k; int cost; int laststop;
 
/* счетчики */ /* стоимость */
 
/* последняя остановка лифта */for (i = 0 ; i<=NFLOORS; i + +) {
 
m[i][0] = floors_walked(0,MAXINT); p[i][0] = -1;for (j=l; j<=nstops; j++)
 
for (i = 0; i<=NFLOORS; i + +) { m[i][j] = MAXINT; for (k=0; k< = i; k++) {
 
cost = m[k][j-1] - floors_walked(k,MAXINT) + floors_walked(k / i) + f loors_.walked(i,MAXINT) ; if (cost < m[i] [j 3) { m[i] [j] = cost; p[i] [j] = k;
 
}
 
}
 
}
 
laststop = 0;
 
for (i=l; i<=NFLOORS; i++)
 
if (m[i][nstops] < m[laststop][nstops]) laststop = i;
 
return(laststop);
 
}
 
Наконец, нам нужно восстановить решение. Идея та же, что и в предыдущих примерах: нужно идти по указателям на родительские элементы в обратную сторону.
 
reconstruct__path (int lastfloor, int stops_to_go)
 
{
 
if (stops_to_go > 1)
 
reconstruct_path(p[lastfloor][stops_to_go], stops_to_go-l);
 
printf("%d\n",lastfloor);
 
}
Запустим программу для 10-этажного здания европейского типа (нижний этаж считается нулевым). Для случая, когда по одному пассажиру хочет выйти на каждом этаже от 1-го до 10-го, и разрешена всего одна остановка, получаем, что лучше всего остановиться на 7-м этаже, суммарная стоимость - 18 лестничных пролетов (пассажиры, направляющиеся на этажи 1, 2 и 3-й, должны с нулевого этажа идти пешком). Если разрешено две остановки, то лучше всего остановиться на этажах 3-м и 8-м, стоимость - 11, а лучшие три остановки - это 3, 6 и 9-й этажи, приводящие к суммарной стоимости в 7 пролетов.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.01.2014, 11:16     Оптимизация лифта
Посмотрите здесь:

Оптимизация C++
Оптимизация алгоритмов C++
Модель лифта C++
Программирование классов для моделирования лифта. C++
C++ Оптимизация вычислений
Оптимизация кода C++
C++ Промоделировать в консоли работу лифта
Оптимизация кода C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 17:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru