Главная страница « Информация « 4 курс « курс ВвФП «

Варианты задания «Генетическое программирование». 2016-17 учебный год


«Нет проблем! Мы можем покончить с этой ерундой за выходные!»
Э. Йордон «Путь камикадзе»

Общие сведения о задании


Задание разработано к. ф.-м. н. А. В. Черновым и использовалось при ведении практикума 327, 328 групп в течение ряда лет. Из-за того, что сейчас не используется система автоматического тестирования, в исходный текст были внесены изменения. Также добавлены несколько не использованных в прошлом вариантов задач.

Решите предлагаемые задачи, используя алгоритмы «генетического программирования». Вам необходимо самостоятельно определить, что является «хромосомой», «популяцией», как выполняется «скрещивание», «мутация» и «отбор лучших особей». В процессе реализации метода необходимо подобрать параметры «генетического алгоритма» таким образом, чтобы добиться наилучшей скорости сходимости и точности.

Все задачи сформулированы в виде задач проверки свойств, то есть требующих ответ #f или #t в зависимости от того, существует ли какое-либо решение задачи, удовлетворяющее указанным свойствам. Однако в случае если решение существует, должно быть напечатано решение, оптимальное по некоторому параметру.

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

Следует использовать версию языка scheme/base (начинайте свой код с директивы #lang scheme/base). Использование в программе мутаторов (присваиваний и т. п.) запрещено. Разрешено использовать библиотеки из Racket Core Libraries и только их.

Выполнения задания разделено на три этапа. На первом этапе разрабатываются тесты, на которых будет проверяться программа. Набор тестов должен быть достаточно большим. В набор должны входить тесты для разных тестовых случаев. Например, тесты на каждый вариант ответа (на #f и на #t). Для каждого теста должен быть известен ответ. Часто, полный ответ не однозначен, и требуется функция-чеккер. В набор должны входить тесты достаточно большого объёма. Предполагается, что из-за большого объёма тесты будут генерироваться с помощью составленной Вами вспомогательной программы. Программа, генерирующая тесты, сдаётся вместе с тестами. Также сдаётся программа (или скрипт/скрипты не на Scheme), автоматизирующие процесс тестирования. Будьте готовы дать пояснения и обоснования выбранных Вами тестовых случаев, способов генерации тестов, функции-чеккера, организации тестирования. Максимальная оценка за 1-й этап -- 10 баллов. Срок сдачи без штрафа: по 15 ноября включительно.

На втором этапе разрабатывается версия программы, которая находит решение. Программа должна проходить все или почти все тесты с первого этапа и, возможно, дополнительные тесты. Код программы должен быть правильно оформлен, структурирован, сопровождён комментариями. Максимальная оценка за 2-й этап -- 20 баллов. Срок сдачи без штрафа: по 6 декабря включительно.

На завершающем этапе готовится отчет о выполненном задании. Отчёт сдаётся по электронной почте в электронной форме в формате PDF. Требования к отчёту указаны ниже. Максимальная оценка за 4-й этап -- 5 баллов. Срок сдачи без штрафа: по 19 декабря включительно.

На всех этапах за каждую неделю просрочки сдачи этапа будет начисляться штраф в размере 1/4 от максимального балла. По прошествии 4-х недель этап можно сдать, но баллы начислены не будут. Студенты не сдавшие задание (в том числе -- отчёт!) не смогут получить положительную оценку на экзамене.

Требования к отчёту

Отчёт пишется на русском языке. Текст отчёта должен быть разбит на следующие части:

  • Титульный лист, с «шапкой» – «Московский государственный университет имени М. В. Ломоносова, факультет Вычислительной математики и кибернетики». Далее следует заголовок: «Отчёт по второму заданию», номер и тема варианта задания, сведения об исполнителе (фамилия, имя и отчество полностью, номер группы). Внизу титульного листа указывается город и год. Нелишне обратить внимание на то, что точки после заголовков не ставятся.

  • Содержание состоит из перечня названий глав и подглав, сопровождаемых указанием номеров страниц, с которых они начинаются. Нумеруются все страницы, за исключением титульного листа. Номер страницы с содержанием: 2.

  • Первая глава, названная «Постановка задачи», содержит формулировку задания. Каждую главу следует начинать с новой страницы.

  • Вторая глава, названная «Генерация тестов», содержит описание рассматриваемых тестовых случаев, описание параметров тестовых наборов, основные детали реализации генератора тестов, пояснения по организации автоматизированного тестирования.

  • Третья глава, названная «Генетический алгоритм», содержит описание хромосомы, описание способа создания начальной популяции, описание оценочной функции, описание операций скрещивания и мутации, описание способа отбора, описание критерия останова, изменения в традиционной схеме генетического алгоритма (если таковые были сделаны), основные детали реализации генетического алгоритма.

  • Четвёртая глава, названная «Результаты», содержит анализ результатов работы программы. Следует охарактеризовать результаты, полученные на тестовых наборах, которые относятся к разным тестовым случаям. В том числе следует проиллюстрировать процесс решения графиками функции пригодности лучшей особи, худшей, пригодности в среднем. Если на каких-то тестовых наборах получены неоптимальные или неверные результаты, следует проанализировать и описать причины этого. Необходимо привести сведения о времени, которое ушло на выполнение тестов.

  • Заключение (которое не нумеруется, но номер на странице ставится), где подводится общий итог работы, завершает отчёт. В заключении можно указать характеристики написанного кода, привести соображения о том, насколько удачно удалось применить генетический алгоритм к решению доставшейся Вам задачи.

  • Список использованной литературы приводится, если в ходе работы над заданием были использованы статьи и/или книги. Библиографические записи в списке следует оформлять по рекомендациям ГОСТ. На каждую запись списка в тексте отчёта должна быть ссылка.

  • Приложение, которое содержит Ваш код.

На всякий случай, приведён вид страницы с содержанием (без указания номеров страниц для 2 главы и последующих частей отчёта)
Содержание
1. Постановка задачи ....................3
2. Генерация тестов ......................
3. Генетический алгоритм .................
4. Результаты ............................
Заключение ...............................
Список литературы ........................
Приложение. Код программы.................


Список вариантов

  1. Упаковка в контейнеры

  2. Задача о рюкзаке

  3. Раскраска вершин графа

  4. Раскраска рёбер графа

  5. Доминирующее множество вершин

  6. Задача коммивояжёра

  7. Расписание заданий в многопроцессорной системе

  8. Клика

  9. Прямоугольное сжатие картинки

  10. Разрезание циклов вершинами

  11. Задача о ранце

  12. Разрезание циклов рёбрами

  13. Независимое множество

  14. Максимальный разрез графа

  15. Доминирующее множество рёбер

  16. Выполнимость КНФ

  17. Задача сельского почтальона

  18. Задача о рюкзаках

Вариант 1. Упаковка в контейнеры


На вход программе подаются два списка: список длины N (N > 0) весов предметов Wi (Wi >0, 1≤i≤N) и список длины K (K >0) вместимостей контейнеров Cj (Cj >0, 1≤ j ≤K). Все веса и вместимости -- целые числа.
Существует ли такое разбиение N предметов по K контейнерам, что для каждого предмета i есть контейнер j, в котором он размещён, и для каждого контейнера j вес всех предметов, в нём размещённых, не превышает Cj? Если такое разбиение существует, напечатайте #t, затем количество использованных контейнеров, а затем само разбиение. Если разбиения не существует, напечатайте #f.
Из всех допустимых разбиений выберите разбиение, которое использует минимальное количество контейнеров. Разбиение печатайте в виде списка содержимого контейнеров. Содержимое контейнера -- это список номеров размещённых в нем предметов.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
(1 2 2 3)
(4 4)
Пример печати результата:
#t
2
((1 4) (2 3))

Вариант 2. Задача о рюкзаке


На вход программе подаются два списка длины N (N > 0) список весов предметов Wi (Wi > 0, 1 ≤ i ≤ N) и список их стоимостей Ci (Ci > 0, 1 ≤ i ≤ N). Все веса и стоимости предметов -- целые числа. Затем на вход программе подаются два целых числа B (B > 0) и K (K > 0).
Существует ли такое подмножество предметов, для которого суммарный вес предметов в этом подмножестве не превышает B, а суммарная стоимость предметов не меньше K? Если такого подмножества не существует, напечатайте #f. Если такое подмножество существует, напечатайте #t, затем суммарный вес предметов, их суммарную стоимость, а затем список номеров предметов, вошедших в это подмножество. Из всех возможных разбиений выберите такое, которое максимизирует суммарную стоимость предметов в рюкзаке.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
(1 1 2 2)
(4 3 2 1)
3
4
Пример печати результата:
#t
2
7
(1 2)

Вариант 3. Раскраска вершин графа


На вход программы подаётся список рёбер неориентированного графа G = (V, E). Вершины vi∈V обозначаются атомами, рёбра представляются списками вида (NODE1 NODE2). Затем на вход программы подаётся целое число K (1 ≥ K).
Можно ли раскрасить вершины графа G не более чем в K цветов, то есть существует ли функция c : V → {1. . .K} такая, что если (u, v)∈E, то c(u) ≠ c(v)? Если раскраски вершин графа в K цветов не существует, напечатайте #f. Если раскраска вершин графа существует, то сначала напечатайте #t, затем количество цветов, в которые раскрашен граф, а затем список вершин с указанием их цветов. Элементами этого списка являются списки из двух элементов следующего вида (NODE COLOR). Из всех возможных вариантов раскраски выберите тот, который требует минимального количества цветов.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b) (b c) (c d) (a d))
2
Пример печати результата:
#t
2
((a 1)(b 2)(c 1)(d 2))

Вариант 4. Раскраска рёбер графа


На вход программы подаётся список рёбер неориентированного графа G = (V, E). Вершины vi∈V обозначаются атомами, рёбра представляются списками вида (NODE1 NODE2). Затем на вход программы подаётся целое число K (1 ≤ K).
Можно ли раскрасить ребра графа G не более чем в K цветов, то есть существует ли функция c : E → {1. . .K} такая, что если (u, v), (u, w), (x, u) ∈E, то c((u, v)) ≠ c((u, w)) и c((u, v)) ≠ c((x, u)) при v ≠ w и v ≠ x? Если раскраски рёбер графа в K цветов не существует, напечатайте #f. Если раскраска рёбер графа существует, то сначала напечатайте #t, затем количество цветов, в которые раскрашен граф, а затем список рёбер с указанием их цветов. Элементами этого списка являются списки из двух элементов следующего вида ((NODE1 NODE2) COLOR). Из всех возможных вариантов раскраски выберите тот, который требует минимального количества цветов.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b) (b c) (c d) (a d))
2
Пример печати результата:
#t
2
((a b) 1)((b c) 2)((c d) 1)((a d) 2))

Вариант 5. Доминирующее множество вершин


На вход программы подаётся список рёбер неориентированного графа G = (V, E). Вершины vi∈V обозначаются атомами, рёбра представляются списками вида (NODE1 NODE2). Затем на вход программы подаётся целое число K (1 ≤ K).
Существует ли в графе G доминирующее подмножество вершин, то есть такое подмножество вершин W ⊆ V, что |W| ≤ K и каждая вершина v не из этого подмножества вершин (v ∈ V-W) соединена ребром по крайней мере с одной вершиной из множества W? Если доминирующего подмножества вершин не существует, напечатайте #f. Если доминирующее подмножество вершин существует, напечатайте #t, затем количество вершин в доминирующем подмножестве, а затем список вершин, входящих в доминирующее подмножество. Из всех возможных вариантов доминирующего подмножества выберите вариант с минимальным количеством вершин.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b) (a c) (a d))
1
Пример печати результата:
#t
1
(a)

Вариант 6. Задача коммивояжёра


На вход программе подаётся описание взвешенного неориентированного графа G = (V, E) в виде списка описаний рёбер. Каждое описание ребра e ∈ E имеет вид (NODE1 NODE2 WEIGHT), где NODE1, NODE2 -- атомы, WEIGHT -- целое положительное число. Затем на вход программе подаётся целое положительное число K.
Существует ли в графе G гамильтонов цикл, то есть путь, начинающийся и заканчивающийся в одной и той же вершине и проходящий через каждую вершину только один раз, стоимости не более чем K? Стоимость пути -- это суммарная стоимость рёбер, составляющих путь. Если гамильтонов цикл не существует, напечатайте #f. Если гамильтонов цикл существует, напечатайте #t, далее стоимость цикла, а затем гамильтонов цикл в виде списка. Первым и последним элементом списка должен быть один и тот же атом. Если существует несколько возможных гамильтоновых путей, найдите путь с минимальной стоимостью.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b 1) (b c 1) (c d 1) (a d 1))
4
Пример печати результата:
#t
4
(a b c d a)

Вариант 7. Расписание заданий в многопроцессорной системе


На вход программе подаётся список длины N (N > 0) длительностей заданий Ti (Ti >0, 1≤i≤N) и K (K >0) -- количество процессоров в многопроцессорной системе и T -- контрольное время. N, K, Ti и T -- натуральные числа.
Существует ли такое расписание N заданий по K процессорам, что для каждого задания i есть процессор j, на котором оно выполняется, и для каждого процессора j суммарная длительность выполняемых на нём заданий не превышает контрольного времени T? Считается, что задания на каждом процессоре выполняются строго последовательно. Считается, что процессоры одинаковы и длительность задания не зависит от того, на каком процессоре оно считается. Если такое расписание существует, напечатайте #t, затем время, необходимое для выполнения всех заданий, а затем список последовательностей номеров заданий для каждого процессора. Если расписания не существует, напечатайте #f.
Из всех допустимых расписаний выберите то, при котором минимизируется время, необходимое для выполнения всех заданий. Расписание печатайте в виде списка последовательностей номеров заданий для каждого процессора.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
(1 2 2 3)
2
4
Пример печати результата:
#t
4
((1 4) (2 3))

Вариант 8. Клика


На вход программе подаётся описание неориентированного невзвешенного графа G = (V, E) в виде списка описаний рёбер. Вершины vi∈V обозначаются атомами, рёбра представляются списками вида (NODE1 NODE2). Затем на вход программе подаётся целое число K (1 ≤ K ≤ |V|).
Существует ли в графе G клика мощности, не меньшей K? Кликой графа называется полный подграф графа. Мощность клики -- это количество вершин в ней. Если такой клики не существует, напечатайте #f. Если клика существует, напечатайте #t, затем мощность клики, затем список вершин, входящих в клику. Из всех возможных решений задачи, удовлетворяющих условию, выберите решение с максимальной мощностью клики.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b) (b c) (c d) (a d) (a c))
3
Пример печати результата:
#t
3
(a b c)

Вариант 9. Прямоугольное сжатие картинки


На вход программы подаётся квадратная битовая матрица M размера NxN (Mij∈{0, 1}). Матрица вводится в виде списка из N строк матрицы, где каждая строка -- это список из N элементов матрицы. Затем задаётся положительное целое число K.
Можно ли покрыть все единичные элементы матрицы M не более чем K прямоугольниками? Другими словами, существует ли такая последовательность четвёрок (ai, bi, ci, di) (1 ≤ i ≤ K, 1 ≤ ai, bi, ci, di ≤ N, ai ≤ ci, bi ≤ di), в которой ai, ci -- это номера строк матрицы, а bi, di -- номера столбцов. Эта последовательность должна удовлетворять условию, что любой единичный элемент матрицы должен покрываться хотя бы одним прямоугольником, и любой прямоугольник должен состоять только из единиц. Если такого покрытия не существует, напечатайте #f. Если покрытие существует, напечатайте #t, затем количество прямоугольников, а затем список описаний прямоугольников. Каждое описание прямоугольника представляет собой список из 4 элементов как описано выше.

В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((1 1 0 0) (1 1 0 0) (0 0 1 1) (0 0 1 1))
2
Пример печати результата: #t
2
((1 1 2 2) (3 3 4 4))

Вариант 10. Разрезание циклов вершинами


На вход программе подаётся описание невзвешенного ориентированного графа G = (V, E) в виде списка рёбер. Вершины графа vi∈V представлены атомами, а описание каждого ребра имеет вид (FROM TO). Затем на вход программе подаётся число K.
Существует ли в графе G такое подмножество вершин W (W ⊆ V) мощности не большей K, что каждый цикл в графе G содержит хотя бы одну вершину из множества W? Если такого подмножества вершин не существует, напечатайте #f, а если такое подмножество вершин существует, напечатайте #t, затем количество вершин в нём, а затем список вершин, входящих в это подмножество. Из всех допустимых подмножеств выберите подмножество минимальной мощности.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b)(b c)(c d)(d a))
1
Пример печати результата:
#t
1
(a)

Вариант 11. Задача о ранце


На вход программе подаются три списка длины N (N > 0) список весов предметов Wi (Wi > 0, 1 ≤ i ≤ N), список объёмов предметов Vi (Vi > 0, 1 ≤ i ≤ N) и список их стоимостей Ci (Ci > 0, 1 ≤ i ≤ N). Все веса, объёмы и стоимости предметов -- целые числа. Затем на вход программе подаются три целых числа: предельный вес W (W > 0), предельный объём V (W > 0) и минимальную стоимость K (K > 0).
Существует ли такое подмножество предметов, для которого суммарный вес предметов в этом подмножестве не превышает W, суммарный объём предметов не превышает V, а суммарная стоимость предметов не меньше K? Если такого подмножества не существует, напечатайте #f. Если такое подмножество существует, напечатайте #t, затем суммарный вес предметов, их суммарный объём, их суммарную стоимость, а затем список номеров предметов, вошедших в это подмножество. Из всех возможных разбиений выберите такое, которое максимизирует суммарную стоимость предметов в ранце.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
(1 1 2 2)
(2 1 1 2)
(1 2 3 4)
3
3
4
Пример печати результата:
#t
3
3
6
(2 4)

Вариант 12. Разрезание циклов рёбрами


На вход программе подаётся описание невзвешенного ориентированного графа G = (V, E) в виде списка рёбер. Вершины графа vi∈V представлены атомами, а описание каждого ребра имеет вид (FROM TO). Затем на вход программе подаётся число K.
Существует ли в графе G такое подмножество рёбер F (F ⊆ E) мощности не большей K, что каждый цикл в графе G содержит хотя бы одно ребро из множества F? Если такого подмножества рёбер не существует, напечатайте #f, а если такое подмножество рёбер существует, напечатайте #t, затем количество рёбер в нём, а затем список рёбер, входящих в это подмножество. Из всех допустимых подмножеств выберите подмножество минимальной мощности.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b)(b c)(c d)(d a))
1
Пример печати результата:
#t
1
((a b))

Вариант 13. Независимое множество


На вход программе подаётся описание неориентированного невзвешенного графа G = (V, E) в виде списка описаний рёбер. Вершины vi∈V обозначаются атомами, рёбра представляются списками вида (NODE1 NODE2). Затем на вход программе подаётся целое число K (1 ≤ K ≤ |V|).
Существует ли в графе G независимое множество мощности, не меньшей K? Независимым множеством графа G называется подмножество V, в котором никакие две вершины не соединены ребром. Мощность множества -- это количество вершин в нём. Если такого множества не существует, напечатайте #f. Иначе напечатайте #t, затем мощность независимого множества, затем список вершин, входящих в него. Из всех возможных решений задачи, удовлетворяющих условию, выберите множество с максимальной мощностью.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b) (b c) (c d) (a d))
2
Пример печати результата:
#t
2
(b d)

Вариант 14. Максимальный разрез графа


На вход программе подаётся описание неориентированного взвешенного графа G = (V, E) в виде списка описаний рёбер. Вершины vi∈V обозначаются атомами, рёбра представляются списками вида (NODE1 NODE2 WEIGHT). Затем на вход программе подаётся целое число K (1 ≤ K ≤ |V|).
Существует ли в графе разрез C величины, не меньшей K? Разрезом C = (S, T) графа G называется разбиение множества V вершин графа на два непустых непересекающихся подмножества S и T, таких что: S ∪ T = V, S ∩ T = ∅, |S| > 0, |T| > 0. С разрезом C = (S, T) связывают множество всех рёбер исходного графа, таких что один из концов ребра является вершиной из S, другой -- вершиной из T. Величина разреза C -- это суммарный вес рёбер в его множестве. Если такого разреза не существует, напечатайте #f. Иначе напечатайте #t, затем величину разреза, затем список рёбер, входящих в разрез. Из всех возможных решений задачи, удовлетворяющих условию, выберите разрез максимальной величины.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b 2) (b c 1) (c d 1) (a d 1) (a e 1) (d e 1))
2
Пример печати результата:
#t
6
((a b 2) (b c 1) (c d 1) (a d 1) (a e 1))

Вариант 15. Доминирующее множество рёбер


На вход программы подаётся список рёбер неориентированного графа G = (V, E). Вершины vi∈V обозначаются атомами, рёбра представляются списками вида (NODE1 NODE2). Затем на вход программы подаётся целое число K (1 ≤ K).
Существует ли в графе G доминирующее подмножество рёбер, то есть такое подмножество рёбер F ⊆ E, что |F| ≤ K и каждое ребро e не из этого подмножества рёбер (e ∈ E-F) имеет общую вершину по крайней мере с одним ребром из подмножества F? Если доминирующего подмножества рёбер не существует, напечатайте #f. Если доминирующее подмножество рёбер существует, напечатайте #t, затем количество рёбер в доминирующем подмножестве, а затем список рёбер, входящих в доминирующее подмножество. Из всех возможных вариантов доминирующего подмножества выберите вариант с минимальным количеством рёбер.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b) (a c) (a d))
1
Пример печати результата:
#t
1
((a d))

Вариант 16. Выполнимость КНФ


На вход программе подаётся конъюнктивная нормальная форма, записанная списком списков. Все списки внутри большого списка рассматриваются как дизъюнкции, объединённые конъюнкцией. В каждом списке-дизъюнкции элементами являются символы (например, alpha или x) либо списки из двух элементов (not символ), обозначающие отрицания.
Выполнима ли КНФ, то есть, существует ли набор значений символов, на котором КНФ принимает значение «истина»? Если КНФ выполнима, напечатайте #t и набор значений символов в виде списка списков (символ значение).
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
(((not x1)) (x10 (not x11) x101))
Пример печати результата:
#t
((x1 #f) (x10 #t) (x11 #f) (x101 #t))

Вариант 17. Задача сельского почтальона


На вход программе подаётся описание взвешенного неориентированного графа G = (V, E) в виде списка описаний рёбер. Каждое описание ребра e ∈ E имеет вид (NODE1 NODE2 WEIGHT), где NODE1, NODE2 -- атомы, WEIGHT -- целое положительное число. Затем на вход программе подаётся целое положительное число K и список рёбер L.
Существует ли в графе гамильтонов G цикл, то есть путь, начинающийся и заканчивающийся в одной и той же вершине и проходящий через каждую вершину из графа G только один раз, стоимости не более чем K, включающий в себя все рёбра из списка L (и, возможно, другие)? Стоимость пути -- это суммарная стоимость рёбер, составляющих путь. Если искомый цикл не существует, напечатайте #f. Если искомый цикл существует, напечатайте #t, далее стоимость цикла, а затем найденный цикл в виде списка. Первым и последним элементом списка должен быть один и тот же атом. Если существует несколько возможных решений, найдите решение с минимальной стоимостью.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
((a b 1) (b c 1) (c d 1) (a d 1))
4
((a b) (a d))
Пример печати результата:
#t
4
(a b c d a)

Вариант 18. Задача о рюкзаках


На вход программе подаются два списка длины N (N > 0) список весов предметов Wi (Wi > 0, 1 ≤ i ≤ N) и список их стоимостей Ci (Ci > 0, 1 ≤ i ≤ N). Все веса и стоимости предметов -- целые числа. Затем на вход программе подаются список весов рюкзаков (Bj > 0) и K (K > 0).
Существует ли такой набор Kj -- множеств предметов, положенных в j-ый рюкзак, для которого суммарный вес предметов в каждом Kj не превышает вес рюкзака Bj, любой предмет либо входит в одно из Kj, либо не входит ни в одно, а сумма всех суммарных стоимостей предметов, входящих Kj, не меньше K? Если такого набора не существует, напечатайте #f. Если такой набор существует, напечатайте #t, затем список пар (<список номеров предметов из Kj> <вес предметов Kj>), а затем суммарную стоимость всех предметов, положенных в рюкзаки. Из всех возможных решений выберите такое, которое максимизирует суммарную стоимость предметов в рюкзаках.
В процессе нахождения решения должен быть предусмотрен сбор данных о ходе процесса приближения текущего решения задачи к оптимальному.
Пример входных данных:
(1 1 2 2)
(4 3 2 1)
(3 2)
5
Пример печати результата:
#t
(((1 3) 3) ((2) 1))
9

Предупреждение


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

  

© Кафедра системного программирования ВМК МГУ.

Обновлено: 31.8.2016