Forums.Avtograd.Ru: Алгоритмы - Forums.Avtograd.Ru

Перейти к содержимому

  • (3 Страниц)
  • +
  • 1
  • 2
  • 3
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

Алгоритмы

#1 Пользователь офлайн   parovozik

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 700
  • Регистрация: 01 Ноябрь 07

Отправлено 16 Март 2008 - 11:59

Решил открыть тему для того, чтобы можно было обсудить различные алгоритмы. Задать вопрос, получить ответ, и тд.

Локомотив

0


  • (3 Страниц)
  • +
  • 1
  • 2
  • 3
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

Другие ответы в этой теме

#2 Пользователь офлайн   parovozik

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 700
  • Регистрация: 01 Ноябрь 07

Отправлено 16 Март 2008 - 12:00

Задача планирования работ

Пусть у нас есть набор работ, и мы знаем время, необходимое для завершения каждой из них, t1,t2,…,tN, сроки d1,d2,..,dN, к которым эти работы должны быть обязательно завершены, а также штрафы p1,p2,…,pN, которые будут наложены при незавершении каждой работы в установленные строки. Установить порядок работ, минимизирующий накладываемые штрафы.


Кто что может подсказать? Что почитать? Предполагаю делать на С++.

Локомотив

0

#3 Пользователь офлайн   TRUTHFUL

  • Пользователь
  • PipPip
  • Группа: Модераторы
  • Сообщений: 412
  • Регистрация: 01 Ноябрь 07

Отправлено 16 Март 2008 - 13:10

Просмотр сообщенияparovozik (16.3.2008, 12:00):

Задача планирования работ

Пусть у нас есть набор работ, и мы знаем время, необходимое для завершения каждой из них, t1,t2,…,tN, сроки d1,d2,..,dN, к которым эти работы должны быть обязательно завершены, а также штрафы p1,p2,…,pN, которые будут наложены при незавершении каждой работы в установленные строки. Установить порядок работ, минимизирующий накладываемые штрафы.
Кто что может подсказать? Что почитать? Предполагаю делать на С++.

Почитай тетрадь с лекциями, предположительно по теории принятия решений. Там есть много замечательных алгоритмов оптимизации, таких как например Беллмана.
Истина где-то рядом... Пускай там и остается!
0

#4 Пользователь офлайн   quarck

  • Новичок
  • Pip
  • Группа: Пользователи
  • Сообщений: 83
  • Регистрация: 28 Ноябрь 07

Отправлено 16 Март 2008 - 22:51

Просмотр сообщенияparovozik (16.3.2008, 12:00):

Задача планирования работ

Пусть у нас есть набор работ, и мы знаем время, необходимое для завершения каждой из них, t1,t2,…,tN, сроки d1,d2,..,dN, к которым эти работы должны быть обязательно завершены, а также штрафы p1,p2,…,pN, которые будут наложены при незавершении каждой работы в установленные строки. Установить порядок работ, минимизирующий накладываемые штрафы.
Кто что может подсказать? Что почитать? Предполагаю делать на С++.


Рекомендую для начала погуглить про NP-сложные задачи :)

P.S. Если это для частного применения, то может просто взять готовый MS-Project, что-бы не изобретать велосипед?
Я поменял пароль на рандомный, считайте я удалил свой аккаунт, никому отвечать не смогу не хочу и не буду по этой причине.
0

#5 Пользователь офлайн   Saray

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 2 388
  • Регистрация: 31 Январь 08

Отправлено 17 Март 2008 - 08:40

Просмотр сообщенияparovozik (16.3.2008, 12:00):

Задача планирования работ

Пусть у нас есть набор работ, и мы знаем время, необходимое для завершения каждой из них, t1,t2,…,tN, сроки d1,d2,..,dN, к которым эти работы должны быть обязательно завершены, а также штрафы p1,p2,…,pN, которые будут наложены при незавершении каждой работы в установленные строки. Установить порядок работ, минимизирующий накладываемые штрафы.
Кто что может подсказать? Что почитать? Предполагаю делать на С++.

погугли про симплекс метод (оптимальное нахождение екстремумов сложных функций с множеством аргументов)
В том случае если время выполнения задач не зависит от выполнения соседних или связанных задач, то вобще не вижу ничего умного - банальный перебор всех вариантов :P
Если женщина не права, нужно извиниться и замолчать.
0

#6 Пользователь офлайн   quarck

  • Новичок
  • Pip
  • Группа: Пользователи
  • Сообщений: 83
  • Регистрация: 28 Ноябрь 07

Отправлено 17 Март 2008 - 10:21

Просмотр сообщенияSaray (17.3.2008, 8:40):

погугли про симплекс метод (оптимальное нахождение екстремумов сложных функций с множеством аргументов)
В том случае если время выполнения задач не зависит от выполнения соседних или связанных задач, то вобще не вижу ничего умного - банальный перебор всех вариантов :P


Единственная проблема -- очень быстро растущее, при увеличении чиста задач, время перебора, - сравномо с экспонентой, а если более точно - пропорциональное примерно факториалу.
Я поменял пароль на рандомный, считайте я удалил свой аккаунт, никому отвечать не смогу не хочу и не буду по этой причине.
0

#7 Пользователь офлайн   Saray

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 2 388
  • Регистрация: 31 Январь 08

Отправлено 17 Март 2008 - 10:41

Просмотр сообщенияquarck (17.3.2008, 10:21):

Единственная проблема -- очень быстро растущее, при увеличении чиста задач, время перебора, - сравномо с экспонентой, а если более точно - пропорциональное примерно факториалу.

не примерно пропорциональное, а равное факториалу вариантов:
кол-во | кол-во
задач | вариантов
-----------------------
1 | 1
2 | 2
3 | 6
4 | 24

действительно, не вариант :blink:
Если женщина не права, нужно извиниться и замолчать.
0

#8 Пользователь офлайн   parovozik

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 700
  • Регистрация: 01 Ноябрь 07

Отправлено 17 Март 2008 - 11:16

Просмотр сообщенияTRUTHFUL (16.3.2008, 13:10):

Почитай тетрадь с лекциями, предположительно по теории принятия решений. Там есть много замечательных алгоритмов оптимизации, таких как например Беллмана.


лекции)) если б их дали, почитал бы) А так приходится самому.
Что касается перебора, то не вариант. Нужно что-то типа эвристики.

Спасибо буду думать.

Локомотив

0

#9 Пользователь офлайн   Saray

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 2 388
  • Регистрация: 31 Январь 08

Отправлено 17 Март 2008 - 11:44

Функция распреедления издержек от порядка выполнения операций многомерная и нелинейная, без четко выраженных максимумов,
если перебрать все варианты нет возможности, то попробуем ограничить область поиска (правда при этом возникает риск не нахождения самого оптимального решения, симплекс методом тоже можно не найти самое оптимальное )
Возникла такая идея попроще:
каким то образом просчитать "вес" каждой задачи и отсортировать по нему список, далее в этом списке брать первый элемент, смещать пузырьком вверх-вниз на ограниченное число позиций (типа задавать глубину поиска) и просчитывать суммарный штраф до нахождения минимума, потом второй и т.д. в результате отбирать самый минимальный общий результат.
"вес" задачи можно просчитать например так: срок * штраф / время выполнения
вобще задачка сама по себе интересная :P
Если женщина не права, нужно извиниться и замолчать.
0

#10 Пользователь офлайн   quarck

  • Новичок
  • Pip
  • Группа: Пользователи
  • Сообщений: 83
  • Регистрация: 28 Ноябрь 07

Отправлено 17 Март 2008 - 13:49

Просмотр сообщенияSaray (17.3.2008, 10:41):

не примерно пропорциональное, а равное факториалу вариантов:
кол-во | кол-во
задач | вариантов
-----------------------
1 | 1
2 | 2
3 | 6
4 | 24

действительно, не вариант :blink:


Примерно -- потому что что-то может удастся соптимизировать, какие-то проверки исключить.
Я поменял пароль на рандомный, считайте я удалил свой аккаунт, никому отвечать не смогу не хочу и не буду по этой причине.
0

#11 Пользователь офлайн   quarck

  • Новичок
  • Pip
  • Группа: Пользователи
  • Сообщений: 83
  • Регистрация: 28 Ноябрь 07

Отправлено 17 Март 2008 - 14:01

Просмотр сообщенияSaray (17.3.2008, 11:44):

Функция распреедления издержек от порядка выполнения операций многомерная и нелинейная, без четко выраженных максимумов,
если перебрать все варианты нет возможности, то попробуем ограничить область поиска (правда при этом возникает риск не нахождения самого оптимального решения, симплекс методом тоже можно не найти самое оптимальное )
Возникла такая идея попроще:
каким то образом просчитать "вес" каждой задачи и отсортировать по нему список, далее в этом списке брать первый элемент, смещать пузырьком вверх-вниз на ограниченное число позиций (типа задавать глубину поиска) и просчитывать суммарный штраф до нахождения минимума, потом второй и т.д. в результате отбирать самый минимальный общий результат.
"вес" задачи можно просчитать например так: срок * штраф / время выполнения
вобще задачка сама по себе интересная :P


Таки советую почитать статьу в википедии: http://en.wikipedia....iki/NP-complete и то, какие существуют решениея различных NP-полных задач, например вот хотя-бы, очень похожая по сути задача: http://en.wikipedia....alesman_problem (Задача о коммивояжёре)

Или о: http://en.wikipedia....ignment_problem --вообще 1-в-1
Я поменял пароль на рандомный, считайте я удалил свой аккаунт, никому отвечать не смогу не хочу и не буду по этой причине.
0

#12 Пользователь офлайн   Saray

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 2 388
  • Регистрация: 31 Январь 08

Отправлено 17 Март 2008 - 14:16

Угу, вобще задачи по логистике очень похожи на эту...
Если женщина не права, нужно извиниться и замолчать.
0

#13 Пользователь офлайн   Barrabas

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 431
  • Регистрация: 01 Ноябрь 07

Отправлено 17 Март 2008 - 15:10

http://www.mtas.ru/uploads/file_44.pdf
0

#14 Пользователь офлайн   KORENHACK

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 464
  • Регистрация: 01 Ноябрь 07

Отправлено 20 Март 2008 - 08:12

Алгоритм упорядочиния динамически растущего массива 4го измерения на С?
0

#15 Пользователь офлайн   KORENHACK

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 464
  • Регистрация: 01 Ноябрь 07

Отправлено 02 Апрель 2008 - 16:09

Как я написал, так все и замолкли :huh:
0

#16 Пользователь офлайн   TRUTHFUL

  • Пользователь
  • PipPip
  • Группа: Модераторы
  • Сообщений: 412
  • Регистрация: 01 Ноябрь 07

Отправлено 02 Апрель 2008 - 20:30

Просмотр сообщенияKORENHACK (2.4.2008, 17:09):

Как я написал, так все и замолкли :huh:

Ерунду потому что написал :)
Истина где-то рядом... Пускай там и остается!
0

#17 Пользователь офлайн   KORENHACK

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 464
  • Регистрация: 01 Ноябрь 07

Отправлено 03 Апрель 2008 - 08:16

Заметь, ты не сказал мне как эту ерунду реализовать :D
Потому что это не ерунда, а "хз как написать" алгоритм.
0

#18 Пользователь офлайн   Barrabas

  • Пользователь
  • PipPip
  • Группа: Пользователи
  • Сообщений: 431
  • Регистрация: 01 Ноябрь 07

Отправлено 05 Апрель 2008 - 12:29

Просмотр сообщенияKORENHACK (3.4.2008, 9:16):

Заметь, ты не сказал мне как эту ерунду реализовать :D
Потому что это не ерунда, а "хз как написать" алгоритм.

это ерунда.
что значит "упорядочиние массива"?
если имелось ввиду сортировка, то алгоритмов полно, а колво измерений роли вобще не играет, всегда можно использовать структуру/класс с нужным кол-вом одномерных массивов в качестве членов (причем во многих языках нет даже двумерных массивов ибо незачем, делаешь класс и вперед)

У каждой задачи должна быть практическая цель, смысла в четырехмерном массиве я не вижу (почему не 56-ти мерном кстати?) если это какието сущности выраженные в 4х значениях, то и нужно сделать структуру/класс этой сущности и потом уже реализовать массив их
0

#19 Пользователь офлайн   Saray

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 2 388
  • Регистрация: 31 Январь 08

Отправлено 08 Апрель 2008 - 13:39

Наверное имелась ввиду мультисортировка четырёхмерного массива по типу:

select t1.text, t2.text, t3.text, t4.text
from t1, t2, t3, t4
where t1.id = t2.id2 and t2.id = t3.id2 and t3.id = t4.id2
order by 3,2,1,4

Если женщина не права, нужно извиниться и замолчать.
0

#20 Пользователь офлайн   KORENHACK

  • Старожил
  • PipPipPipPipPip
  • Группа: Пользователи
  • Сообщений: 1 464
  • Регистрация: 01 Ноябрь 07

Отправлено 08 Апрель 2008 - 18:59

Надо упорядочивать массив, который динамически меняет кол-во свих измерений!
Так тяжело это понять?

Почему все, что Вы не в состоянии сделать называйте ерундой?

Есть массив. Он начинает БЕСКОНЕЧНО расти (растет как кол-во измерений так и размеры уже готовых измерений) и заполняться случайными числами. Его надо сортировать по возрастанию (убыванию) по мере прибавления измерений.

Теперь думаю всем понятно. Алгоритм можно описать на С или Дельфи.
0

  • (3 Страниц)
  • +
  • 1
  • 2
  • 3
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

1 человек читают эту тему
0 пользователей, 1 гостей, 0 скрытых пользователей