Решение комбинаторных задач

Решение комбинаторных задач [c.248]

Таким образом, метод прямого перебора в случае решения комбинаторных задач даже ири использовании современных ЭВМ имеет весьма ограниченную область применения, поскольку возрастание числа вариантов, подлежащих проверке, при увеличении числа стадий и возможных на них состояний может очень быстро превысить возможности любой вычислительной машины. [c.250]

Таким образом, сформулированная выше комбинаторная задача решена до конца. В процессе решения потребовалось исследовать всего Мп вариантов, тогда как при применении метода прямого перебора нужно оценить п различных вариантов. Время решения комбинаторной задачи с п и N = 20 при оценке одного варианта за 1 сек с использованием принципа оптимальности будет равно 20-3 = 180 сек 3 мин, что в сравнении с 3 сек 960 тыс. ч, необходимыми для решения задачи прямым перебором, позволяет весьма ощутимо представить преимущества динамического программирования при решении подобных задач. [c.252]

Метод ветвей и границ используется для решения комбинаторных задач дискретного программирования. Кратко поясним основную сущность метода ветвей и границ. [c.249]

Следует отметить, что при линейной зависимости стоимости теплообменника от поверхности Цт = и при равенстве коэффициентов теплопередачи Kt для всех теплообменников эти эвристические правила переходят в необходимые и достаточные условия оптимальности. На основании эвристических правил на энтальпийной диаграмме для элемента площади холодных потоков подбирается равновеликий элемент площади горячих потоков так, чтобы теплообмен был термодинамически возможен. Иными словами, все равно решается комбинаторная задача, но относительно подбора не пар потоков, а пар элементов площадей на энтальпийной диаграмме. Таким образом, можно считать графический подход комбинаторным, причем решение комбинаторной задачи выполняется на основании эвристических правил. [c.148]

Однако естественные причины часто сокращают дерево вариантов недостаточно, чтобы сделать решение комбинаторной задачи практически возможным, т. е. после сокращения остается меньше, чем m вариантов, но все-таки еще очень большое число. [c.153]

Наиболее наглядно метод динамического программирования можно демонстрировать при решении комбинаторных задач, которые могут быть представлены как многостадийные процессы [c.261]

При таком числе комбинаций решение комбинаторной задачи прямым перебором не представляется возможным. [c.216]

Однако решение комбинаторной задачи посредством линейного программирования [64] возможно только в том случае, если каждой комбинации Г/ (/ = 1,2,..., у) удается поставить в соответствие точку 2-мерного пространства при некотором z, связанном с сущностью задачи. Например, если Q (Г) — некоторая линейная функция точки Г, причем Г — множество вариантов данной задачи, а Ь — выпуклый многогранник, состоящий из всевозможных комбинаций точек множества Г , то комбинаторная задача может бы ть сведена к задаче линейного программирования, заключающейся в максимизации Q (Г) на выпуклом многограннике Ь. Однако это возможно лишь при условии, что многогранник Ь удается задать с помощью системы равенств и неравенств, связывающих компоненты точки Г, т. е. если он может быть представлен как пересечение некоторого числа гиперплоскостей и полупространств точек Г. [c.226]

Обращаясь к нашей задаче, видим, что сведение к линейному программированию не представляется возможным, поскольку функция Q (Г) не является линейной из-за ступенчатого характера функции пропускной способности в дугах подсети. Поэтому мы можем воспользоваться только приближенным методом решения комбинаторной задачи, основанным на эвристике, метода случайного поиска или комбинации случайного поиска и эвристических приемов [24]. [c.226]

В ходе решения комбинаторной задачи оптимизации плана-графика ремонта установок ХТС с последовательно-параллельной [c.226]

Другой принципиальной трудностью, с которой приходится сталкиваться при попытке учесть статистическими методами внутримолекулярные реакции в разветвленных полимерах, является необходимость решения комбинаторной задачи пересчета всех возможных конфигураций макромолекул, имеющих одну и ту же вероятность (или, в случае равновесия, одинаковую свободную энергию образования всех связей). Математически эта трудность связана с тем, что перечисление графов с циклическими фрагментами (циклических графов) является существенно более сложной, по сравнению с деревьями, задачей, не решенной в общем виде до настоящего времени. [c.188]

В рамках второй модели функциональная группа может образовать цикл в подавляющем большинстве случаев только в результате взаимодействия с другими группами, удаленными от нее на некоторое ограниченное расстояние. Отсюда вытекает, что в рассматриваемой модели вероятность образования макромолекул с достаточно большими циклами практически равна нулю. В первой модели Харриса появление бесконечных выражений при расчете ММР полимера связано с непропорционально большой долей именно таких макромолекул. Хотя Харрис при приближенном решении комбинаторной задачи для второй модели использует еще несколько произвольных математических допущений, найденные им результаты качественно верны. В частности, из них следует, что с разбавлением системы конверсия в гель-точке растет, причем существует критическая степень разбавления, выше которой точки гелеобразования совсем не существует. [c.189]

Наиболее наглядно метод динамического программирования можно демонстрировать при решении комбинаторных задач, которые могут быть представлены как многостадийные ироцессы принятия решений, т. е. выбора управления на каждой стадии из некоторого дискретного и конечного набора возможных управлений (решений). [c.248]

Метод програлширования с обратным слежением , который широко используется при решении комбинаторных задач, соответствует процедуре лучевого ветвления с упреждением на т шагов вперед без операции отсечения неперспективных вершин, т. е. соответствует полному перебору на ДВР, реализуемому с использованием стратегии в глубину , или стратегии перебора вершин на ДВР односторонним обходом с просмотром на т шагов вперед. [c.189]

Когда дерево вариантов построено, решение комбинаторной задачи находится следующим образом для всех висячих вершин, для которых 5/ = в", ввчисляется критерий К ,- = /С (в , [c.152]

В работе [41 ] для задачи синтеза оптимальных систем теплообмена были впервые применены вышеизложенные идеи решения комбинаторных задач путем построения сокращенного дерева вариантов. Прежде всего, было введено эвристическое правило в оптимальной схеме теплообмена при теплообмене между какими-то горячим и холодным потоками переходит максимальное количество теплоты, допускаемое минимальным температурным сближением Дттш- Это эвристическое правило резко сокращает дерево вариантов, максимальное число висячих вершин падает от m до от (от до N1 для задачи синтеза систем теплообмена), так как в каждой схеме любая пара потоков встречается только один раз. На первом уровне дерева вариантов возможно N пар потоков, на втором — N (М — 1), на третьем — N (М — ) (Ы — 2) и так далее, на Л -м уровне — N (М — I) (Ы — 2)- - I = N1. Очевидно, что Л < для N 3. [c.154]

Справочник химика 21

Химия и химическая технология